问题描述
问题是在列表中找到最后一个字符,例如
The question is to find the last but one character in a list, e.g.
?- last_but_one(X, [a,b,c,d]).
X = c.
我的代码是:
last_but_one(X, [X,_]).
last_but_one(X, [_|T]) :- last_but_one(X, T).
他们给出的代码是:
last_but_one(X, [X,_]).
last_but_one(X, [_,Y|Ys]) :- last_but_one(X, [Y|Ys]).
当我学习 Haskell 时,我记得当问题询问某个列表中的第 2、3 或第 n 个字符时,结构与提供的答案相同,所以我知道按照他们的方式编写它'我写了它有一些意义.但我似乎仍然可以通过我编写它的方式得到正确的答案.
When I was studying Haskell, I can recall that when questions asked for the 2nd, 3rd, or nth character in some list, the structure was the same as the answer that's been supplied, so I know writing it the way they've written it has some significance. But I still seem to get correct answers with the way I have written it.
是不是我写错了?做出答案的人写的代码是否更好?如果是,如何?
Is the way I have written it wrong? Is the code that the guys who made the answer wrote better—and if so, how?
推荐答案
您的原始版本更易于阅读.特别是,递归规则读取 - 从右到左读取它
Your original version is much simpler to read. In particular, the recursive rule reads - reading it right-to-left
last_but_one(X, [_|T]) :- last_but_one(X, T).
^^^^^^^^^^
provided X is the lbo-element in T
^^ then, it follows, that (that's an arrow!)
^^^^^^^^^^^^^^^^^^^^^^
X is also the lbo-element of T with one more element
换句话说:如果您在给定列表T
中已经有一个lbo元素,那么您可以构造新列表,其中包含前面也具有相同lbo元素的任何其他元素.
In other words: If you have already an lbo-element in a given list T
, then you can construct new lists with any further elements in front that also have the very same lbo-element.
人们可能会争论哪个版本在效率方面更可取.如果你真的很喜欢,那就去吧:
One might debate which version is preferable as to efficiency. If you are really into that, rather take:
last_but_one_f1(E, Es) :-
Es = [_,_|Xs],
xs_es_lbo(Xs, Es, E).
xs_es_lbo([], [E|_], E).
xs_es_lbo([_|Xs], [_|Es], E) :-
xs_es_lbo(Xs, Es, E).
甚至:
last_but_one_f2(E, [F,G|Es]) :-
es_f_g(Es, F, G, E).
es_f_g([], E, _, E).
es_f_g([G|Es], _, F, E) :-
es_f_g(Es, F, G, E).
永远不要忘记一般测试:
Never forget general testing:
| ?- last_but_one(X, Es).
Es = [X,_A] ? ;
Es = [_A,X,_B] ? ;
Es = [_A,_B,X,_C] ? ;
Es = [_A,_B,_C,X,_D] ? ;
Es = [_A,_B,_C,_D,X,_E] ? ;
Es = [_A,_B,_C,_D,_E,X,_F] ? ...
以下是我的 olde labtop 上的一些基准测试:
And here are some benchmarks on my olde labtop:
SICStus SWI
4.3.2 7.3.20-1
--------------+----------+--------
you 0.850s | 3.616s | 4.25×
they 0.900s | 16.481s | 18.31×
f1 0.160s | 1.625s | 10.16×
f2 0.090s | 1.449s | 16.10×
mat 0.880s | 4.390s | 4.99×
dcg 3.670s | 7.896s | 2.15×
dcgx 1.000s | 7.885s | 7.89×
ap 1.200s | 4.669s | 3.89×
差异很大的原因是 f1
和 f2
都完全确定地运行,没有创建任何选择点.
The reason for the big difference is that both f1
and f2
run purely determinate without any creation of a choicepoint.
使用
bench_last :-
+ ( length(Ls, 10000000),
member(M, [you,they,f1,f2,mat,dcg,dcgx,ap]), write(M), write(' '),
atom_concat(last_but_one_,M,P), + time(call(P,L,Ls))
).
这篇关于列表中的 Prolog 递归,最后一个元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!