Sliding window method for pattern recognition in SWI-Prolog

huangapple
go评论64阅读模式
英文:

Sliding window method for pattern recognition in SWI-Prolog

问题

我想要找到在SWI-Prolog中以算法方式计算某些模式出现次数的最流畅和高效的方法。

目前，我的解决方案使用DCG，如下所示：

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,
    findall(1, (
        between(0, MaxIndex, Index),
        sublist(List, Index, PatternLength, PatternList)
    ), Counts),
    sum_list(Counts, Count).

结果如下：

1 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
Count = 3.

2 ?- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 1.

3 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 2.

我对这个结果感到满意，但我认为这不是计算效率最高的方法，希望能够获得一些帮助，使其计算速度更快。我认为使用append和findall在计算上是昂贵的，但无法想出如何在没有它们的情况下完成相同的任务...

这里显示的DCG只是一个示例，但我必须计算列表中模式的出现次数并为它们评分。这是在实现五子棋的人工智能时的上下文，使用Alpha-Beta剪枝。由于棋盘经常被评估，算法复杂性对于减少AI采取行动所需的时间非常重要。

我已经尝试了上面显示的代码的多个变种，但它们都使用了findall谓词，我找到的最好的减少计算时间的解决方案是实施早期失败。

英文:

I would like to find the most eloquent and efficient method, algorithmically speaking, to count occurrences of some patterns in SWI-Prolog.

For now, my solution uses DCG and looks like this:

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,
    findall(1, (
        between(0, MaxIndex, Index),
        sublist(List, Index, PatternLength, PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, Index, Length, Sublist) :-
    length(Sublist, Length),
    append(Prefix, Rest, List),
    length(Prefix, Index),
    append(Sublist, _, Rest).

rep(S, L) --> [], {L is 0} | [S], {L is 1} | [S], { L_1 is L - 1 }, rep(S, L_1), !.
open_rep(S, L) --> [v], rep(S, L), [v], !.

The result is this:

1 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
Count = 3.

2 ?- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 1.

3 ?- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
Count = 2.

I am satisfied with this result, but I don't think this is the most efficient method to achieve it and would like some help making it faster to compute. I think that using append and findall is computationally expensive, but can't figure how to do the same without them...

The DCG shown here is just an example, but I have to count the occurrences of patterns in a list and give them a score. This is in the context of implementing an AI for Gomoku using Alpha-Beta Pruning. Since the board is evaluated frequently, algorithmic complexity matters in order to reduce the time it takes for the AI to take an action.

I have tried multiple variations of the code shown above, but they all use the findall predicate and the best solution I have found to reduce the compute time is to implement early fails.

答案1

得分: 3

以下是您要翻译的内容：

"Something in your question is missing, can't tell what. I am also surprised by the answers.

Not sure if you must use lists or if you can use atoms or strings. Atoms and strings have sub_atom/5 and sub_string/5, resp, which can be used for searching. Like this:

?- sub_atom(vnvnvvvvvvnvv, Before, Len, After, vnv).
Before = 0, Len = 3, After = 10 ;
Before = 2, Len = 3, After = 8 ;
Before = 9, Len = 3, After = 1 ;
false.

The same but with strings works with sub_string/5.

And if you are already using SWI-Prolog, you can use library(aggregate) to count solutions:

?- aggregate_all(count, sub_atom(vnvnvvvvvvnvv, _,_,_, vnv), N).
N = 3.

?- aggregate_all(count, sub_atom(vnvnvvvvvvnnnvv, _,_,_, vnv), N).
N = 2.

So far you don't need to program anything. If you must use lists, the two appends are enough:

?- aggregate_all(
      count,
      ( append(_, Back, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v]),
        append([v,n,n,n,v], _, Back)
      ),
      N).
N = 1.

And remember that you also have the regular expression library library(pcre). If you use the example code from the docs:

:- use_module(library(pcre)).

re_match_count(Regex, String, N) :-
    re_foldl(inc, Regex, String, 0, N, []).
inc(_, V0, V) :- V is V0 + 1.

you can also count, using either atoms or strings:

?- re_match_count('vn{1}(?=v)', vnvnvvvvvvnvv, N).
N = 3.

?- re_match_count("vn{3}(?=v)", "vnvnvvvvvvnnnvv", N).
N = 1.

(Note: these regexes use "zero-width positive lookahead". They were initially borked by me, and fixed after Will Ness noticed the mistake).

In this example all information about the match itself is discarded and only the number of matches is counted. You could do anything you feel using the first argument to re_foldl/6.

Note: you need to measure what works fastest for you. If there is a way to read and keep the strings as Prolog strings, and use library(pcre), that might be faster than other methods.

Finally, if you want to use a DCG for the pattern recognition, you can use the following code to "match anywhere":

match_dcg(G) --> string(_), call(G), remainder(_).

This now completely ignores what comes before and after, or the position of the match within the list. You can use it like this, with your own open_rep//2:

?- aggregate_all(
       count,
       phrase(match_dcg(open_rep(n, 1)), [v,n,v,n,v,v,v,v,v,v,n,v,v]),
       N).
N = 3.

The difference between match_dcg//1 as defined here and the match//1 in the example in the docs to phrase_from_file/2 is that match_dcg//1 takes another DCG as an argument, not a pattern (substring)."

英文:

Something in your question is missing, can't tell what. I am also surprised by the answers.

Not sure if you must use lists or if you can use atoms or strings. Atoms and strings have sub_atom/5 and sub_string/5, resp, which can be used for searching. Like this:

?- sub_atom(vnvnvvvvvvnvv, Before, Len, After, vnv).
Before = 0, Len = 3, After = 10 ;
Before = 2, Len = 3, After = 8 ;
Before = 9, Len = 3, After = 1 ;
false.

The same but with strings works with sub_string/5.

And if you are already using SWI-Prolog, you can use library(aggregate) to count solutions:

?- aggregate_all(count, sub_atom(vnvnvvvvvvnvv, _,_,_, vnv), N).
N = 3.

?- aggregate_all(count, sub_atom(vnvnvvvvvvnnnvv, _,_,_, vnv), N).
N = 2.

So far you don't need to program anything. If you must use lists, the two appends are enough:

?- aggregate_all(
      count,
      ( append(_, Back, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v]),
        append([v,n,n,n,v], _, Back)
      ),
      N).
