How to use dynamic databases in Prolog?

Question

I have written the following program, which calculates the longest non-decreasing sub-sequence of input array.

The sub-program to find the longest list from the list of lists is taken from stackoverflow (How do I find the longest list in a list of lists) itself.

:- dynamic lns/2.
:- retractall(lns(_, _)).

lns([], []).
lns([X|_], [X]).
lns([X|Xs], [X, Y|Ls]) :-
    lns(Xs, [Y|Ls]),
    X < Y,
    asserta(lns([X|Xs], [X, Y|Ls])).
lns([_|Xs], [Y|Ls]) :-
    lns(Xs, [Y|Ls]).

% Find the longest list from the list of lists.
lengths([], []).
lengths([H|T], [LH|LengthsT]) :-
    length(H, LH),
    lengths(T, LengthsT).

lengthLongest(ListOfLists, Max) :-
    lengths(ListOfLists, Lengths),
    max_list(Lengths, Max).

longestList(ListOfLists, Longest) :-
    lengthLongest(ListOfLists, Len),
    member(Longest, ListOfLists),
    length(Longest, Len).

optimum_solution(List, Ans) :-
    setof(A, lns(List, A), P),
    longestList(P, Ans), 
    !.

I have used the Prolog dynamic database for memoization purpose. Though the program with database runs slower than the program without database. Below are the comparative times between two runs.

?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 53,397 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 609577 Lips)
Ans = [0, 2, 6, 9]. %% With database

?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 4,097 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2322004 Lips)
Ans = [0, 2, 6, 9]. %% Without database. commented out the database usage.

I would like to know if I am using the dynamic database correctly. Thanks!

You really should link to the question or answer from which you got your code. — , Feb 05 '16 at 03:18
Are you sure that you are doing the timing correctly? Is it at all possible that this second run you show is actually using the memoized facts? — , Feb 05 '16 at 03:20
@DanielLyons Since `asserta` is used (not `assertz`) the longest subsequence found so far will be matched first. Since the lists will be unified in the head of the predicate, there is no explicit (native Prolog) traversal, which is why it is not entirely bad as an approach (the traversal still happens of course, but much more efficient). I would nevertheless like to see a link to the source of this code. — , Feb 05 '16 at 07:42
@Boris. I have added link to the source where I took the solution to find the longest list from list of lists. I also verified again and I can see that I am doing the timing correctly. — UnSat, Feb 05 '16 at 15:04
@Daniel. I could not think of O(n) solution to this problem. If you know one, could you please share? — UnSat, Feb 05 '16 at 15:04
@user114754. There **is** no O(n) algorithm for this problem. For more on this, look at https://en.m.wikipedia.org/wiki/Longest_increasing_subsequence . — repeat, Feb 05 '16 at 21:28
@user114754. Want some more clpfd-based approaches? I got at least two others. — repeat, Feb 05 '16 at 21:31

Daniel Lyons · Accepted Answer · 2016-02-06T07:56:30.460

2

The issue is that as you are traversing the list building subsequences, you need to consider only prior subsequences whose last value is less than the value you have in-hand. The problem is that Prolog's first-argument indexing is doing an equality check, not a less-than check. So Prolog will have to traverse the entire store of lns/2, unifying the first parameter with a value so you can check to see if it's less and then backtracking to get the next.

edited Feb 06 '16 at 07:56

answered Feb 05 '16 at 17:32

Daniel Lyons

22,421
2
50
77

2

What about tie situations? Consider: First, `longest_increasing_subsequence([0,8,4,12,2,10,6,14,1],[0,2,6,14])` succeeds. Let's append `9` to above list! Now, `longest_increasing_subsequence([0,8,4,12,2,10,6,14,1,9],[0,2,6,9])` succeeds, but `longest_increasing_subsequence([0,8,4,12,2,10,6,14,1,9],[0,2,6,14])` fails even though `[0,2,6,14]` **still is** optimal. – repeat Feb 05 '16 at 19:01
@Daniel. Your explanation about first-argument indexing explains why dynamic database usage is slowing down the program instead of reducing the run time. Thanks. Though as 'repeat' pointed out, solution you provided fails in few situations. Mine program still works but is slower. – UnSat Feb 05 '16 at 20:45

