Программа, которая находит K-й самый большой элемент в списке

Question

Я пишу логическую программу для kth_largest (Xs, K), которая реализует линейный алгоритм для нахождения k-го наибольшего элемента K из списка Xs.Алгоритм имеет следующие шаги:

1. Разбить список на группы из пяти элементов.
2. Эффективно найти медиану каждой из групп, что можно сделать с фиксированным числомсравнения.
3. Рекурсивно найти медиану медиан.
4. Разбить исходный список по медиане медиан.
5. Рекурсивно найти самый большой k-й элемент в соответствующемменьший список.

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

select(X; HasXs; OneLessXs)  
% The list OneLessXs is the result of removing
% one occurrence of X from the list HasXs.
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :-  select(X,Ys,Zs).

Answer 1

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

Я нашел статью в Википедии о Алгоритм выбора , чтобы быть весьма полезным в понимании общей картины "быстрых" (наихудшего случая с линейным временем) алгоритмов этого типа.

Но то, что вы спросили в конце вашего Вопроса, несколько проще.Вы написали: «Как мне это сделать? Я могу выбрать элемент из списка, но я не знаю, как получить наибольшее , используя вышеописанную процедуру».(акцент был добавлен мной)

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

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

Задача поиска самого большого элемента является детерминированной (по крайней мере, если все элементы различны), иэто более простая задача, чем общий выбор k-го наибольшего элемента (среди прочего, задача, связанная со статистикой заказов).

Давайте дадим простой, надеюсь, очевидно правильный код для поиска наибольшего элемента, а затемпоговорим о более оптимизированном способе сделать это.

maxOfList(H,[H|T]) :-  upperBound(H,T), !.
maxOfList(X,[_|T]) :-  maxOfList(X,T).

upperBound(X,[ ]).
upperBound(X,[H|T]) :-
    X >= H,
    upperBound(X,T).

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

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

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

Добавлено:

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

Вместо этого способ Пролога состоит в том, чтобы ввести дополнительный аргумент и определитьпредикат maxOfList / 2 путем вызова вспомогательного предиката с тремя аргументами:

maxOfList(X,[H|T]) :- maxOfListAux(X,H,T).

Дополнительный аргумент в maxOfListAux / 3 может затем использоваться для отслеживаниянаибольшее значение «пока» выглядит следующим образом:

maxOfListAux(X,X,[ ]).
maxOfListAux(Z,X,[H|T]) :-
    ( X >= H  -> Y = X ; Y = H ),
    maxOfListAux(Z,Y,T).

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

Второе предложение для maxOfListAux оставляет первый аргумент несвязанным и «обновляет» второй аргумент соответственно как следующий элемент списка превышает предыдущее наибольшее значение или нет.

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

maxOfList(X,[X]) :- !.
maxOfList(X,[H1,H2|T]) :-
    ( H1 >= H2  -> Y = H1 ; Y = H2 ),
    maxOfList(X,[Y|T]).