N = 1.

And remember that you also have the regular expression library library(pcre). If you use the example code from the docs:

:- use_module(library(pcre)).

re_match_count(Regex, String, N) :-
    re_foldl(inc, Regex, String, 0, N, []).
inc(_, V0, V) :- V is V0 + 1.

you can also count, using either atoms or strings:

?- re_match_count('vn{1}(?=v)', vnvnvvvvvvnvv, N).
N = 3.

?- re_match_count("vn{3}(?=v)", "vnvnvvvvvvnnnvv", N).
N = 1.

(Note: these regexes use "zero-width positive lookahead". They were initially borked by me, and fixed after Will Ness noticed the mistake).

In this example all information about the match itself is discarded and only the number of matches is counted. You could do anything you feel using the first argument to re_foldl/6.

Note: you need to measure what works fastest for you. If there is a way to read and keep the strings as Prolog strings, and use library(pcre), that might be faster than other methods.

Finally, if you want to use a DCG for the pattern recognition, you can use the following code to "match anywhere":

match_dcg(G) --> string(_), call(G), remainder(_).

This now completely ignores what comes before and after, or the position of the match within the list. You can use it like this, with your own open_rep//2:

?- aggregate_all(
       count,
       phrase(match_dcg(open_rep(n, 1)), [v,n,v,n,v,v,v,v,v,v,n,v,v]),
       N).
N = 3.

The difference between match_dcg//1 as defined here and the match//1 in the example in the docs to phrase_from_file/2 is that match_dcg//1 takes another DCG as an argument, not a pattern (substring).

答案2

得分: 3

根据经验性增长分析，您可以看到，您的代码表现出二次行为，而各种答案的代码变体是线性的。

这是因为您坚持要求中缀从已知的索引开始，逐个递增索引。然后，中缀字符串是由一对append操作找到的，每次都从输入列表的开头重新开始。

因此，这个工作以经典的三角形方式完成（如链接中所示），导致了问题的二次行为。

但两个append操作将自行完成此操作，而且还会从上次处理的索引重新开始，不会从索引0开始。它们将直接从索引i继续，因此具有线性执行时间。

要使用您的代码实现这一点，您只需删除与索引操作相关的每一部分，它将神奇地变成答案中所看到的高效变体。

这将得到以下代码：

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    findall(1, (
        sublist(List, PatternList)
    ), Counts),
    sum_list(Counts, Count).

如预期的那样，它是线性的。

现在，您可以将findall和sum_list的调用合并到一个谓词count中，就像在答案中所看到的那样。不过，请确保测试两种方法，使用实际数据进行测试。使用库函数可能仍然更快。因此，还可以尝试TA_intern的答案中的aggregate_all方法。

要求和控制更少，实现更多！或者，

过早的<s>优化</s>实现是一切恶的根源。

英文:

