% Longest Common Subsequence, 06-feb-2014 % Redo this code, use just strings, easier for user to understand. % LPImmes % Employ pragma declaration in order to memoize-- makes a huge difference, % see test cases 9. % Future, show argument calls to findLngCmnSubsq/2, with and without % pragma declaration. %lngCommSubseq 487>uname -a %Darwin luke-immess-imac-2.local 13.0.0 Darwin Kernel %Version 13.0.0: Thu Sep 19 22:22:27 PDT 2013; %root:xnu-2422.1.72~6/RELEASE_X86_64 x86_64 %Make sure that .bashrc has: % MERCURY_GCC=/Developer-3.2/usr % ... % $MERCURY_GCC/bin:\ % ... % % Comment out this path entry for compiling, e.g., python modules. % %lngCommSubseq 485>gcc --version %i686-apple-darwin10-gcc-4.2.1 (GCC) 4.2.1 (Apple Inc. build 5646) %Copyright (C) 2007 Free Software Foundation, Inc. %This is free software; see the source for copying conditions. There is NO %warranty; not even for MERCHANTABILITY %or FITNESS FOR A PARTICULAR PURPOSE. % %lngCommSubseq 483>mmc -version %mercury_compile: invalid grade `ion' %Mercury Compiler, version 13.05, configured for x86_64-apple-darwin12.5.0 %Copyright (C) 1993-2013 The University of Melbourne %Usage: mmc [] %Use `mmc --help' for more information. %BUILD, either one: % mmc --make --fully-strict -E -v -O 0 --use-subdirs lngCommonSubseqStck_tbl % mmc --grade none.gc.stseg --fully-strict -E -v -O 0 --use-subdirs lngCommSubseqStck_tbl %With logging: try to run % lngCommSubsq 503>./lngCommSubseqStck.bash % Working, and predicates found in module, but not sure of semantics of his logging. % RUN: % Caching is on, i.e., pragma. Just add +1 when calling findLngCmnSubsqStck. % Count what occurs, not what other text books have mentioned. % Generalize from examples below: % If input strings are everywhere not equal, % and lengths equal, then total number of calls = length(leftString) + 1, % if lengths not equal length, then total number of calls = length(largerString) + 1. % If input strings equal in some positions, and unequal lengths then % length(shorterString) <= total number of calls <= length(longerString), % if equal lengths then total number of calls = length(leftString) + 1 % % TROUBLE is that, I am analyzing algorithm based on Mercury's caching. If another language, % on another machine, was also cached, then would analysis be the same? If caching % works the same way, then we should count and obtain identical results. % lngCommSubseqStck 477>./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 length: 0, b length: 0, findLngCmnSubsqStck calls: 1. % 1 % LongestCommonSubsequence('a', 'b')='', % a length: 1, b length: 1, findLngCmnSubsqStck calls: 2. % 2 % LongestCommonSubsequence('aa', 'bb')='', % a length: 2, b length: 2, findLngCmnSubsqStck calls: 3. % 3 % LongestCommonSubsequence('aaa', 'bbb')='', % a length: 3, b length: 3, findLngCmnSubsqStck calls: 4. % 4 % LongestCommonSubsequence('aaaa', 'bbbb')='', % a length: 4, b length: 4, findLngCmnSubsqStck calls: 5. % 5 % LongestCommonSubsequence('aaaaa', 'bbbbb')='', % a length: 5, b length: 5, findLngCmnSubsqStck calls: 6. % 6 % LongestCommonSubsequence('aaaaaa', 'bbbbbb')='', % a length: 6, b length: 6, findLngCmnSubsqStck calls: 7. % 14 % LongestCommonSubsequence('aaaaaaaaaaaaaa', 'bbbbbbbbbbbbbb')='', % a length: 14, b length: 14, findLngCmnSubsqStck calls: 15. % 15 % LongestCommonSubsequence('aaaaaaaaaaa', 'bbbbbbb')='', % a length: 11, b length: 7, findLngCmnSubsqStck calls: 8. % 16 % LongestCommonSubsequence('aaaaaaaaaaa', 'bbbbbbbbb')='', % a length: 11, b length: 9, findLngCmnSubsqStck calls: 10. % 17 % LongestCommonSubsequence('aaa', 'bb')='', % a length: 3, b length: 2, findLngCmnSubsqStck calls: 3. % 23 % LongestCommonSubsequence('abcbdab', 'bdcaba')='bcba', % a length: 7, b length: 6, findLngCmnSubsqStck calls: 9. % 24 % LongestCommonSubsequence('a', 'b')='', % a length: 1, b length: 1, findLngCmnSubsqStck calls: 2. % 32 % LongestCommonSubsequence('acdefaaa', 'badbbeabfbb')='adef', % a length: 8, b length: 11, findLngCmnSubsqStck calls: 13. % 31 % LongestCommonSubsequence('aabcaaadaaa', 'bcbcabbdbabb')='bcada', % a length: 11, b length: 12, findLngCmnSubsqStck calls: 17. % 30 % LongestCommonSubsequence('aaaaaaaaaaa', 'bbbbbabbbabb')='aa', % a length: 11, b length: 12, findLngCmnSubsqStck calls: 13. % 29 % LongestCommonSubsequence('bac', 'abc')='bc', % a length: 3, b length: 3, findLngCmnSubsqStck calls: 5. % 28 % LongestCommonSubsequence('bac', 'cab')='b', % a length: 3, b length: 3, findLngCmnSubsqStck calls: 4. % 27 % LongestCommonSubsequence('ba', 'a')='a', % a length: 2, b length: 1, findLngCmnSubsqStck calls: 3. % хорошо́ EOF, Quit % lngCommSubseqStck 477> %33 %LongestCommonSubsequence('acdeabe', 'acbe')='acbe', % a length: 7, b length: 4, findLngCmnSubsqStck calls: 8. %34 %LongestCommonSubsequence('acdeg', 'acghi')='acg', % a length: 5, b length: 5, findLngCmnSubsqStck calls: 6. :- module lngCommonSubseqStck_tbl. % name of file, for now :- interface. :- import_module io. :- pred main(io, io). :- mode main(di, uo) is det. :- implementation. :- import_module table_statistics, pair, char, int, list, array, string. % io. %log4m. % Analysis % Following author uses longest length, versus, longest common sequence, as an output: % http://www.ics.uci.edu/~eppstein/161/960229.html % Time analysis for his code: each call to subproblem takes constant time. We call it once from the main routine, % and at most twice every time we fill in an entry of array L. There are (m+1)(n+1) entries, so the % total number of calls is at most 2(m+1)(n+1)+1 and the time is O(mn). % % Comment pragma out, and run test case: 9, aaaa..., bbb..., and we wait forever. % Using pragma, i.e, caching, we solve same problem very quickly. % Work out by hand: (aaaa, bbbb); some caching does occur, e.g., (aaa, bb). For this small example it does not % seem that the amount of caching is significant. % See mercury IO: http://dbpatterson.tumblr.com/post/10101986648 % Calling java: % http://www.mercurylang.org/information/doc-release/mercury_ref/Using-pragma-foreign_005fexport-for-Java.html % Pragma, i.e., caching really speeds up execution, but number of calls is the same in either case. % I would be expecting much fewer calls if caching, i.e., no repeat recursion. % ( I used a version in which counting was returning NewCnt, which I took out here.) %Reply: https://bugs.mercurylang.org/view.php?id=317 % 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. % http://mercurylang.org/information/doc-release/mercury_ref/Tabled-evaluation.html#Tabled-evaluation :- func findLngCmnSubsqStck(int, string, string) = pair(int, string). :- mode findLngCmnSubsqStck(in, in, in) = out is det. :- pragma memo(findLngCmnSubsqStck/3, [statistics]). % Cache old results; no need to write additional code. findLngCmnSubsqStck(Cnt, First, Second) = LngCmnSq :- % Don't use ';' even though a little easier to read, because this neccessites 'multi'. % And multi can be problematic with memo pragma. % Compare these two strings left to right. % I, % do spliting which is n+m, if two different length, use 2m for same length % add +2m more for string.length comparison. % II, do recursive call n times: see above for discussion % So, from I and II, the total number of computations would be O(4mn). string.split(First, 1, A, FirstRest), string.split(Second, 1, B, SecondRest), (if (A = ""; B = "") % ';' means or; base case then LngCmnSq = pair(Cnt, "") % don't do any counting here else % recursive cases (if A = B % initial char = then P = findLngCmnSubsqStck(Cnt+1, FirstRest, SecondRest), % call func. +1 NewCnt = fst(P), LngCm = snd(P), LngCmnSq = pair(NewCnt, A ++ LngCm) else % initial char is != , so shorten size of the other string P1 = findLngCmnSubsqStck(Cnt+1, First, SecondRest), % call func. +1 NewCnt1 = fst(P1), LngCm1 = snd(P1), P2 = findLngCmnSubsqStck(Cnt+1, FirstRest, Second), % call func. +1 NewCnt2 = fst(P2), LngCm2 = snd(P2), (if string.length(LngCm1) >= string.length(LngCm2) then LngCmnSq = pair(NewCnt1, LngCm1) else LngCmnSq = pair(NewCnt2, LngCm2) ) % S1 >= S2 ) % A = B ). % empty string test :- func longestCommonSubsequence(int) = string. :- mode longestCommonSubsequence(in) = out is det. longestCommonSubsequence(Indx) = LngCmnSubsq :- % Input test cases from tst/0: 0, 1, 2, 3, 4 ,... PairsTst = array.lookup(tst, Indx), A = list.det_index0(PairsTst, 0), LenA = string.length(A), B = list.det_index0(PairsTst, 1), LenB = string.length(B), P = findLngCmnSubsqStck(1, A, B), % call func. +1 Cnt = fst(P), LngCm = snd(P), format("LongestCommonSubsequence('%s', '%s')='%s',\n\ta length: %i, b length: %i, findLngCmnSubsqStck calls: %i.", [s(A), s(B), s(LngCm), i(LenA), i(LenB), i(Cnt)], LngCmnSubsq). :- func tst = array(list(string)). :- mode tst = out is det. % When prompted for test index, use either: 0, 1, 2, 3, 4. tst = array.array([ % Worst case analysis, if strings are != in every position % length a string = length of b string ["", ""], ["a", "b"], ["aa", "bb"], ["aaa", "bbb"], ["aaaa", "bbbb"], ["aaaaa", "bbbbb"], ["aaaaaa", "bbbbbb"], ["aaaaaaa", "bbbbbbb"], ["aaaaaaaa", "bbbbbbbb"], ["aaaaaaaaa", "bbbbbbbbb"], ["aaaaaaaaaa", "bbbbbbbbbb"], ["aaaaaaaaaaa", "bbbbbbbbbbb"], ["aaaaaaaaaaaa", "bbbbbbbbbbbb"], ["aaaaaaaaaaaaa", "bbbbbbbbbbbbb"], % starts to slow up here without caching ["aaaaaaaaaaaaaa", "bbbbbbbbbbbbbb"], ["aaaaaaaaaaa", "bbbbbbb"], ["aaaaaaaaaaa", "bbbbbbbbb"], ["aaa", "bb"], ["aaaa", "bbb"], ["aaaaa", "bb"], ["aaaaa", "b"], % go forever if no caching; careful on proportional fonts! Lengths can be deceiving. [ "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"], % typical cases ["a", "" ], % '' ["abcbdab", "bdcaba"], % 8 'bcba' Cormen text, p391, 36 calls ["a", "b"], % '' ["a", "ab"], % 'a' ["ab", "a"], % 'a' ["ba", "a"], % 'a' ["bac", "cab"], % 'b' ["bac", "abc"], % 'bc' ["aaaaaaaaaaa", "bbbbbabbbabb"], % 30 'aa' ["aabcaaadaaa", "bcbcabbdbabb"], % 31 'bcada' ["acdefaaa", "badbbeabfbb"], % 32 'adef' ["acdeabe", "acbe"], ["acdeg", "acghi"] ] ). main(In, Out) :- write_string("Input test case 0, 1, 2, 3, 4, ... Output longest common subsequence.\n^d to quit.\n\tCaching really speeds up execution, but same number of calls.\n", In, Out1), mainAux(Out1, Out). :- pred mainAux(io, io). :- mode mainAux(di, uo) is det. mainAux(In, Out) :- io.read_line_as_string(Result, In, Out0), % blank line, wait for input from console ( Result = eof, % c^d io.write_string("хорошо́ EOF, Quit\n", Out0, Out) ; Result = error(Error), io.format("IO error: %s\n", [s(io.error_message(Error))], Out0, Out) % IO error from readLine ; 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' % mainAux(Out1, Out) % do it again % if tabling, then just do a single iteration. ).