Введение

Метод поиска k-го наименьшего значения, моделирование естественного отбора в генетических алгоритмах

В информатике алгоритм отбора — это алгоритм для поиска k-го наименьшего значения в наборе упорядоченных значений, таких как числа. Значение, которое он находит, называется k-й порядковой статистикой. Отбор включает в себя, как частные случаи, задачи поиска минимального, медианного и максимального элементов в наборе. Алгоритмы отбора включают в себя алгоритм Quickselect и алгоритм медианы медиан. При применении к набору значений эти алгоритмы выполняются за линейное время, что выражается с помощью нотации «большое O». Для данных, которые уже структурированы, могут быть возможны более быстрые алгоритмы; в крайнем случае, отбор в уже отсортированном массиве занимает время .

Заявление о проблеме

Алгоритм для задачи выбора принимает на вход набор значений и число *k*, и выводит *k*-е наименьшее из этих значений, или, в некоторых версиях задачи, набор *k* наименьших значений. Для того, чтобы это было корректно определено, необходимо иметь возможность упорядочить значения от наименьшего к наибольшему; например, это могут быть целые числа, числа с плавающей точкой или объекты другого типа с числовым ключом. Однако не предполагается, что значения уже отсортированы. Часто алгоритмы выбора ограничиваются моделью вычислений, основанной на сравнении, как и в алгоритмах сортировки сравнением, где алгоритм имеет доступ к операции сравнения, позволяющей определить относительный порядок любых двух значений, но не может выполнять другие арифметические операции над этими значениями. Для упрощения задачи некоторые работы предполагают, что все значения различны или что для пар элементов с одинаковым значением используется последовательный метод разрешения конфликтов для определения порядка. Другая вариация в определении задачи касается нумерации упорядоченных значений: наименьшее значение получается при *k* = 1, как в нулевой нумерации массивов, или при *k* = 1, следуя общепринятым в английском языке обозначениям для наименьшего, второго наименьшего и т.д.? В данной статье используются соглашения, принятые у Кормена и др., согласно которым все значения различны, а минимальное значение получается при *k* = 1. При этом максимальное значение среди набора из *n* значений получается при *k* = *n*. Если *n* – нечетное число, то медиана набора получается при *k* = (*n* + 1) / 2. Если *n* – четное число, то существует два варианта для медианы, получаемых округлением этого значения *k* вниз или вверх, соответственно: нижняя медиана при *k* = *n* / 2 и верхняя медиана при *k* = (*n* / 2) + 1.

Заводы

Детерминированные алгоритмы выбора с наименьшим известным числом сравнений, для значений, далеких от 0 или 1, основаны на концепции фабрик, введенной в 1976 году Арнольдом Шёнхаге, Майком Паттерсоном и другими. Это методы, которые строят частичные порядки определенных типов на небольших подмножествах входных значений, используя сравнения для объединения меньших частичных порядков. В качестве простого примера, один тип фабрики может принимать на вход последовательность частичных порядков, состоящих из одного элемента, сравнивать пары элементов из этих порядков и выдавать последовательность полностью упорядоченных множеств по два элемента. Элементы, используемые в качестве входа для этой фабрики, могут быть либо входными значениями, которые еще не сравнивались ни с чем, либо "лишними" значениями, созданными другими фабриками. Цель алгоритма, основанного на фабриках, – объединить различные фабрики, при этом выходы одних фабрик служат входами для других, чтобы в конечном итоге получить частичный порядок, в котором один элемент (k-й наименьший) больше, чем некоторые другие элементы, и меньше, чем остальные. Тщательное проектирование этих фабрик приводит к алгоритму, который при применении к поиску медианы использует не более сравнений. Для других значений k число сравнений равно.

Сублинейные структуры данных

Когда данные уже организованы в структуру данных, возможно выполнение выборки за время, сублинейное по количеству значений. В качестве простого примера, для данных, уже отсортированных в массив, выбор *k*-го элемента может быть выполнен одним обращением к массиву, за постоянное время. Для значений, организованных в двумерный массив размером *n* × *m* с отсортированными строками и столбцами, выборка может быть выполнена за время *O(n + m)*, или быстрее, когда *n* и *m* малы относительно размера массива. Для коллекции одномерных отсортированных массивов, с *k* элементами меньше, чем выбранный элемент в *i*-м массиве, время составляет *O(k + i)*.