Applying the empirical orders of growth analysis, you can see that your code exhibits quadratic behavior while the various answers' code variants are linear.

Why is that?

It is because you insist on forcing the infix to start at a known index, increasing the index one by one. Then the infix string is found by the pair of appends, each time starting afresh from the input list's very beginning.

Thus the work is done in the classic triangular fashion (as is also illustrated in the linked entry), causing the problematic quadratic behavior.

But the two appends will do this on their own, moreover restarting at the last processed index and not from the index 0. Instead of starting from 0 and going along the input list to the given index i they will just continue from i directly; thus having the linear execution time.

To achieve this with your code, you just need to delete from it every bit dealing with the index manipulations, and it will magically turn into the efficient variant of what you see in the answers.

This gets you

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    /*length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,*/
    findall(1, (
        /*between(0, MaxIndex, Index),*/
        sublist(List, /*Index, PatternLength,*/ PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, /*Index, Length,*/ Sublist) :-
    /*length(Sublist, Length),*/
    append(_Prefix, Rest, List),
    /*length(Prefix, Index),*/
    append(Sublist, _, Rest).

which checks out linear, as expected:

167 ?- random_list(1000,L),time(count_occurrences(open_rep(n,3),L,C)).
% 3,094 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
L = [v, n, n, v, v, v, n, n, n|...],
C = 24.

168 ?- random_list(10000,L),time(count_occurrences(open_rep(n,3),L,C)).
% 30,514 inferences, 0.000 CPU in 0.003 seconds (0% CPU, Infinite Lips)
L = [n, n, v, v, v, v, v, n, v|...],
C = 280.

Tested using random_list/2 from another answer here.

Now you can fuse your calls to findall and sum_list into one predicate count as seen in that answer. Be sure to test both approaches though, with your actual data. Using library functions might still be faster. So, do also try the aggregate_all approach from TA_intern's answer.

Demand and control less, achieve more! Or,

Premature <s>optimization</s> implementation is the root of all evil.

答案3

得分: 2

I think that, even using the predicate append/3, you can still have an efficient solution (at least that's what can be observed with swi-prolog).

count(Pattern, List, Count) :-
    phrase(Pattern, Sublist),
    count(List, Sublist, 0, Count).

count([], _, Count, Count).
count([X|Xs], Sublist, Count0, Count) :-
    (   append(Sublist, _, [X|Xs])
    ->   Count1 is Count0 + 1
    ;    Count1 is Count0 ),
    count(Xs, Sublist, Count1, Count).

% To compare the two versions with large lists

random_list(0, []) :- !.
random_list(N, [X|Xs]) :-
    random_member(X, [n,v]),
    M is N-1,
    random_list(M, Xs).

Comparison of count/3 and count_occurrences/3, using swi-prolog:

?- random_list(1000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 4,648 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 3,003,226 inferences, 1.578 CPU in 1.683 seconds (94% CPU, 1903034 Lips)
L = [v, n, v, v, n, n, n, n, v|...],
C1 = C2, C2 = 116.

?- random_list(2000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 9,288 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 12,006,431 inferences, 11.812 CPU in 12.421 seconds (95% CPU, 1016417 Lips)
L = [n, n, v, v, n, n, n, v, n|...],
C1 = C2, C2 = 229.

?- random_list(1000000,L), time(count(open_rep(n,3),L,C1)).
% 4,905,979 inferences, 0.109 CPU in 0.146 seconds (75% CPU, 44854665 Lips)
L = [n, v, v, v, n, v, n, n, n|...],
C1 = 31246.

?- L = [v,n,v,n,v,v,v,v,v,v,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 77 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 571 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 3.

?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,3),L,C1)), time(count_occurrences(open_rep(n,3),L,C2)).
% 99 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 641 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 1.

?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 86 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 739 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 2.
英文:

I think that, even using the predicate append/3, you can still have an efficient solution (at least that's what can be observed with swi-prolog).

count(Pattern, List, Count) :-
phrase(Pattern, Sublist),
count(List, Sublist, 0, Count).
count([], _, Count, Count).
count([X|Xs], Sublist, Count0, Count) :-
(   append(Sublist, _, [X|Xs])
-&gt;   Count1 is Count0 + 1
;    Count1 is Count0 ),
count(Xs, Sublist, Count1, Count).
% To compare the two versions with large lists
random_list(0, []) :- !.
random_list(N, [X|Xs]) :- 
random_member(X, [n,v]), 
M is N-1, 
random_list(M, Xs).

Comparison of count/3 and count_occurrences/3, using swi-prolog:

?- random_list(1000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 4,648 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 3,003,226 inferences, 1.578 CPU in 1.683 seconds (94% CPU, 1903034 Lips)
L = [v, n, v, v, n, n, n, n, v|...],
C1 = C2, C2 = 116.
?- random_list(2000,L), time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 9,288 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 12,006,431 inferences, 11.812 CPU in 12.421 seconds (95% CPU, 1016417 Lips)
L = [n, n, v, v, n, n, n, v, n|...],
C1 = C2, C2 = 229.
?- random_list(1000000,L), time(count(open_rep(n,3),L,C1)).
% 4,905,979 inferences, 0.109 CPU in 0.146 seconds (75% CPU, 44854665 Lips)
L = [n, v, v, v, n, v, n, n, n|...],
C1 = 31246.
?- L = [v,n,v,n,v,v,v,v,v,v,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 77 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 571 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 3.
?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,3),L,C1)), time(count_occurrences(open_rep(n,3),L,C2)).
% 99 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 641 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 1.
?- L = [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], time(count(open_rep(n,1),L,C1)), time(count_occurrences(open_rep(n,1),L,C2)).
% 86 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
% 739 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
L = [v, n, v, n, v, v, v, v, v|...],
C1 = C2, C2 = 2.

答案4

得分: 1

在我看来，你的方法过于特定，从可重用性的角度来看，它将不够优化。
SWI-Prolog提供了一个库谓词，用于执行RLE（Run Length Encoding），我从这个有趣的话题中发现了这一点，值得一试：在这里，我将发布一个模块，其中我复制了你的代码，以及一个使用clumped/2的替代方法：

/*  File:    x_so_sliding_window.pl
    Author:  Carlo
    Created: Mar  4 2023
    Purpose: https://stackoverflow.com/q/75630809/874024
*/

:- module(x_so_sliding_window,
          [count_occurrences/3
          ,open_rep//2
          ,count_by_clumped/3
          ]).

count_occurrences(Pattern, List, Count) :-
    phrase(Pattern, PatternList),
    length(PatternList, PatternLength),
    length(List, ListLength),
    MaxIndex is ListLength - PatternLength,
    findall(1, (
        between(0, MaxIndex, Index),
        sublist(List, Index, PatternLength, PatternList)
    ), Counts),
    sum_list(Counts, Count).

sublist(List, Index, Length, Sublist) :-
    length(Sublist, Length),
    append(Prefix, Rest, List),
    length(Prefix, Index),
    append(Sublist, _, Rest).

rep(S, L) --> [], {L is 0} | [S], {L is 1} | [S], { L_1 is L - 1 }, rep(S, L_1), !.
open_rep(S, L) --> [v], rep(S, L), [v], !.

count_by_clumped(Pattern, List, Count) :-
    clumped(List, R),
    aggregate_all(count, member(Pattern, R), Count).

然后，我在x_so_sliding_window.plt文件中有以下代码：

:- [x_so_sliding_window].

t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).

c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
c(Count) :- count_by_clumped(n-3, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).

这在第一次查看时显示了t/1和c/1调用之间的等价关系：

?- t(Count).
Count = 3 ;
Count = 1 ;
Count = 2.

?- c(Count).
Count = 3 ;
Count = 1 ;
Count = 2.

最后，在REPL中直接编码的“基准测试”如下：

?- time((between(1,1000,_),(t(_),fail))).
% 1,953,001 inferences, 0.234 CPU in 0.234 seconds (100% CPU, 8332804 Lips)
false.
?- time((between(1,1000,_),(c(_),fail))).
% 123,001 inferences, 0.000 CPU in 0.014 seconds (0% CPU, Infinite Lips)
false.
英文:

IMO your approach is too much specific, and it will be sub optimal from the (re)usability viewpoint.
SWI-Prolog offers a library predicate that performs RLE (run length encoding), as I discovered from this interesting topic, and is worth to try: here I'll post a module, where I copied your code, and an alternative that uses clumped/2:

/*  File:    x_so_sliding_window.pl
Author:  Carlo
Created: Mar  4 2023
Purpose: https://stackoverflow.com/q/75630809/874024
*/
:- module(x_so_sliding_window,
[count_occurrences/3
,open_rep//2
,count_by_clumped/3
]).
count_occurrences(Pattern, List, Count) :-
phrase(Pattern, PatternList),
length(PatternList, PatternLength),
length(List, ListLength),
MaxIndex is ListLength - PatternLength,
findall(1, (
between(0, MaxIndex, Index),
sublist(List, Index, PatternLength, PatternList)
), Counts),
sum_list(Counts, Count).
sublist(List, Index, Length, Sublist) :-
length(Sublist, Length),
append(Prefix, Rest, List),
length(Prefix, Index),
append(Sublist, _, Rest).
rep(S, L) --&gt; [], {L is 0} | [S], {L is 1} | [S], { L_1 is L - 1 }, rep(S, L_1), !.
open_rep(S, L) --&gt; [v], rep(S, L), [v], !.
count_by_clumped(Pattern,List,Count) :-
clumped(List, R),
aggregate_all(count, member(Pattern,R), Count).

then I had this code in x_so_sliding_window.plt

:- [x_so_sliding_window].
t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 3), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
t(Count) :- count_occurrences(open_rep(n, 1), [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,v,v], Count).
c(Count) :- count_by_clumped(n-3, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).
c(Count) :- count_by_clumped(n-1, [v,n,v,n,v,v,v,v,v,v,n,n,n,v,v], Count).

that shows at first glance the equivalence between t/1 and c/1 calls:

?- t(Count).
Count = 3 ;
Count = 1 ;
Count = 2.
?- c(Count).
Count = 3 ;
Count = 1 ;
Count = 2.

and, at last, the 'benchmark' directly coded in the REPL:

?- time((between(1,1000,_),(t(_),fail))).
% 1,953,001 inferences, 0.234 CPU in 0.234 seconds (100% CPU, 8332804 Lips)
false.
?- time((between(1,1000,_),(c(_),fail))).
% 123,001 inferences, 0.000 CPU in 0.014 seconds (0% CPU, Infinite Lips)
false.

答案5

得分: 1

这是一个更好的子列表方法：

sublist1([H|T], Index, Length, Sublist) :-
    sublist1_start_(T, H, 1, Index, Length, Sublist).

% P = previous
sublist1_start_(L, P, Ind, Index, Length, Sublist) :-
    sublist1_loop_(L, P, Ind, Index, 1, Length, Sublist).
sublist1_start_([H|T], _, Ind, Index, Length, Sublist) :-
    Ind1 is Ind + 1,
    % 前往下一个元素
    sublist1_start_(T, H, Ind1, Index, Length, Sublist).

sublist1_loop_(_, H, Ind, Ind, Len, Len, [H]).
sublist1_loop_([H|T], P, Ind, Index, Len, Length, [P|Sublist]) :-
    Len1 is Len + 1,
    sublist1_loop_(T, H, Ind, Index, Len1, Length, Sublist).

在swi-prolog中的结果：

?- sublist1([a,b,c], Ind, Len, Sub).
Ind = Len, Len = 1,
Sub = [a] ;
Ind = 1,
Len = 2,
Sub = [a, b] ;
Ind = 1,
Len = 3,
Sub = [a, b, c] ;
Ind = 2,
Len = 1,
Sub = [b] ;
Ind = Len, Len = 2,
Sub = [b, c] ;
Ind = 3,
Len = 1,
Sub = [c].

如果你希望索引从0开始而不是1，请在第2行将1更改为0。

我已排除空列表。

英文:

Here's a better method for a sublist:

sublist1([H|T], Index, Length, Sublist) :-
    sublist1_start_(T, H, 1, Index, Length, Sublist).

% P = previous
sublist1_start_(L, P, Ind, Index, Length, Sublist) :-
    sublist1_loop_(L, P, Ind, Index, 1, Length, Sublist).
sublist1_start_([H|T], _, Ind, Index, Length, Sublist) :-
    Ind1 is Ind + 1,
    % Go to next element
    sublist1_start_(T, H, Ind1, Index, Length, Sublist).

sublist1_loop_(_, H, Ind, Ind, Len, Len, [H]).
sublist1_loop_([H|T], P, Ind, Index, Len, Length, [P|Sublist]) :-
    Len1 is Len + 1,
    sublist1_loop_(T, H, Ind, Index, Len1, Length, Sublist).

Results in swi-prolog:

?- sublist1([a,b,c], Ind, Len, Sub).
Ind = Len, Len = 1,
Sub = [a] ;
Ind = 1,
Len = 2,
Sub = [a, b] ;
Ind = 1,
Len = 3,
Sub = [a, b, c] ;
Ind = 2,
Len = 1,
Sub = [b] ;
Ind = Len, Len = 2,
Sub = [b, c] ;
Ind = 3,
Len = 1,
Sub = [c].

If you want the indexing to start from 0 rather than 1, then change the 1 to 0 in the 2nd line.

I've excluded empty lists.

huangapple
  • 本文由 发表于 2023年3月4日 02:46:55
  • 转载请务必保留本文链接：https://go.coder-hub.com/75630809.html
  • dcg
  • gomoku
  • pattern-matching
  • prolog
  • sliding-window
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定