我需要一个计算两个大字符串之间的字符重合但忽略'_'重合的子句。我有这个代码：
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位prolog完成的，使用--stack-limit=32g选项，因为我的代码没有得到很好的优化，fit子句只是一个更大过程的一小部分，但这是我的代码的主要问题。
编辑3
CapelliC代码使用较少的资源工作。
使用library(reif)v2的错误代码工作得越快。
有关更多建议的解决方案，请参阅使用library(aggregate)计算两个序列中匹配元素的复杂性。
似乎没有必要一直坚持你有来自"_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).
如果您的Prolog有库(聚合(，您可以进行
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).
但是库(reif(v2所允许的通用性和正确性，如@false的回答和注释所示，似乎非常值得(相当小的(开销。
如果你总是用两个已经完全实例化的第一个参数来调用谓词，所以你把它用作函数，而不是关系——看起来你确实这样做了——我怀疑在最后一行代码的开头添加!,就足以消除堆栈溢出。
为了做得更好一点，我们使用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).
并且我们甚至可能不需要该切割，因为CCD_ 18已经是确定性的。
(未经测试(