Выборка из данных в двоичной куче занимает время *O(log n)*. Это не зависит от размера *n* кучи и быстрее, чем *O(n)*, которое было бы получено при простом переборе. Этот же метод может быть применен более широко к данным, организованным как любое дерево, упорядоченное по принципу кучи (дерево, в котором каждый узел хранит одно значение, и родитель каждого узла (кроме корня) имеет значение меньше, чем его потомок). Этот метод выполнения выборки в куче применяется к задачам перечисления множественных решений комбинаторных задач оптимизации, таких как поиск *k* кратчайших путей во взвешенном графе, путем определения пространства состояний решений в форме неявно заданного дерева, упорядоченного по принципу кучи, а затем применения этого алгоритма выборки к нему. В противоположном направлении, алгоритмы линейного времени для выборки использовались в качестве подпрограммы в структуре данных приоритетной очереди, связанной с кучей, улучшая время извлечения *k*-го элемента из *O(n)* до *O(log n)*. Здесь *n* – размер кучи.

Для коллекции значений данных, подвергающихся динамическим вставкам и удалениям, дерево статистического ранга дополняет самобалансирующееся бинарное дерево поиска постоянным объемом дополнительной информации на узел, позволяя выполнять вставку, удаление и запросы на выборку *k*-го элемента в текущем наборе за время *O(log n)* на операцию. Выходя за рамки модели вычислений, основанной на сравнениях, возможно достижение более быстрого времени на операцию для значений, являющихся небольшими целыми числами, на которых выполняются бинарные арифметические операции. Невозможно для потокового алгоритма с памятью, сублинейной как по *n*, так и по *m*, точно решать задачи выборки для динамических данных, но структура данных Count-Min Sketch может быть использована для приблизительного решения задач выборки, находя значение, чья позиция в упорядочении элементов (если бы оно было добавлено к ним) находилась бы в пределах *εn* от *k*, для структуры данных размером, отличающимся на логарифмические факторы.

Языковая поддержка

Очень немногие языки программирования имеют встроенную поддержку общего выбора, хотя многие предоставляют средства для поиска наименьшего или наибольшего элемента в списке. Примечательным исключением является библиотека стандартных шаблонов (STL) для C++, которая предоставляет шаблонный метод nth_element с гарантией ожидаемого линейного времени. Стандартная библиотека Python (начиная с версии 2.4) включает подпрограммы `heapq.nsmallest` и `heapq.nlargest` для возврата наименьших или наибольших элементов из коллекции в отсортированном порядке. Различные версии Python использовали разные алгоритмы для этих подпрограмм. Начиная с Python 3.13, реализация использует двоичную кучу, ограниченную хранением *k* элементов и инициализированную первыми *k* элементами коллекции. Затем каждый последующий элемент коллекции может заменить наибольший или наименьший элемент в куче (соответственно для `heapq.nsmallest` и `heapq.nlargest`), если он меньше или больше этого элемента. В худшем случае время работы этой реализации составляет O(n log k), что хуже, чем O(n), которое можно достичь с помощью алгоритма heapselect. Однако для случайных входных последовательностей, вероятно, будет немного обновлений кучи, и большинство входных элементов будут обработаны только с одним сравнением. С 2017 года в Matlab включены функции `maxk` и `mink`, которые возвращают максимальные (минимальные) *k* значений в векторе, а также их индексы. В документации Matlab не указано, какой алгоритм используют эти функции и какова их сложность.

История

Quickselect был представлен Тони Хоаром без анализа и впервые проанализирован в техническом отчете 1971 года. Первым известным детерминированным алгоритмом выбора за линейное время является метод медианы медиан, опубликованный в 1973 году Мануэлем Блумом, Робертом Флойдом, Воганом Праттом, Роном Ривестом и Робертом Тарджаном. Они возводят формулировку задачи выбора к работам Чарльза Л. Доджсона (более известного как Льюис Кэрролл), который в 1883 году отметил, что стандартная схема спортивных турниров с выбыванием после поражения не гарантирует, что второй лучший игрок займет второе место, а также к работам Хьюго Стейнхауса примерно в 1930 году, который развил эту же идею, запросив разработку схемы турнира, способной обеспечить такую гарантию при минимальном количестве проведенных игр (то есть,