Производительность пролога и тип рекурсии

Я играл с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)

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

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

Ответы на вопрос(3)

Действительно хороший вопрос, +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).

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

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

Посмотрим сейчасразворачивание первый вариант и частичная оценка его для списка из 3 элементов. Начнем с простой цели:

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

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

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

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

 mat07 нояб. 2015 г., 11:57
Это правда, но как мы узнаем, куда на самом деле стремится время? Это головное объединение или издержки вызова предиката?
 mat07 нояб. 2015 г., 13:20
Возможно из-за медленной реализации мета-вызова?
 false07 нояб. 2015 г., 12:13
Количество выводов достаточно надежноеАннотация измерения. Анализировать конкретные измерения практически невозможно. И на самом деле не стоит. В конкретном случае разница междуfindall(L, Goal, Ls) а также(Goal, false) это фактор 5 ...
 false07 нояб. 2015 г., 11:15
... потому что он должен делать меньше унификаций при возврате ". Это не точно. Причина, по которой версия 2 работает медленнее, заключается в количестве обращений кpermute/2, Для каждого ответаselect это позвонитpermute/2 тогда как версия 1 вызываетpermute/2 только один раз до звонкаselect/3
 false07 нояб. 2015 г., 13:25
findall/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, когда выпросто проверка. Глядя на код этоЛегко понять почему: первый должен переставить весь хвост списка, а второй - попытаться выбрать один элемент. В этом случае может быть легко указать на генерирующий случай и сказать это:более желанным. Это определение является просто одним из компромиссов, которые нужно отслеживать при работе с Прологом. Это'очень трудно делать предикаты, которые являются всем для всех и всегда велики; Вы должны решить, какие "привилегированные пути " а которые нет.

Я смутно помню, кто-то недавно показал пример добавления списковво время возвращения и как ты мог взять то, что нет или не долженне быть хвостом рекурсивным и заставить его работать благодаря объединению, но я неСсылка не нужна. Надеюсь, кто бы ни поднял это в прошлый раз (Уилл?), Он появится и поделится этим.

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

 CapelliC10 июн. 2013 г., 09:38
отдокументы:is_permutation(Xs, Ys) :- msort(Xs, Sorted), msort(Ys, Sorted).
 lurker10 июн. 2013 г., 13:30
Спасибо Даниэль. Я взял ответ наsums как хороший совет, и это соответствовало всему остальному, что ямы готовы (эта рекурсия хвоста предпочтительна). Затем я столкнулся с моим несколько слишком тривиальным примером, и я искал на нем мысли относительно распространенного совета, что хвостовая рекурсия лучше всего. Ваше объяснение весьма полезно.
 repeat19 окт. 2015 г., 14:05
s (X): Спасибо за исследование других случаевperm(Xs,Ys) чемground(Xs),var(Ys)! То, как я вижу вещи сейчас "способ 2 " это путь И тем более, если присутствуют дополнительные ограничения.

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

В ожидании того, чтобы кто-то опубликовал анализ времени / пространства, единственное предостережение, которое я могу предложить, - это метод 1 & 2 неt завершается, когда первый аргумент свободен, в то время как метод 3 делает.

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

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

больше редактировать: Я забыл ранее указать, что перестановка / 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]

редактировать: ЯВыложили комментарий на SWI-Прологстраница документа об этой теме.

 user181245710 июн. 2013 г., 12:08
Глядя на ссылку, которую вы предоставили, кажется, что это не такпросто совет, но в спецификации. В любом случае, я предполагаю, что порядок важен только потому, что все библиотеки, которые я проверял, придерживаются его (и так же как учебники по математике). Есть ли смысл в заказе или это просто соглашение?
 CapelliC10 июн. 2013 г., 11:56
@Boris: Тыверно,C ++ например, вызвать функцию next_permutation и просто сообщить о лексикографическом порядке в документации. Но фактор ускорения 3 (или более) может быть значительным.
 CapelliC10 июн. 2013 г., 12:21
Я думаю этоПросто обычное. Наивное использование перестановки / 2, как решение 'зебры, как» головоломки, конечно, нене волнует.
 lurker10 июн. 2013 г., 13:40
Я сделал еще один маленький тест в GNU Prolog и обнаружил, что работает встроенныйpermutation( X, [1,2,3] ) вызвал переполнение стека, когда я нажал; после того как было представлено первое решение. К сожалению. ;) SWI-Пролог сработал, но дает лексикографический порядок только в том случае, если экземпляр аргумента является первым.
 user181245710 июн. 2013 г., 11:44
На самом деле я не могу вспомнить, чтобы когда-либо использовались (все) перестановки без необходимости и не полагаться на лексикографический порядок. Перестановки традиционно перечисляются в лексикографическом порядке, и все библиотеки, предоставляющие перестановки, создают их в этом порядке. В этом смысле было бы немного странно и очень вводить в заблуждение менять порядок.

Ваш ответ на вопрос