list - 如何在Prolog中使用动态数据库？

Question

我编写了以下程序，它计算输入数组的最长非递减子序列。

从列表列表中查找最长列表的子程序取自 stackoverflow ( 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.

我想知道我是否正确使用动态数据库。谢谢!

Answer 1

问题在于，当您遍历列表构建子序列时，您只需要考虑最后一个值小于您手头值的先前子序列。问题在于 Prolog 的第一个参数索引正在执行相等检查，而不是小于检查。所以Prolog 将不得不遍历lns/2 的整个存储区。 ，将第一个参数与一个值统一，以便您可以检查它是否较小，然后回溯以获取下一个。