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

Question

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

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异常(exception)，收效甚微。
问题是，在深度递归子句中经常被调用。有没有更好的方法来做到这一点？
编辑
当一个或两个列表为空时，该子句需要停止。
编辑 2
值得一提的是，以下所有答案的测试都是使用 64 位序言完成的，使用 --stack-limit=32g选项，因为我的代码没有得到很好的优化， fit子句是较大过程的一小部分，但它是我的代码的主要问题。
编辑 3
CapelliC 代码使用较少的资源工作。
使用 library(reif) 的假代码v2 工作得更快。
见 Complexity of counting matching elements in two sequences using library(aggregate) 更多建议的解决方案。

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