Производительность и рекурсия Prolog

Я играл с permutation в нескольких программах и наткнулся на этот небольшой эксперимент:

Метод перестановок 1:

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

Метод перестановок 2:

permute([], []).
permute(L, [P | P1]) :-
    select(P, L, L1),
    permute(L1, P1).

Метод перестановок 3 (используйте встроенный):

permute(L, P) :- permutation(L, P).

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

time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).

Я получил следующие результаты, которые относительно согласованы между несколькими прогонами:

Способ 1:

% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)

Способ 2:

% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)

Способ 3:

% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)

Таким образом, не-хвостовой рекурсивный метод значительно эффективнее в режиме реального времени.

Является ли конкретный тип рекурсии более эффективным в реальном времени, при прочих равных условиях (я знаю, что не всегда простая предпосылка)? Этот эксперимент говорит мне, что я, возможно, не хочу всегда стремиться к рекурсии хвоста, но сначала мне нужно сначала выполнить анализ производительности, а затем оценить эффективность работы с другими преимуществами, которые имеет хвостовая рекурсия.

Ответ 1

Действительно хороший вопрос, +1!

Хвост (и, в качестве специального случая, рекурсия хвоста) оптимизация применяется только в том случае, если предикат является детерминированным! Здесь не так, поэтому ваш предикат всегда будет требовать локального пространства стека, независимо от того, в каком порядке вы ставите цели. Рекурсивная версия, отличная от хвоста, более эффективна (время) при создании всех решений, потому что она должна делать меньше унификаций при обратном трафике.

РЕДАКТИРОВАТЬ. Я расширяюсь в этом вопросе, так как лучше изучить разницу в производительности более подробно.

Во-первых, для ясности я переименовываю две разные версии, чтобы уточнить, о какой версии я говорю:

Вариант 1: нерегулярный:

permute1([], []).
permute1([X|Rest], L) :-
    permute1(Rest, L1),
    select(X, L, L1).

Вариант 2: хвостохранилище:

permute2([], []).
permute2(L, [P|P1]) :-
    select(P, L, L1),
    permute2(L1, P1).

Заметим еще раз, что хотя вторая версия явно рекурсивна хвостом, оптимизация хвостового вызова (а следовательно, и хвостовая рекурсия) помогает только в том случае, если предикат является детерминированным и, следовательно, не может помочь, когда мы генерируем все перестановки, поскольку точки выбора все еще остаются в этом случае.

Заметим также, что я намеренно сохраняю первоначальное имя имен переменных и основное имя предиката, чтобы не вводить больше вариантов. Лично я предпочитаю соглашение об именах, которое дает понять, какие переменные обозначают списки, добавляя s к их именам, по аналогии с регулярным английским множественным числом. Кроме того, я предпочитаю имена предикатов, которые более четко демонстрируют (по крайней мере предполагаемый и желательный) декларативный, реляционный характер кода и рекомендуют избегать императивных имен по этой причине.

Рассмотрим теперь разворачивание первого варианта и частичную его оценку для списка из трех элементов. Начнем с простой цели:

?- Xs = [A,B,C], permute1(Xs, L).

а затем постепенно разворачивайте его, включив определение permute1/2, делая все явные заголовки. На первой итерации получим:

?- Xs = [A,B,C], Xs1 = [B,C], permute1(Xs1, L1), select(A, L, L1).

Я отмечаю выделение главы жирным шрифтом.

Теперь остается еще одна цель permute1/2. Поэтому мы повторяем процесс, снова добавляя в предикат только применимое правило тела вместо его головы:

?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], permute1(Xs2, L2), select(B, L1, L2), select(A, L, L1).

Еще один проход этого, и получим:

?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], select(C, L2, []), select(B, L1, L2), select(A, L, L1).

Вот как выглядит исходная цель, если мы снова разворачиваем определение permute1/2.

Теперь, как насчет второго варианта? Опять же, мы начинаем с простой цели:

?- Xs = [A,B,C], permute2(Xs, Ys).

Одна итерация разворачивания permute2/2 дает эквивалентную версию:

?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), permute2(L1, P1).

а вторая итерация дает:

?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1),  Ys1 = [P1|P2], select(P1, L1, L2), permute2(L2, P2).

Я оставляю третью и последнюю итерацию как простое упражнение, которое я настоятельно рекомендую вам сделать.

