Минимальный элемент пары в списке в прологе медленный

Вы можете быстро увидеть проблему при трассировке:

?- 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 ? 

По сути, проблема заключается в том, что вы в конечном итоге вызываете pairwise_min(T, ...) в оба случаях, хотя во втором случае это не будет отличаться. Попарный минимум хвоста — это попарный минимум хвоста, независимо от того, как текущий элемент сверяется с ним.

Хорошим решением было бы исключить второе правило, используя явное условное выражение, что-то вроде этого:

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

Существенным препятствием для удобочитаемости для меня является то, что я действительно не понимаю, какой порядок вы пытаетесь достичь с помощью своего попарного минимума. Но в будущем было бы неплохо выделить это в отдельный предикат. У меня нет уверенности, что я правильно понял ваш минимум; не правда ли, что @</2 сделает то, что вы хотите? Если это так, вы можете сделать это с очень плотной хвостовой рекурсией:

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

Если это не так, вы можете написать свой собственный предикат min_pair/2, который сравнивает две пары, и использовать его вместо @</2 и получить преимущество. Или вызовите его из исправленного pairwise_min/2 выше и убедитесь в преимуществах оптимизации хвостового вызова.

Я думаю, у вас возникнут проблемы с улучшением производительности этой версии.

В некотором смысле вам повезло найти правильный запрос. Представьте, вы бы выбрали восходящий список. В этом случае вы бы испытали гораздо более быструю программу на данный момент. Но в демонстрационный день нисходящий список испортил бы ваше шоу.

Чтобы понять, что на самом деле происходит, часто очень полезно взглянуть только на очень маленький фрагмент вашей программы. А поскольку ваши порезы по сути являются зелеными порезами, мы можем сделать это даже в их присутствии. Я добавлю в вашу программу цели false. И не ждите, что этот фрагмент вообще будет иметь какое-то значение. Его уже нет. Однако он показывает нам пространство поиска, которое Prolog должен исследовать:

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,
    !.

Результат теперь не зависит от конкретных значений (при условии, что второй аргумент не конкретизирован). Теперь у нас есть два варианта выбора для каждого элемента списка. В списке длины n у нас есть 2ⁿ вариантов. Так что это причина этих накладных расходов. Чтобы его убрать, надо что-то изменить в видимой части. В идеале вы добавляете несколько сравнений до рекурсии.

очень простое определение, не оптимизированное, но довольно быстрое

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

в любом случае, изучение производительности вашего кода будет очень хорошим способом понять модель исполнения Пролога.