Minimum element of a pair in a list in prolog is slow

Question

I have this code in GNU Prolog, and I don't know why it is slow with a 50-element paired list:

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (A,B) ) :-
    pairwise_min( T, (_,B1) ),
    B1 > B,
    !.
pairwise_min( [(_,B)|T], (A1,B1) ) :-
    pairwise_min( T, (A1,B1) ),
    B1 =< B,
    !.

The following query takes 10 seconds:

?- pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).

What can I do to quickly find this minimum?

Answer 1

You can quickly see the problem when you trace:

?- trace, pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).
   Call: (7) pairwise_min([ (25, 25), (24, 24), (23, 23), (22, 22), (21, 21), (20, 20), (19, 19), (..., ...)|...], _G737) ? 
   ... snip ...
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1065, _G1066)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ? 
   Exit: (30) pairwise_min([ (2, 2), (1, 1)], (1, 1)) ? 
   Call: (30) 1>3 ? 
   Fail: (30) 1>3 ? 
   Redo: (29) pairwise_min([ (3, 3), (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1062, _G1063)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ? 

Basically, the problem is that you wind up calling pairwise_min(T, ...) in both cases, even though it won't be different in the second case. The pairwise minimum of the tail is the pairwise minimum of the tail, regardless of how the current element checks out against it.

A good solution would be to eliminate the second rule by using an explicit conditional, something like this:

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (RA,RB) ) :-
    pairwise_min(T, (A1,B1)), !,
    (B1 > B -> (RA = A,  RB = B)
             ; (RA = A1, RB = B1)).

A significant impediment to readability for me is that I don't really grok what kind of ordering you're trying to achieve with your pairwise minimum. But it would be a good idea for the future to extract that into its own predicate anyway. I have zero confidence I've gotten your minimum right; is it not true that @</2 will do what you want? If that is the case, you can do this with a very tight, tail-recursive fold:

minimum([X|Xs], Min) :- minimum(Xs, X, Min).
minimum([], Min, Min).
minimum([X|Xs], MinSoFar, Min) :-
    (X @< MinSoFar -> minimum(Xs,        X, Min)
                    ; minimum(Xs, MinSoFar, Min)).

If that isn't the case, you can write your own predicate min_pair/2 that compares two pairs, and use that instead of @</2 and gain the benefit. Or call it from the revised pairwise_min/2 above and see the benefit of tail call optimization.

I think you'll have some trouble improving on the performance of this version.

Answer 2

a very simple definition, not optimized but fairly fast

pairwise_min(L, (A,B)) :-
    select((A,B), L, R),
    \+ ( member((A1,B1), R), B1 < B ).

anyway, studying the performance of your code will be a very good way to understand Prolog' execution model

Answer 3

In a sense you were lucky to find the right query. Imagine, you would have chosen an ascending list. In that case, you would have experienced a much faster program for the moment. But on demo-day a descending list would have ruined your show.

To understand what is actually happening, it is often very useful to look only at a very tiny fragment of your program. And since your cuts are essentially green cuts, we may do so, even in their presence. I will add false goals into your program. And don't expect this fragment to have any meaning at all. It has no longer any. However, it shows us the search space Prolog has to explore:

pairwise_min( [X], X ) :- false, !.
pairwise_min( [(A,B)|T], (A,B) ) :-
    pairwise_min( T, (_,B1) ), false
    B1 > B,
    !.
pairwise_min( [(_,B)|T], (A1,B1) ) :-
    pairwise_min( T, (A1,B1) ), false
    B1 =< B,
    !.

The outcome is now independent of the concrete values (provided the second argument is uninstantiated). We now get two choices per element of the list. With a list of length n, we have 2ⁿ choices. So that is the reason for this overhead. To remove it, you have to change something in the visible part. Ideally, you are adding some comparisons prior to the recursion.