Пролог находит наибольшее целое число в списке из хвоста

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

Вот что у меня так далеко:

largest([X],X).
largest([X|Xs],X) :- largest(Xs,Y), X>=Y.
largest([X|Xs],N) :- largest(Xs,N), N>X.

Имейте в виду, что это находит наибольшее целое число в голове, и мне нужно, чтобы оно работало от хвоста. Спасибо за помощь.

Источник

3 ответа

Подожди секунду! Прежде чем продолжить, сначала измерьте время, которое занимает ваш предикат!

? - длина (J,I), I>10, добавление (J,[2],L), список карт (=(1),J), время (наибольшее (L, N)).
% 12,282 умозаключений, 0,006 ЦП за 0,006 секунды (99% ЦП, 1977389 губ)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
Я = 11,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2;
% 4, 0,000 CPU за 0,000 секунд (84% CPU, 98697 Lips)
% 24,570 выводов, 0,011 ЦП за 0,011 секунды (99% ЦП, 2191568 губ)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
Я = 12,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2;
Выводы% 4, 0,000 CPU за 0,000 секунд (84% CPU, 98556 Lips)
% 49,146 выводов, 0,021 ЦП за 0,021 секунды (100% ЦП, 2365986 губ)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
Я = 13,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ...

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

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

самый большой ([X],X):- ложно. самый большой ([X|Xs],X):- самый большой (Xs, Y), false, X> = Y. самый большой ([X|Xs],N):- самый большой (Xs, N), false, N> X.

Для каждого элемента в списке у нас есть два одинаково применимых варианта. Так со списком N элементы, у нас есть 2^N выбор!

Вот возможный переписать:

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y, R = X
   ;  Y > X, R = N
   ).

Вы можете сделать еще лучше, используя if-then-else...

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y -> R = X
   ;  Y > X, R = N
   ).

или же max/2

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   R is max(X,Y).

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

А для фактической оптимизации, которую вы хотите выполнить, прочитайте

SWI-Пролог: Sum-List

Источник

Хвостово-рекурсивное решение "голова-вперед" выглядит так:

largest( [X|Xs] , Max ) :- largest( Xs , X , Max ) .

largest( []     , R , R ) .
largest( [X|Xs] , T , R ) :- X >  T , largest( Xs , X , R ) .
largest( [X|Xs] , T , R ) :- X =< T , largest( Xs , T , R ) .

largest/2 просто вызывает largest/3, заполняя свой аккумулятор заголовком списка (начальное значение 'max'). Как largest/3 повторяется вниз по списку, он заменяет этот аккумулятор новым "текущим" максимальным значением при его обнаружении. Когда список исчерпан, аккумулятор имеет максимальное значение для всего списка.

Ваше первоначальное решение:

largest([X],X).
largest([X|Xs],X) :- largest(Xs,Y), X>=Y.
largest([X|Xs],N) :- largest(Xs,N), N>X.

бежит в хвост Он возвращается до конца списка, после чего он решает, что последний элемент в списке является начальным значением "max". Когда он поднимает стек по пути вверх, он сравнивает это с предыдущим значением и делает все необходимое.

Проблема с вашим подходом состоит из двух частей:

  • он выполняется за время, близкое к O (n2), так как он должен многократно повторять список при каждой ошибке.
  • он занимает пространство стека, вы дали список достаточной длины, вы не сможете вычислить решение из-за переполнения стека, с которым вы столкнетесь.

С другой стороны, хвостовой рекурсивный подход "голова-сначала" выполняется за O(n) времени: список повторяется только один раз, в конце которого у вас есть решение. Кроме того, благодаря оптимизации хвостовой рекурсии рекурсивный вызов по существу преобразуется в итерацию, что означает, что пространство стека не используется вне исходного кадра стека. Это означает, что решение может быть рассчитано для списков любой длины (при условии, что вы готовы ждать ответа).

Источник

Идиоматическая, хвостово-рекурсивная, голова-первая версия:

largest([X|Xs], O) :- largest(Xs, X, O).

largest([], O, O).
largest([X|Xs], M, O) :-
    M1 is max(X, M),
    largest(Xs, M1, O).
Источник
Другие вопросы по тегам