score 2 · Answer 2 · edited May 23 '17 at 12:15

Earlier, we presented a concise solution based on clpfd. Now we aim at generality and efficiency!

:- use_module([library(clpfd), library(lists)]).

list_long_nondecreasing_subseq(Zs, Xs) :-
   minimum(Min, Zs),
   append(_, Suffix, Zs),
   same_length(Suffix, Xs),
   zs_subseq_taken0(Zs, Xs, Min).

zs_subseq_taken0([], [], _).
zs_subseq_taken0([E|Es], [E|Xs], E0) :-
   E0 #=< E,
   zs_subseq_taken0(Es, Xs, E).
zs_subseq_taken0([E|Es], Xs, E0) :-
   zs_subseq_taken0_min0_max0(Es, Xs, E0, E, E).

zs_subseq_taken0_min0_max0([], [], E0, _, Max) :-
   Max #< E0.
zs_subseq_taken0_min0_max0([E|Es], [E|Xs], E0, Min, Max) :-
   E0 #=< E,
   E0 #> Min #\/ Min #> E,
   E0 #> Max #\/ Max #> E,
   zs_subseq_taken0(Es, Xs, E).
zs_subseq_taken0_min0_max0([E|Es], Xs, E0, Min0, Max0) :-
   Min #= min(Min0,E),
   Max #= max(Max0,E),
   zs_subseq_taken0_min0_max0(Es, Xs, E0, Min, Max).

Sample query using SICStus Prolog 4.3.2 (with pretty-printed answer sequence):

?- list_long_nondecreasing_subseq([0,8,4,12,2,10,6,14,1,9], Xs).
   Xs = [0,8,12,14]
;  Xs = [0,8,10,14]
;  Xs = [0,4,12,14]
;  Xs = [0,4,10,14]
;  Xs = [0,4, 6,14]
;  Xs = [0,4, 6, 9]
;  Xs = [0,2,10,14]
;  Xs = [0,2, 6,14]
;  Xs = [0,2, 6, 9]
;  Xs = [0,8,9]
;  Xs = [0,4,9]
;  Xs = [0,2,9]
;  Xs = [0,1,9]
;  false.

Note that the answer sequence of list_long_nondecreasing_subseq/2 may be a lot smaller than the one given by list_nondecreasing_subseq/2.

Above list [0,8,4,12,2,10,6,14,1,9] has 9 non-descending subsequences of length 4—all are "returned" by both list_nondecreasing_subseq/2 and list_long_nondecreasing_subseq/2.

The respective answer sequence sizes, however, differ considerably: (65+9=74) vs (4+9=13).

score 1 · Answer 3 · edited May 23 '17 at 10:28

1

TL;DR: In this answer we implement a very general approach based on clpfd.

:- use_module(library(clpfd)).

