Каковы плюсы и минусы использования ручной итерации списка по сравнению с рекурсией через сбой

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

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

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

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 ответа

Решение

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

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

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

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

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

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

Источник

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

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

? - сезон (S), длина атома (S, L). S = весна,
L = 6;
S = лето,
L = 6;
S = осень,
L = 6;
S = зима,
L = 6

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

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

? - сезон (S), длина атома (S,L), диф (L,6). ложный.

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

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

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

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

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

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

В ISO writeq/1,2, write_canonical/1,2, write_term/2,3 с опцией quoted(true) гарантировать, что поплавки могут быть прочитаны точно. То есть они одинаковы по (==)/2

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

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

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

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

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

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

Blam([]).
Блам ([L|L]):- Блам (L).

bigterm(L):- длина (L,64), глухой (L).

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

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

Источник

При использовании findall уже почему бы и нет maplist также:

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

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

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

Источник
Другие вопросы по тегам