如何在Prolog中使用動態數據庫？

我寫了下面的程序，它計算輸入數組最長的非遞減子序列。如何在Prolog中使用動態數據庫？

從列表中找到最長列表的子程序取自計算器（How do I find the longest list in a list of lists）本身。

:- 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), 
    !.

我已將Prolog動態數據庫用於記憶目的。儘管帶數據庫的程序運行速度比沒有數據庫的程序慢。以下是兩次運行之間的比較時間。

?- 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.

我想知道我是否正確使用動態數據庫。謝謝！

來源

2016-02-05 UnSat

你真的應該鏈接到這個問題競爭或從中獲得代碼的答案。 – 2016-02-05 03:18:57

你確定你正在做正確的時間？你顯示的第二輪運行是否真的在使用記憶事實？ – 2016-02-05 03:20:01

@DanielLyons由於使用了'asserta'（而不是'assertz'），所以到目前爲止找到的最長的子序列將首先被匹配。由於列表將在謂詞的頭部統一，因此沒有明確的（本地Prolog）遍歷，這就是爲什麼它不是一種完全不好的方法（當然，遍歷仍然發生，但效率更高）。我仍然希望看到一個鏈接到這個代碼的來源。 – 2016-02-05 07:42:42

問題在於，當您遍歷列表構建子序列時，您只需要考慮前一個子序列的最後一個值小於您掌握的值。問題在於Prolog的第一個參數索引是在進行平等檢查，而不是低於檢查。因此，Prolog將不得不遍歷整個lns/2商店，將第一個參數統一爲一個值，以便檢查是否更少，然後回溯到下一個參數。

來源

2016-02-05 17:32:01

怎麼樣的領帶情況？考慮：首先，'longest_increasing_subsequence（[0,8,4,12,2,10,6,14,1]，[0,2,6,14]）'成功。讓我們追加'9'到上面的列表！現在，'longest_increasing_subsequence（[0,8,4,12,2,10,6,14,1,9]，[0,2,6,9]）'成功，但'longest_increasing_subsequence（[0,8,4 ，12,2,10,6,14,1,9]，[0,2,6,14]）'儘管'[0,2,6,14] **仍然是最優的， – repeat

@丹尼爾。您對第一個參數索引的解釋說明了爲什麼動態數據庫使用會減慢程序速度，而不是減少運行時間。謝謝。儘管如'重複'指出的那樣，您提供的解決方案在少數情況下仍然失敗。礦井計劃仍然有效，但速度較慢。 – UnSat

TL; DR： 在這個答案，我們實現了一個基於clpfd一個非常普遍的做法。使用SWI-Prolog的7.3.16

 
:- 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

樣品查詢：

 
?- 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.

注答案序列的特定順序！最長的列表首先出現，然後是列表稍小......一直到單身列表和空列表。

來源

2016-02-05 20:21:47 repeat

只有4行...！（子集/ 2的+ gusbro解）。非常優雅和簡潔...！謝謝。 – UnSat

@ user114754。 Thx欣賞！在一些Prolog系統中，'list_subseq/2'作爲一個庫謂詞是開箱即用的：例如，[SICStus Prolog]（https://sicstus.sics.se/）提供['subseq0/2 ']（https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002dlists.html）。 – repeat

「我想知道我是否正確使用動態數據庫，謝謝！」 - 這個問題。 –

Earlier，我們根據clpfd提出了一個簡明解決方案。現在我們的目標是通用性和效率！

 
:- 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).

使用SICStus的Prolog 4.3.2（漂亮的印刷的答案序列）樣品查詢：

?- 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.

注意的list_long_nondecreasing_subseq/2 答案序列可以是很多比給出的一個較小的通過list_nondecreasing_subseq/2。

上面所列內容[0,8,4,12,2,10,6,14,1,9]已經獲得兩家list_nondecreasing_subseq/2和 list_long_nondecreasing_subseq/2長度 —所有的「返回」的非降序列。

相應答案序列的大小，然而，差異很大：（65 + 9 = 74 ）與（4 + 9 = ）。

來源

2016-02-07 22:03:01 repeat

不斷變好！在這個答案我們目前list_long_nondecreasing_subseq__NEW/2，list_long_nondecreasing_subseq/2 —代替的直接替換。

讓我們切入討論並定義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).

那麼...它仍然像以前一樣工作嗎？讓我們運行一些測試，並比較了答案序列：

 
| ?- 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

所有答案序列爲正是一模一樣！ ...那麼，運行時間呢？

讓我們使用SICStus Prolog 4.3.2運行一些更多的查詢，然後漂亮地打印答案！

 
?- 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.

當然，在這個答案顯示的baroque方法根本無法與「嚴肅」 suitable algorithms確定lis —的是，越來越10X增速總是感覺很好:)

來源

2016-02-08 06:21:27 repeat

如何在Prolog中使用動態數據庫？

回答

相關問題