Mercury Bugs - mercury
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0000317mercuryBugpublic2014-02-07 15:332014-02-10 10:38
Reporterlpimmes 
Assigned Tojuliensf 
PriorityhighSeveritymajorReproducibilityalways
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
up.
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.
Relationships
Attached Files? lngCommonSubseqStck.m (9,448) 2014-02-07 15:33
https://bugs.mercurylang.org/file_download.php?file_id=201&type=bug
? lngCommonSubseqStck_tbl.m (12,434) 2014-02-07 19:34
https://bugs.mercurylang.org/file_download.php?file_id=202&type=bug

Notes
(0000640)
juliensf   
2014-02-07 16:39   
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.
(0000641)
lpimmes   
2014-02-07 19:36   
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
Thanks.
(0000642)
juliensf   
2014-02-07 20:06   
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)
(0000643)
lpimmes   
2014-02-08 07:26   
OK, great. It works, i.e., compiles, and shows my output, and statistics output.
Thanks.
(0000644)
ttmrichter   
2014-02-09 01:45   
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
(0000645)
juliensf   
2014-02-10 10:38   
Not a bug.

Issue History
Date ModifiedUsernameFieldChange
2014-02-07 15:33lpimmesNew Issue
2014-02-07 15:33lpimmesFile Added: lngCommonSubseqStck.m
2014-02-07 16:39juliensfNote Added: 0000640
2014-02-07 19:34lpimmesFile Added: lngCommonSubseqStck_tbl.m
2014-02-07 19:36lpimmesNote Added: 0000641
2014-02-07 20:06juliensfNote Added: 0000642
2014-02-08 07:26lpimmesNote Added: 0000643
2014-02-09 01:45ttmrichterNote Added: 0000644
2014-02-10 10:38juliensfNote Added: 0000645
2014-02-10 10:38juliensfStatusnew => resolved
2014-02-10 10:38juliensfResolutionopen => no change required
2014-02-10 10:38juliensfAssigned To => juliensf