1

Here are two similar algorithms for last/2. Why does last_element0/2 perform better than last_element1/2? With the extra code last_element0/2 performs almost as well as last/2, but it is not as elegant as last_element1/2. Also, last_element1/2 throws a stack overflow error for lists that are too big, but last_element0/2 doesn't, why? Finally, last_element1/2 has an extra choice point so a cut is necessary, not sure this is a huge concern here.

last_element0(X,Last) :-
    last_element0(X,_,Last).

last_element0([X|Xs],_,Last) :-
    last_element0(Xs,X,Last).
last_element0([],Last,Last).

last_element1([_|Xs],Last) :-
    last_element1(Xs,Last),
    !.
last_element1([Last],Last).

Here are the test results:

last_element0/2

1 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last_element0(Cs,X)).
% 1,000,003 inferences, 0.031 CPU in 0.023 seconds (136% CPU, 32000096 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.

last_element1/2

2 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last_element1(Cs,X)).
% 1,000,001 inferences, 0.250 CPU in 0.452 seconds (55% CPU, 4000004 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.

last/2

3 ?- length(Cs, 1000000), maplist(=(c), Cs),time(last(Cs,X)).
% 1,000,001 inferences, 0.031 CPU in 0.022 seconds (142% CPU, 32000032 Lips)
Cs = [c, c, c, c, c, c, c, c, c|...],
X = c.
repeat
  • 18,496
  • 4
  • 54
  • 166
lefunction
  • 301
  • 2
  • 16
  • this was answered [here](http://stackoverflow.com/questions/11734986/implementing-last-in-prolog) – lefunction Jun 25 '15 at 03:41
  • Hm, didn't see your comment. You should probably delete your question. I will leave my answer for now, if you delete the question it will go with it. –  Jun 25 '15 at 07:01
  • @Boris: it's not a duplicate, but certainly related. – false Jun 25 '15 at 13:12
  • @false Well, it pops up on the side as "Linked" so good enough I guess? –  Jun 25 '15 at 13:14
  • @Boris: It is linked because there are links (by lefunction and you) to this and the other article. It has nothing to do with the content. – false Jun 25 '15 at 13:20

1 Answers1

2

Your last_element0/2 is almost the same as the library implementation of last/2, at least for SWI-Prolog. It is (much) faster because, due to the underlying implementation, the two clauses of last_element0/3 (the helper predicate) are recognized as mutually exclusive, so no choice points are created, and no choice points need to be discarded.

However, look at this:

?- last_element0(Xs, X).
ERROR: Out of local stack

?- last_element1(Xs, X).
ERROR: Out of local stack

?- last(Xs, X).
Xs = [X] ;
Xs = [_G1570, X] ;
Xs = [_G1570, _G1573, X] ;
% ... and so on

The culprit: the order of the clauses for the helper predicate!

By the way, there are other ways of defining last/2:

last_reverse(List, Last) :- reverse(List, [Last|_]).
last_append(List, Last) :- append(_, [Last], List).

(Shameless self-promotion) See this question and both answers for some more discussion about termination behavior, choice points, and efficiency (there are more links to follow there, too). I asked that question after answering a question on programmers.stackexchange and in the process realizing that I know nothing.

Community
  • 1
  • 1