| View Issue Details [ Jump to Notes ] | [ Issue History ] [ Print ] | ||||||||
| ID | Project | Category | View Status | Date Submitted | Last Update | ||||
|---|---|---|---|---|---|---|---|---|---|
| 0000317 | mercury | Bug | public | 2014-02-07 15:33 | 2014-02-10 10:38 | ||||
| Reporter | lpimmes | ||||||||
| Assigned To | juliensf | ||||||||
| Priority | high | Severity | major | Reproducibility | always | ||||
| Status | resolved | Resolution | no change required | ||||||
| Platform | OS | OSx 10.9.1 | OS Version | ||||||
| Product Version | |||||||||
| Target Version | Fixed in Version | ||||||||
| Summary | 0000317: :- pragma memo(findLngCmnSubsqStck/3). WORKING; not sure how to do static Asymptotic analysis | ||||||||
| Description | Answers 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 Reproduce | See listing for comments of trace run. Perhaps I counted incorrectly. Thanks again to the Mercury team, and Mercury! | ||||||||
| Additional Information | Example 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. | ||||||||
| Tags | No tags attached. | ||||||||
| Attached Files |
| ||||||||
 Relationships |
|
 Relationships |
| Notes |
|
|
juliensf (administrator) 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. |
|
lpimmes (reporter) 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. |
|
juliensf (administrator) 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) |
|
lpimmes (reporter) 2014-02-08 07:26 |
OK, great. It works, i.e., compiles, and shows my output, and statistics output. Thanks. |
|
ttmrichter (reporter) 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 |
|
juliensf (administrator) 2014-02-10 10:38 |
Not a bug. |
| Notes |
| 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 |