Каковы плюсы и минусы использования ручной итерации списка по сравнению с рекурсией через сбой - PullRequest
8 голосов
/ 17 марта 2012

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

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

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

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

Одна проблема, которую я вижу, состоит в том, что каждый раз, когда вызывается fail, мы теряем способность передавать что-либо обратно в вызывающий предикат, например,если это было methodtwo(SeasonResults), так как мы преднамеренно терпим неудачу предиката.Таким образом, methodtwo потребуется утвердить факты для хранения состояния.

Предположительно (?) Метод 2 будет быстрее, поскольку он не должен выполнять (большой) обработки списка?

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

Но опять же, я читал, что утверждение фактов - это очень «дорогое» дело, поэтому обработка списков может быть подходящим вариантом даже для больших списков?

Есть мысли?Или иногда лучше использовать одно, а не другое, в зависимости от (какой) ситуации?например.для оптимизации памяти используйте метод 2, включая утверждение фактов, а для скорости используйте метод 1?

season(spring).
season(summer).
season(autumn).
season(winter).

 % Season handling
showseason(Season) :-
    atom_length(Season, LenSeason),
    write('Season Length is '), write(LenSeason), nl.

% -------------------------------------------------------------
% Method 1 - Findall facts/iterate through the list and process each
%--------------------------------------------------------------
% Iterate manually through a season list
lenseason([]).
lenseason([Season|MoreSeasons]) :-
    showseason(Season),
    lenseason(MoreSeasons).


% Findall to build a list then iterate until all done
methodone :-
    findall(Season, season(Season), AllSeasons),
    lenseason(AllSeasons),
    write('Done').

% -------------------------------------------------------------
% Method 2 - Use fail to force recursion
%--------------------------------------------------------------
methodtwo :-
    % Get one season and show it
    season(Season),
    showseason(Season),

    % Force prolog to backtrack to find another season
    fail.

% No more seasons, we have finished
methodtwo :-
    write('Done').

Ответы [ 3 ]

10 голосов
/ 20 марта 2012

Давайте посмотрим на ваш пример.Это очень просто, поэтому мы представим, что это более сложно.Тем не менее, кажется, что вы принимаете как должное, что побочные эффекты необходимы.Позвольте мне задать вопрос:

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

?- <b>season(S), atom_length(S,L).</b>
S = spring,
L = 6 ;
S = summer,
L = 6 ;
S = autumn,
L = 6 ;
S = winter,
L = 6.

Нет необходимости в findall/3, нет необходимости в write/1.

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

?- <b>season(S), atom_length(S,L), dif(L,6).</b>
false.

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

Это мой самый первый ответ на ваш вопрос:

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

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

  • Если ваши программы могут быть легко опрошены на верхнем уровне, добавление тестовых примеров для них будет тривиально.

  • Оболочка верхнего уровня используется многими другими пользователями и поэтому очень хорошо протестирована,Ваше собственное письмо часто ошибочно и не проверено.Подумайте об ограничениях.Подумайте о написании поплавков.Будете ли вы использовать write/1 для поплавков?Как правильно писать плавающие выражения, чтобы их можно было точно прочитать? - это способ сделать это в .Вот ответ:

  • В оболочке верхнего уровня отображается действительный текст Пролога.На самом деле ответ сам по себе является запросом!Его можно вставить обратно на верхний уровень - только чтобы получить тот же ответ.Таким образом, вы узнаете более экзотические, но неизбежные детали Пролога, такие как цитирование, экранирование и скобки.В противном случае практически невозможно выучить синтаксис, поскольку синтаксические анализаторы Prolog часто чрезвычайно разрешительны.

  • Скорее всего, ваша программа будет более доступна для декларативных рассуждений.

Скорее всего, ваши две процедуры methodone и methodtwo неверны: вы забыли перевод строки после написания Done.Так что methodone, methodone содержит искаженную строку.Как это легко проверить?

Но давайте посмотрим немного подробнее на вашу программу.Что характерно для циклов, управляемых ошибками, так это то, что они невинно начинаются как нечто, производящее «только» побочные эффекты, но рано или поздно они также имеют тенденцию привлекать больше семантических частей.В вашем случае, atom_length/2 скрыто в цикле, управляемом отказами, полностью недоступном для тестирования или рассуждений.

Соображения эффективности

Системы Prolog часто реализуют отказ, освобождая стек.Следовательно, циклы, управляемые сбоями, не требуют сборщика мусора.Вот почему люди считают, что отказоустойчивые циклы эффективны.Однако это не обязательно так.Для такой цели, как findall(A, season(A), As), каждый ответ на A копируется в некоторое пространство.Это тривиальная операция для чего-то вроде атомов, но представьте себе более крупный термин.Скажем:

blam([]).
blam([L|L]) :- blam(L).

bigterm(L) :- length(L,64), blam(L).

Во многих системах findall/3 или assertz/1 на этот большой срок заморозят систему.

Кроме того, системы, такие как SWI, YAP, SICStus, имеют довольно сложныесборщики мусора.А использование меньшего количества циклов, управляемых сбоями, поможет еще более улучшить эти системы, поскольку это создает потребность в более сложных методах .

7 голосов
/ 17 марта 2012

Первый метод кажется расточительным, поскольку факты доступны, зачем создавать их список (особенно большой список). Это должно иметь последствия для памяти, если список достаточно велик?

Да, метод 1 занимает Θ ( n ) памяти. Основное преимущество заключается в том, что оно декларативно, т. Е. Имеет прямое логическое значение.

Метод 2, «цикл, управляемый ошибками», как его называют программисты Пролога, занимает постоянную память, является процедурным и может быть предпочтительным, когда вы все равно делаете процедурные (вне логические) вещи; то есть в коде ввода / вывода можно использовать его.

Обратите внимание, что у SWI-Prolog есть третий способ написания этого цикла:

forall(season(S), showseason(S)).

Это работает, только если showseason успешно выполняется для каждой привязки season(S).

3 голосов
/ 17 марта 2012

Если уже используется findall, почему бы и не maplist:

findall(S, season(S), L), maplist( showseason, L).

Оба не в чисто логическом ядре Пролога. И да, вы выделяете целый списокдля всех решений.

Ваш второй метод называется «цикл, управляемый отказами», и в этом нет ничего плохого, за исключением того, что невозможно вернуться к предыдущим решениям после возврата через отказ.Вот почему findall не логично.Внутренне это может быть вызвано как цикл, управляемый ошибками, который сохраняет промежуточные результаты посредством утверждения.Таким образом, второй концептуально более чистый, в дополнение к тому, что он не выделяет никакой дополнительной памяти.Обычно используется в предикатах верхнего уровня "драйвер" (т. Е. Пользовательский интерфейс).

...