И из этого ясно, чего мы изначально, вероятно, не ожидали: большая разница заключается в главных объединениях, которые первая версия работает детерминистически с самого начала, а вторая версия снова и снова выполняет возвратов.

Этот знаменитый пример прекрасно показывает, что, в отличие от общего ожидания, хвостовая рекурсия может быть довольно медленной, если код не является детерминированным.

Ответ 2

Действительно хороший вопрос.

Ожидая, что кто-то опубликует анализ времени и пространства, единственное предостережение, которое я могу предложить, заключается в том, что метод 1 и 2 не заканчивается, когда первый аргумент свободен, а метод 3 -.

В любом случае, метод 1 кажется намного более эффективным, чем встроенный. Полезно знать.

edit: и учитывая, что реализация библиотеки просто корректирует создание аргументов и вызывает метод 1, я собираюсь обсудить в списке рассылки SWI-Prolog ваш метод 2 как альтернативу (или, вы предпочитаете делать это самостоятельно, позвольте мне знаю).

more edit: Я забыл ранее указать, что перестановка /3 (скажем, метод 2) дает лексикографически упорядоченные решения, а метод 1 - нет. Я думаю, что это может быть сильным преференциальным требованием, но должно быть выражено как опция, учитывая прирост производительности, который позволяет метод 1.

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 3,112,758 inferences, 3,160 CPU in 3,162 seconds (100% CPU, 984974 Lips)
P = [1, 4, 8, 3, 7, 6, 5, 9, 2|...] .

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 10,154,843 inferences, 9,779 CPU in 9,806 seconds (100% CPU, 1038398 Lips)
P = [2, 7, 8, 3, 9, 1, 5, 4, 6|...] .

YAP дает еще больший выигрыш!

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 0.716 CPU in 0.719 seconds ( 99% CPU)
P = [1,4,8,3,7,6,5,9,2,0]

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 8.357 CPU in 8.368 seconds ( 99% CPU)
P = [2,7,8,3,9,1,5,4,6,0]

edit: Я опубликовал комментарий к SWI-Prolog странице doc об этой теме.

Ответ 3

Я подозреваю, что вызвало это расследование обсуждение хвостового рекурсивного sum/2 с использованием аккумулятора против нет. Пример sum/2 очень разрезан и сух; одна версия выполняет арифметику в стеке, другая использует аккумулятор. Однако, как и большинство вещей в реальном мире, общая истина заключается в том, "это зависит". Например, сравните эффективность методов 1 и 2 с использованием полного экземпляра:

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (66% CPU, 857143 Lips)
true ;
% 86,546 inferences, 0.022 CPU in 0.022 seconds (100% CPU, 3974193 Lips)
false.

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 857143 Lips)
true ;
% 47 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 940000 Lips)
false.

Метод 1 бьет метод 2, когда вы генерируете решения (как в ваших тестах), но метод 2 превосходит метод 1, когда вы просто проверяете. Глядя на код, легко понять, почему: первый должен переставить весь хвост списка, а второй - попробовать выбрать один элемент. В этом случае может быть легко указать на генерирующий случай и сказать, что это более желательно. Это определение является просто одним из компромиссов, которые нужно отслеживать при работе с Prolog. Очень сложно сделать предикаты, которые являются вещами для всех людей, и всегда исполнять большие успехи; вы должны решить, какие "привилегированные пути", а какие нет.

Я смутно вспоминаю, что кто-то недавно показал пример добавления списков "во время возвращения" и как вы могли взять что-то, что не является или не должно быть хвостом рекурсивным и заставить его работать благодаря унификации, но я не имеют ссылку. Будем надеяться, что тот, кто приносил это в прошлый раз (Will?), Появится и поделится им.

Отличный вопрос, кстати. Ваш метод исследования действителен, вам просто нужно будет учитывать другие шаблоны создания. Говоря лично, я обычно стараюсь больше беспокоиться о правильности и общности, чем о производительности. Если я сразу увижу, как использовать аккумулятор, я буду, но в противном случае я не буду этого делать до тех пор, пока не столкнутся с реальной потребностью в лучшей производительности. Рекурсия хвоста - всего лишь один из способов повышения производительности; часто есть другие вещи, которые необходимо решать как плохо или хуже.