list_nondecreasing_subseq(Zs, Xs) :-
   append(_, Suffix, Zs),
   same_length(Suffix, Xs),
   chain(Xs, #=<),
   list_subseq(Zs, Xs).                % a.k.a. subset/2 by @gusbro

Sample query using SWI-Prolog 7.3.16:

?- list_nondecreasing_subseq([0,8,4,12,2,10,6,14,1,9], Zs).
   Zs = [0,8,12,14]
;  Zs = [0,8,10,14]
;  Zs = [0,4,12,14]
;  Zs = [0,4,10,14]
;  Zs = [0,4,6,14]
;  Zs = [0,4,6,9]
;  Zs = [0,2,10,14]
;  Zs = [0,2,6,14]
;  Zs = [0,2,6,9]
;  Zs = [0,8,12]
...
;  Zs = [9]
;  Zs = []
;  false.

Note the particular order of the answer sequence! The longest lists come first, followed by the lists a little smaller ... all the way down to singleton lists, and the empty list.

edited May 23 '17 at 10:28

Community

1
1

answered Feb 05 '16 at 20:21

repeat

18,496
4
54
166

3

Just 4 lines...!! (+ gusbro solution for subset/2). Very elegant and concise...!! Thank you. – UnSat Feb 05 '16 at 21:40
@user114754. Thx for appreciating! With some Prolog systems, `list_subseq/2` is available out-of-the-box as a library predicate: [SICStus Prolog](https://sicstus.sics.se/), for instance, provides [`subseq0/2`](https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002dlists.html). – repeat Feb 05 '16 at 23:23
2

"I would like to know if I am using the dynamic database correctly. Thanks!"—the question. – Daniel Lyons Feb 06 '16 at 08:32
1

@DanielLyons. The OP has answered *that* question, don't you agree? "Do I get correct answer(s)?" Yes. "Am I saving memory?" No. "Does it run faster?" No. – repeat Feb 06 '16 at 09:24

score 0 · Answer 4 · edited May 23 '17 at 12:07

Keeps getting better! In this answer we present list_long_nondecreasing_subseq__NEW/2, a drop-in replacement of list_long_nondecreasing_subseq/2—presented in this earlier answer.

Let's cut to the chase and define list_long_nondecreasing_subseq__NEW/2!

:- use_module([library(clpfd), library(lists), library(random), library(between)]).

list_long_nondecreasing_subseq__NEW(Zs, Xs) :-
   minimum(Min, Zs),
   append(Prefix, Suffix, Zs),
   same_length(Suffix, Xs),
   zs_skipped_subseq_taken0(Zs, Prefix, Xs, Min).

zs_skipped_subseq_taken0([], _, [], _).
zs_skipped_subseq_taken0([E|Es], Ps, [E|Xs], E0) :-
   E0 #=< E,
   zs_skipped_subseq_taken0(Es, Ps, Xs, E).
zs_skipped_subseq_taken0([E|Es], [_|Ps], Xs, E0) :-
   zs_skipped_subseq_taken0_min0_max0(Es, Ps, Xs, E0, E, E).

zs_skipped_subseq_taken0_min0_max0([], _, [], E0, _, Max) :-
   Max #< E0.
zs_skipped_subseq_taken0_min0_max0([E|Es], Ps, [E|Xs], E0, Min, Max) :-
   E0 #=< E,
   E0 #> Min #\/ Min #> E,
   E0 #> Max #\/ Max #> E,
   zs_skipped_subseq_taken0(Es, Ps, Xs, E).
zs_skipped_subseq_taken0_min0_max0([E|Es], [_|Ps], Xs, E0, Min0, Max0) :-
   Min #= min(Min0,E),
   Max #= max(Max0,E),
   zs_skipped_subseq_taken0_min0_max0(Es, Ps, Xs, E0, Min, Max).

So ... does it still work as before? Let's run some tests and compare the answer sequences:

| ?- setrand(random(29251,13760,3736,425005073)),
     between(7, 23, N), 
     nl,
     write(n=N),
     write(' '),
     length(Zs, N),
     between(1, 10, _),
     maplist(random(1,N), Zs),
     findall(Xs1, list_long_nondecreasing_subseq(     Zs,Xs1), Xss1),
     findall(Xs2, list_long_nondecreasing_subseq__NEW(Zs,Xs2), Xss2),
     ( Xss1 == Xss2 -> true ; throw(up) ),
     length(Xss2,L),
     write({L}),
     false.

n=7 {3}{8}{3}{7}{2}{5}{4}{4}{8}{4}
n=8 {9}{9}{9}{8}{4}{4}{7}{5}{6}{9}
n=9 {9}{8}{5}{7}{10}{7}{9}{4}{5}{4}
n=10 {7}{12}{7}{14}{13}{19}{13}{17}{10}{7}
n=11 {14}{17}{7}{9}{17}{21}{14}{10}{10}{21}
n=12 {25}{18}{20}{10}{32}{35}{7}{30}{15}{11}
n=13 {37}{19}{18}{22}{20}{14}{10}{11}{8}{14}
n=14 {27}{9}{18}{10}{20}{29}{69}{28}{10}{33}
n=15 {17}{24}{13}{26}{32}{14}{22}{28}{32}{41}
n=16 {41}{55}{35}{73}{44}{22}{46}{47}{26}{23}
n=17 {54}{43}{38}{110}{50}{33}{48}{64}{33}{56}
n=18 {172}{29}{79}{36}{32}{99}{55}{48}{83}{37}
n=19 {225}{83}{119}{61}{27}{67}{48}{65}{90}{96}
n=20 {58}{121}{206}{169}{111}{66}{233}{57}{110}{146}
n=21 {44}{108}{89}{99}{149}{148}{92}{76}{53}{47}
n=22 {107}{137}{221}{79}{172}{156}{184}{78}{162}{112}
n=23 {163}{62}{76}{192}{133}{372}{101}{290}{84}{378}
no

All answer sequences were exactly identical! ... So, how about runtimes?

Let's run some more queries using SICStus Prolog 4.3.2 and pretty-print the answers!

?- member(N, [15,20,25,30,35,40,45,50]),
   length(Zs, N),
   _NN #= N*N,
   maplist(random(1,_NN), Zs),
   call_time(once(list_long_nondecreasing_subseq(     Zs, Xs )), T1),
   call_time(once(list_long_nondecreasing_subseq__NEW(Zs,_Xs2)), T2),
   Xs == _Xs2,
   length(Xs,L).
N = 15, L =  4, T1 =    20, T2 =    0, Zs = [224,150,161,104,134,43,9,111,76,125,50,68,202,178,148], Xs = [104,111,125,202] ;
N = 20, L =  6, T1 =    60, T2 =   10, Zs = [71,203,332,366,350,19,241,88,370,100,288,199,235,343,181,90,63,149,215,285], Xs = [71,88,100,199,235,343] ;
N = 25, L =  7, T1 =   210, T2 =   20, Zs = [62,411,250,222,141,292,276,94,548,322,13,317,68,488,137,33,80,167,101,475,475,429,217,25,477], Xs = [62,250,292,322,475,475,477] ;
N = 30, L = 10, T1 =   870, T2 =   30, Zs = [67,175,818,741,669,312,99,23,478,696,63,793,280,364,677,254,530,216,291,660,218,664,476,556,678,626,75,834,578,850], Xs = [67,175,312,478,530,660,664,678,834,850] ;
N = 35, L =  7, T1 =   960, T2 =  120, Zs = [675,763,1141,1070,299,650,1061,1184,512,905,139,719,844,8,1186,1006,400,690,29,791,308,1180,819,331,482,982,81,574,1220,431,416,357,1139,636,591], Xs = [299,650,719,844,1006,1180,1220] ;
N = 40, L =  9, T1 =  5400, T2 =  470, Zs = [958,1047,132,1381,22,991,701,1548,470,1281,358,32,605,1270,692,1020,350,794,1451,11,985,1196,504,1367,618,1064,961,463,736,907,1103,719,1385,1026,935,489,1053,380,637,51], Xs = [132,470,605,692,794,985,1196,1367,1385] ;
N = 45, L = 10, T1 = 16570, T2 = 1580, Zs = [1452,171,442,1751,160,1046,470,450,1245,971,1574,901,1613,1214,1849,1805,341,34,1923,698,156,1696,717,1708,1814,1548,463,421,1584,190,1195,1563,1772,1639,712,693,1848,1531,250,783,1654,1732,1333,717,1322], Xs = [171,442,1046,1245,1574,1613,1696,1708,1814,1848] ;
N = 50, L = 11, T1 = 17800, T2 = 1360, Zs = [2478,2011,2411,1127,1719,1286,1081,2042,1166,86,355,894,190,7,1973,1912,753,1411,1082,70,2142,417,1609,1649,2329,2477,1324,37,1781,1897,2415,1018,183,2422,1619,1446,1461,271,56,2399,1681,267,977,826,2145,2318,2391,137,55,1995], Xs = [86,355,894,1411,1609,1649,1781,1897,2145,2318,2391] ;
false.

Of course, the baroque approach shown in this answer simply cannot compete with "serious" suitable algorithms for determining the lis—still, getting 10X speedup always feels good:)

How to use dynamic databases in Prolog?

4 Answers4