如何在不触发 Out of Local Stack 异常的情况下计算两个大字符串的每个字符的巧合？

Question

我需要一个子句来计算两个大字符串之间的 char 巧合但忽略 '_' 巧合。我有这个代码：

fit(GEN1, GEN2, N, N) :-
   length(GEN1, L1),
   length(GEN2, L2),
   0 is L1*L2.

fit([P1|R1], [P2|R2], N, TOTAL) :-
   member(P1, ['_',a,c,t,g]),
   member(P2, ['_',a,c,t,g]),
   append([P1],[P2],T),
   (  member(T,[[a,a],[c,c],[t,t],[g,g]])
   -> X is N+1
   ;  X is N
   ),
   fit(R1,R2,X,TOTAL).

其中 GEN1 和 GEN2 是包含所有字符大字符串的列表。

我尝试增加堆栈限制以避免 Out of Local Stack 异常，但收效甚微。

问题在于，在深度递归子句中经常被调用。有没有更好的方法来做到这一点？

编辑

子句需要在一个或两个列表为空时停止。

编辑 2

值得一提的是，以下所有答案的测试都是使用 64 位序言完成的，带有 --stack-limit=32g 选项，因为我的代码没有得到很好的优化，并且 fit 子句是更大的过程，但这是我的代码的主要问题。

编辑 3

CapelliC 代码使用更少的资源工作。

使用 library(reif) v2 的假代码工作得更快。

有关更多建议的解决方案，请参阅。

Answer 1

似乎没有必要一直坚持 "_actg" 中的字母。一个广义的定义似乎就足够了。使用 library(reif):

fit([], _, N,N).
fit([_|_], [], N,N).
fit([P1|R1], [P2|R2], N,TOTAL) :-
   if_( ( P1 = P2, dif(P1, '_') ), X is N+1, X = N ),
   fit(R1, R2, X,TOTAL).

更新：请确保使用 library(reif) 的 v2。原版没有编译dif/3.

这里是一个只能同时索引一个参数的系统版本：

fit([], _, N,N).
fit([P1|R1], L2, N,TOTAL) :-
    ifit(L2, [P1|R1], N,TOTAL).

ifit([], _, N,N).
ifit([P2|R2], [P1|R1], N,TOTAL) :-
   if_( ( P1 = P2, dif(P1, '_') ), X is N+1, X = N ),
   fit(R1, R2, X,TOTAL).

Answer 2

如果你的 Prolog 有库（aggregate）你可以做

fit(GEN1, GEN2, N) :-
  aggregate_all(count, (nth1(P,GEN1,S),nth1(P,GEN2,S),memberchk(S,[a,c,g,t])), N).

编辑

根据数据的统计，只需交换最后两个调用即可获得明显的改进，即...(nth1(P,GEN1,S),memberchk(S,[a,c,g,t]),nth1(P,GEN2,S))...

编辑

当然，紧密循环比双索引扫描更好。为了性能，我会这样写

fit_cc(GEN1, GEN2, N) :-
  fit_cc(GEN1, GEN2, 0, N).

fit_cc([X|GEN1], [Y|GEN2], C, N) :-
  (  X\='_' /*memberchk(X, [a,c,g,t])*/, X=Y
  -> D is C+1 ; D=C
  ),
  fit_cc(GEN1, GEN2, D, N).
fit_cc(_, _, N, N).

但是 library(reif) v2 所允许的通用性和正确性，如@false 的回答和评论所示，似乎非常值得（相当小的）开销。

Answer 3

如果你总是用两个已经完全实例化的第一个参数调用你的谓词，那么你将它用作一个函数，而不是一个关系——你似乎确实这样做了——我怀疑只是添加 !, 在最后一行代码的开头应该足以消除堆栈溢出。

为了做得更好一点，我们将使用 memberchk 而不是 member 并注意 append([A],[B],C) 与 C = [A,B] 完全相同；所以经过一些重组之后，我们最终得到了类似

的结果

fit( [], [], N, N).

fit( [P1|R1], [P2|R2], N, TOTAL) :-
   memberchk( P1, [a,c,t,g]),
   (  P2 == P1
   -> X is N+1
   ;  X is N
   ),
   %%  !,    %% might need the cut
   fit( R1, R2, X, TOTAL).

我们甚至可能不需要那个削减，因为 memberchk 已经是确定性的了。

（虽然未测试）

如何在不触发 Out of Local Stack 异常的情况下计算两个大字符串的每个字符的巧合？

How to count coincidences on each character of two large strings without triggering the Out of Local Stack exception?

stack-overflow

optimization

performance

prolog