2023-12-01 07:22 AEDT

View Issue Details Jump to Notes ]
IDProjectCategoryView StatusLast Update
0000317mercuryBugpublic2014-02-10 10:38
Assigned Tojuliensf 
StatusresolvedResolutionno change required 
PlatformOSOSx 10.9.1OS Version
Product Version 
Target VersionFixed in Version 
Summary0000317: :- pragma memo(findLngCmnSubsqStck/3). WORKING; not sure how to do static Asymptotic analysis
DescriptionAnswers for longest common subsequence appear to be correct.
If pragma commented out, we take forever on longer test cases. Thus pragma is working,
but how?
I returned number of calls to findLngCmnSubsqStck/3. Number of calls remains the
same regardless of pragma or not. I would expect calls to be reduced significantly.
This is a bug in my understanding. Thank goodness pragma works, because it really speeds things
I would like to resolve what other authors have determined:
'total number of calls is at most 2(m+1)(n+1)+1 and the time is O(mn)'
Steps To ReproduceSee listing for comments of trace run. Perhaps I counted incorrectly.
Thanks again to the Mercury team, and Mercury!
Additional InformationExample output:
% lngCommSubseqStck 495>./lngCommonSubseqStck
% Input test case 0, 1, 2, 3, 4, ... Output longest common subsequence.
% ^d to quit.
% Caching really speeds up execution, but same number of calls.
% 0
% LongestCommonSubsequence('a', 'a')='a',
% a length: 1, b length: 1, findLngCmnSubsqStck calls: 2.
% 1
% LongestCommonSubsequence('aa', 'bb')='',
% a length: 2, b length: 2, findLngCmnSubsqStck calls: 4.
% 2
% LongestCommonSubsequence('aaa', 'bbb')='',
% a length: 3, b length: 3, findLngCmnSubsqStck calls: 7.
% 3
% LongestCommonSubsequence('aaaa', 'bbbb')='',
% a length: 4, b length: 4, findLngCmnSubsqStck calls: 11.
% 4
% LongestCommonSubsequence('aaaaa', 'bbbbb')='',
% a length: 5, b length: 5, findLngCmnSubsqStck calls: 16.
% 5
% LongestCommonSubsequence('aaaaaa', 'bbbbbb')='',
% a length: 6, b length: 6, findLngCmnSubsqStck calls: 22.
% 6
% LongestCommonSubsequence('aaaaaaa', 'bbbbbbb')='',
% a length: 7, b length: 7, findLngCmnSubsqStck calls: 29.
% 7
% LongestCommonSubsequence('aaaaaaaa', 'bbbbbbbb')='',
% a length: 8, b length: 8, findLngCmnSubsqStck calls: 37.
% 9
% LongestCommonSubsequence('aaaaaaaaaa', 'bbbbbbbbbb')='',
% a length: 10, b length: 10, findLngCmnSubsqStck calls: 56.
TagsNo tags attached.
Attached Files




juliensf (administrator)

The number of calls are the same because one of the things that the memo table in your
program caches is the number of calls.

If you want to examine the the actual number of calls that are made during program execution, you
will need to either profile the program or use the table statistics mechanism described in the ``Tabled evaluation'' section of the reference manual and the table_statistics module in the standard library.


lpimmes (reporter)

Hopefully, number of duplicate calls will appear on output.
Compiler problem:
lngCommonSubseqStck_tbl.m:295: In clause for predicate `mainAux'/2:
lngCommonSubseqStck_tbl.m:295: in argument 1 of call to predicate
lngCommonSubseqStck_tbl.m:295: `write_table_stats'/3:
lngCommonSubseqStck_tbl.m:295: type error: variable `Table' has type
lngCommonSubseqStck_tbl.m:295: `table_statistics.proc_table_statistics',
lngCommonSubseqStck_tbl.m:295: expected type was
lngCommonSubseqStck_tbl.m:295: `table_statistics.table_stats'.
     Result = io.ok(IndxStr),
     Indx = string.det_to_int(string.strip(IndxStr)), % use det_ so func. is det
     io.format("%s\n", [ s(longestCommonSubsequence(Indx)) ], Out0, Out1),
     table_statistics_for_findLngCmnSubsqStck_3(Table, Out1, Out2),
     write_table_stats(Table, Out2, Out) % compiler error: expected type was `table_statistics.table_stats'
Casting to that type does not work.
See lngCommonSubseqStck_tbl.m


juliensf (administrator)

The output of table_statistics_for_findLngCmnSubsqStck_3 has type proc_table_statistics/0 *not*
table_stats/0. You need to deconstruct the output in order to extract the tabling statistics you are interested in, for example:

         table_statistics_for_findLngCmnSubsqStck_3(ProcTableStats, Out1, Out2),
         ProcTableStats = proc_table_statistics(CallTableStats, _),
         CallTableStats = table_stats_curr_prev(Stats, _),
         write_table_stats(Stats, Out2, Out)


lpimmes (reporter)

OK, great. It works, i.e., compiles, and shows my output, and statistics output.


ttmrichter (reporter)

lpimmes: Have you considered signing up to an appropriate mailing list[1] instead of (ab)using a bug tracker for these kinds of issues?

[1] http://lists.mercurylang.org/listinfo/users


juliensf (administrator)

Not a bug.

-Issue History
Date Modified Username Field Change
2014-02-07 15:33 lpimmes New Issue
2014-02-07 15:33 lpimmes File Added: lngCommonSubseqStck.m
2014-02-07 16:39 juliensf Note Added: 0000640
2014-02-07 19:34 lpimmes File Added: lngCommonSubseqStck_tbl.m
2014-02-07 19:36 lpimmes Note Added: 0000641
2014-02-07 20:06 juliensf Note Added: 0000642
2014-02-08 07:26 lpimmes Note Added: 0000643
2014-02-09 01:45 ttmrichter Note Added: 0000644
2014-02-10 10:38 juliensf Note Added: 0000645
2014-02-10 10:38 juliensf Status new => resolved
2014-02-10 10:38 juliensf Resolution open => no change required
2014-02-10 10:38 juliensf Assigned To => juliensf
+Issue History