Алгоритм выбора

Информацию о моделировании естественного отбора в генетических алгоритмах см. в разделе « Отбор (генетический алгоритм)» .

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

Постановка задачи

Алгоритм решения задачи выбора принимает на вход набор значений и число $k$. Он выводит $k$наименьшее из этих значений или, в некоторых вариантах задачи, набор $k$ наименьшие значения. Чтобы это было четко определено, должна быть возможность сортировать значения в порядке от наименьшего к наибольшему; например, это могут быть целые числа , числа с плавающей запятой или какой-либо другой объект с числовым ключом. Однако не предполагается, что они уже отсортированы. Часто алгоритмы выбора ограничиваются моделью вычислений , основанной на сравнении , как в алгоритмах сортировки сравнением , где алгоритм имеет доступ к операции сравнения , которая может определить относительный порядок любых двух значений, но не может выполнять какие-либо другие арифметические действия. операции над этими значениями.

Чтобы упростить проблему, в некоторых работах по этой проблеме предполагается, что все значения отличны друг от друга. или что какой-то последовательный метод разрешения конфликтов использовался для присвоения порядка парам элементов с одинаковым значением друг друга. Другой вариант постановки задачи касается нумерации упорядоченных значений: наименьшее значение, полученное заданием $k=0$, как при нумерации массивов с нуля , или получается установкой $k=1$, следуя обычным англоязычным соглашениям о самом маленьком, втором по величине и т. д.? Эта статья следует соглашениям, используемым Корменом и др., согласно которым все значения различны, а минимальное значение получается из $k=1$.

Согласно этим соглашениям, максимальное значение среди совокупности $n$ значений, получается путем установки $k=n$. Когда $n$ является нечетным числом , медиана коллекции получается путем установки $k=(n+1)/2$. Когда $n$ четно, есть два варианта медианы, получаемой округлением этого выбора. $k$ вниз или вверх соответственно: нижняя медиана с $k=n/2$ и верхняя медиана с $k=n/2+1$.

Алгоритмы

Сортировка и пирамидальная выборка

В качестве базового алгоритма выбор $k$Наименьшее значение в коллекции значений можно получить с помощью следующих двух шагов:

• Сортировка коллекции
• Если выходные данные алгоритма сортировки представляют собой массив , извлеките его $k$-й элемент; в противном случае просканируйте отсортированную последовательность, чтобы найти $k$й элемент.

Во времени для этого метода преобладает этап сортировки, который требует $\Theta (n\log n)$ время с использованием сортировки сравнения . Даже когда можно использовать алгоритмы целочисленной сортировки , они обычно медленнее, чем линейное время, которого можно достичь с помощью специализированных алгоритмов выбора. Тем не менее, простота этого подхода делает его привлекательным, особенно когда высокооптимизированная процедура сортировки предоставляется как часть библиотеки времени выполнения, а алгоритм выбора — нет. Для входных данных среднего размера сортировка может быть быстрее, чем алгоритмы неслучайного выбора, из-за меньших постоянных факторов во времени ее выполнения. Этот метод также создает отсортированную версию коллекции, которая может быть полезна для других последующих вычислений, в частности для выбора других вариантов выбора. $k$.

Для алгоритма сортировки, генерирующего по одному элементу за раз, такого как сортировка выбором , сканирование может выполняться одновременно с сортировкой, и сортировка может быть прекращена, как только $k$элемент найден. можно считать один из возможных вариантов создания утешительной сетки в турнире с выбыванием из турнира с одним выбыванием , в котором команды, проигравшие возможному победителю, играют еще один мини-турнир для определения второго места. Примером этого метода Применение этой оптимизации к пирамидальной сортировке создает алгоритм heapselect , который может выбирать $k$наименьшее значение во времени $O(n+k\log n)$. Это быстро, когда $k$ мал по сравнению с $n$, но вырождается в $O(n\log n)$ для больших значений $k$, например, выбор $k=n/2$ используется для нахождения медианы.

Поворот

Многие методы выбора основаны на выборе специального «поворотного» элемента из входных данных и использовании сравнений с этим элементом для разделения оставшихся $n-1$ входные значения в два подмножества: набор $L$ элементов меньше, чем стержень, и множество $R$ элементов больше, чем ось. Затем алгоритм может определить, где находится $k$наименьшее значение необходимо найти на основе сравнения $k$ с размерами этих наборов. В частности, если $k\leq |L|$, ​ $k$наименьшее значение находится в $L$, и его можно найти рекурсивно, применив тот же алгоритм выбора к $L$. Если $k=|L|+1$, тогда $k$Наименьшее значение — это опорная точка, и его можно вернуть немедленно. В оставшемся случае $k$наименьшее значение находится в $R$, а точнее, это элемент в позиции $k-|L|-1$ из $R$. Его можно найти, рекурсивно применив алгоритм выбора, ища значение в этой позиции в $R$.

Как и в случае с соответствующим алгоритмом быстрой сортировки на основе поворота , разделение входных данных на $L$ и $R$ это можно сделать путем создания новых коллекций для этих наборов или с помощью метода, который разбивает заданный тип данных списка или массива на месте. Подробности различаются в зависимости от того, как представлена ​​входная коллекция . Время для сравнения опорной точки со всеми остальными значениями равно $O(n)$. Однако методы поворота различаются тем, как они выбирают поворот, что влияет на размер подзадач в каждом рекурсивном вызове. Эффективность этих методов во многом зависит от выбора стержня. Если ось выбрана неудачно, время работы этого метода может быть очень медленным . $O(n^{2})$.

• Если бы точка поворота находилась точно на середине входных данных, то каждый рекурсивный вызов имел бы не более половины значений, чем предыдущий вызов, а общее время складывалось бы в прогрессию геометрическую $O(n)$. Однако нахождение медианы само по себе является проблемой выбора для всего исходного ввода. Попытка найти его с помощью рекурсивного вызова алгоритма выбора приведет к бесконечной рекурсии, поскольку размер задачи не будет уменьшаться при каждом вызове.
• Быстрый выбор равномерно случайным образом выбирает опорную точку из входных значений. Его можно описать как алгоритм обрезки и поиска . вариант быстрой сортировки с той же стратегией поворота, но где быстрая сортировка выполняет два рекурсивных вызова для сортировки двух подколлекций $L$ и $R$, быстрый выбор выполняет только один из этих двух вызовов. Его ожидаемое время $O(n)$. Для любой константы $C$, вероятность того, что число его сравнений превысит $Cn$ суперэкспоненциально мал в $C$.
• Алгоритм Флойда-Ривеста , разновидность быстрого выбора, выбирает точку поворота путем случайной выборки подмножества $r$ значения данных для некоторого размера выборки $r$, а затем рекурсивно выбираем два элемента немного выше и ниже позиции $rk/n$ образца для использования в качестве опорных точек. При таком выборе вполне вероятно, что $k$ зажат между двумя опорными точками, так что после поворота для рекурсивного вызова остается лишь небольшое количество значений данных между опорными точками. Этот метод позволяет добиться ожидаемого количества сравнений, т.е. $n+\min(k,n-k)+o(n)$. В своей оригинальной работе Флойд и Ривест утверждали, что $o(n)$ срок можно сделать настолько маленьким, насколько $O({\sqrt {n}})$ по рекурсивной схеме выборки, но правильность их анализа подвергается сомнению. Вместо этого более строгий анализ показал, что версия их алгоритма достигает $O({\sqrt {n\log n}})$ на этот срок. Хотя обычный анализ как быстрого выбора, так и алгоритма Флойда-Ривеста предполагает использование истинного генератора случайных чисел , было доказано, что версия алгоритма Флойда-Ривеста, использующая генератор псевдослучайных чисел, засеянный только логарифмическим количеством истинных случайных битов, работает в линейное время с высокой вероятностью.

Визуализация выбора опорной точки для метода медианы медиан . Каждый набор из пяти элементов показан на рисунке в виде столбца точек, отсортированных по возрастанию сверху вниз. Если их медианы (зеленые и фиолетовые точки в среднем ряду) отсортировать по возрастанию слева направо и выбрать в качестве опорной медиану, то $3n/10$ элементов в верхнем левом квадранте будет меньше опорного, а $3n/10$ элементы в нижнем правом квадранте будут больше, чем поворот, показывая, что многие элементы будут удалены при повороте.

• Метод медианы медиан разделяет входные данные на наборы из пяти элементов и использует какой-либо другой нерекурсивный метод для нахождения медианы каждого из этих наборов за постоянное время для каждого набора. Затем он рекурсивно вызывает себя, чтобы найти медиану этих значений. $n/5$ медианы. Используя полученную медиану медиан в качестве опорной точки, получается раздел с $\max(|L|,|R|)\leq 7n/10$. Таким образом, проблема на $n$ элементов сводится к двум рекурсивным задачам на $n/5$ элементы (чтобы найти ось) и не более $7n/10$ элементы (после использования точки поворота). Общий размер этих двух рекурсивных подзадач не более $9n/10$, что позволяет анализировать общее время как геометрическую прогрессию, добавляющую к $O(n)$. В отличие от быстрого выбора, этот алгоритм является детерминированным, а не рандомизированным. Это был первый известный алгоритм детерминированного выбора с линейным временем. и обычно преподается на курсах по алгоритмам для студентов как пример принципа « разделяй и властвуй» , который не делится на две равные подзадачи. Однако высокие постоянные факторы в его $O(n)$ ограничение по времени делает его на практике медленнее, чем быстрый выбор , и даже медленнее, чем сортировка входных данных среднего размера.
• Гибридные алгоритмы, такие как интроселект, могут использоваться для достижения практической эффективности быстрого выбора с возвратом к медианам медиан, гарантирующим наихудший случай. $O(n)$ время.

Заводы

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

Параллельные алгоритмы

Параллельные алгоритмы отбора изучаются с 1975 года, когда Лесли Валиант представил модель параллельного дерева сравнений для анализа этих алгоритмов и доказал, что в этой модели отбор с использованием линейного числа сравнений требует $\Omega (\log \log n)$ параллельные шаги, даже для выбора минимума или максимума. Позже исследователи обнаружили параллельные алгоритмы отбора в $O(\log \log n)$ шагов, соответствующих этой границе. В модели дерева рандомизированных параллельных сравнений можно выполнять выбор за ограниченное число шагов и линейное число сравнений. В более реалистичной модели вычислений с параллельным ОЗУ , с исключительным доступом к памяти для чтения и исключительной записи, выбор может выполняться вовремя. $O(\log n)$ с $O(n/\log n)$ процессоров, что оптимально как по времени, так и по количеству процессоров. При одновременном доступе к памяти в целом возможно немного более быстрое параллельное время . и $\log n$ срок в ограниченном времени может быть заменен на $\log k$.

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

Когда данные уже организованы в структуру данных , выбор может быть выполнен за время, сублинейное по количеству значений. В качестве простого случая для данных, уже отсортированных в массив, выбор $k$Этот элемент может быть выполнен путем одного поиска в массиве за постоянное время. Для значений, организованных в двумерный массив размером $m\times n$, при отсортированных строках и столбцах выбор может выполняться во времени $O{\bigl (}m\log(2n/m){\bigr )}$или быстрее, когда $k$ мал по сравнению с размерами массива. Для коллекции $m$ одномерные отсортированные массивы, с $k_{i}$ элементы меньше, чем выбранный элемент в $i$массив , время ${\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}$.

Выбор из данных в двоичной куче требует времени $O(k)$. Это не зависит от размера $n$ из кучи и быстрее, чем $O(k\log n)$ ограниченное по времени, которое будет получено в результате поиска по принципу «сначала лучшее» . Тот же метод можно применять в более общем плане к данным, организованным в виде любого дерева с кучей (дерева, в котором каждый узел хранит одно значение, в котором родительский элемент каждого некорневого узла имеет меньшее значение, чем его дочерний элемент). Этот метод выполнения выбора в куче применялся к задачам составления списка нескольких решений задач комбинаторной оптимизации, таких как поиск k кратчайших путей во взвешенном графе, путем определения пространства состояний решений в форме неявно определенной кучи. упорядоченное дерево, а затем применить этот алгоритм выбора к этому дереву. С другой стороны, алгоритмы выбора линейного времени используются в качестве подпрограммы в структуре данных приоритетной очереди, связанной с кучей, что сокращает время извлечения ее. $k$этот предмет из $O(\log n)$ к $O(\log ^{*}n+\log k)$; здесь $\log ^{*}n$ это повторный логарифм .

Для набора значений данных, подвергающихся динамическим вставкам и удалениям, дерево статистики заказов дополняет самобалансирующуюся структуру двоичного дерева поиска постоянным объемом дополнительной информации на каждый узел дерева, позволяя вставлять, удалять и выполнять запросы выбора, которые запрашивают $k$-й элемент в текущем наборе, чтобы все были выполнены в $O(\log n)$ время на одну операцию. Выходя за рамки сравнительной модели вычислений, можно добиться более быстрого выполнения операции для значений, представляющих собой небольшие целые числа, над которыми разрешены двоичные арифметические операции . Невозможно использовать потоковый алгоритм с сублинейной памятью в обоих случаях. $n$ и $k$ для решения запросов выбора именно для динамических данных, но скетч count-min можно использовать для приближенного решения запросов выбора, находя значение, положение которого в упорядочении элементов (если бы оно было добавлено к ним) было бы в пределах $\varepsilon n$ шаги $k$, для эскиза, размер которого находится в пределах логарифмических коэффициентов $1/\varepsilon$.

Нижние границы

The $O(n)$ время работы алгоритмов выбора, описанных выше, необходимо, поскольку алгоритму выбора, который может обрабатывать входные данные в произвольном порядке, должно потребоваться столько времени, чтобы просмотреть все свои входные данные. Если какое-либо из его входных значений не сравнивается, это значение может быть тем, которое должно было быть выбрано, и алгоритм может дать неправильный ответ. Помимо этого простого аргумента, было проведено значительное количество исследований точного количества сравнений, необходимых для отбора, как в рандомизированном, так и в детерминированном случаях.

Выбор минимума $n$ ценности требуют $n-1$ сравнения, потому что $n-1$ значения, которые не выбраны, должны быть определены как неминимальные, поскольку они являются наибольшими в некотором сравнении, и никакие два из этих значений не могут быть самыми большими в одном и том же сравнении. Тот же аргумент применим симметрично и к выбору максимума.

Следующий простейший случай — выбор второго по величине. После нескольких неверных попыток первая точная нижняя оценка для этого случая была опубликована в 1964 году советским математиком Сергеем Кислицыным . Это можно показать, заметив, что выбор второго наименьшего значения также требует различения наименьшего значения от остальных, и рассмотрев число $p$ сравнений, включающих наименьшее значение, которое делает алгоритм для этой задачи. Каждый из $p$ элементы, которые сравнивались с наименьшим значением, являются кандидатами на второе наименьшее значение, и $p-1$ одно из этих значений должно оказаться больше другого значения при втором сравнении, чтобы исключить их как вторые по наименьшему значению.С $n-1$ значения являются большими, по крайней мере, в одном сравнении, и $p-1$ если значения больше по крайней мере в двух сравнениях, то всего имеется не менее $n+p-2$ сравнения. Аргумент противника , в котором результат каждого сравнения выбирается так, чтобы максимизировать $p$ (при условии соблюдения хотя бы одного возможного порядка), а не числовых значений данных элементов, показывает, что можно заставить $p$ быть по крайней мере $\log _{2}n$. Следовательно, наихудшее количество сравнений, необходимое для выбора второго наименьшего значения, равно $n+\lceil \log _{2}n\rceil -2$, то же число, которое было бы получено при проведении турнира на выбывание со вторым туром среди значений, проигравших до наименьшего значения. Однако ожидаемое количество сравнений алгоритма рандомизированного выбора может быть лучше этой границы; например, выбор второго наименьшего из шести элементов требует в худшем случае семи сравнений, но может быть выполнен с помощью рандомизированного алгоритма с ожидаемым числом 6,5 сравнений.

В более общем плане, выбор $k$й элемент из $n$ требуется как минимум $n+\min(k,n-k)-O(1)$ сравнений, в среднем случае, соответствующих числу сравнений алгоритма Флойда–Ривеста до его $o(n)$ срок. Аргументация ведется непосредственно в пользу детерминированных алгоритмов с рядом сравнений, усредняемых по всем возможным перестановкам входных значений. Согласно принципу Яо , это также применимо к ожидаемому количеству сравнений для рандомизированного алгоритма на его входных данных в худшем случае.

Для детерминированных алгоритмов было показано, что выбор $k$для этого элемента требуется ${\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})$ сравнения, где $$H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}$$ — двоичная функция энтропии . мере Особый случай поиска медианы имеет немного большую нижнюю границу количества сравнений, по крайней $(2+\varepsilon )n$, для $\varepsilon \approx 2^{-80}$.

Точное количество сравнений

Нахождение медианы пяти значений с использованием шести сравнений. На каждом этапе сравнения, которые необходимо выполнить дальше, показаны в виде сегментов желтой линии, а диаграмма Хассе найденных на данный момент отношений порядка (меньше = ниже и больше = выше) в виде сегментов синей линии. Уже обнаружено, что красные элементы превышают три других и поэтому не могут быть медианой. Больший из двух элементов в окончательном сравнении является медианой.

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

0

1    1

2    3    2

3    4    4    3

4    6    6    6    4

5    7    8    8    7    5

6    8   10   10   10   8    6

7    9   11   12   12   11   9    7

8   11   12   14   14   14   12   11   8

9   12   14   15   16   16   15   14   12   9

Большую часть, но не все записи в левой половине каждой строки можно найти по формуле $$n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.$$ Это описывает количество сравнений, выполненных с помощью метода Абдоллы Хадиана и Милтона Собела , связанного с кучей, который находит наименьшее значение с использованием турнира с одним выбыванием, а затем повторно использует меньший турнир среди значений, исключенных возможными победителями турнира, чтобы найти следующие последовательные значения до достижения $k$самый маленький. С помощью компьютерного поиска было доказано, что некоторые из более крупных записей являются оптимальными.

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

Очень немногие языки имеют встроенную поддержку общего выбора, хотя многие предоставляют средства для поиска наименьшего или самого большого элемента списка. Заметным исключением является Стандартная библиотека шаблонов для C++ , которая предоставляет nth_element метод с гарантией ожидаемого линейного времени.

Python включает в себя Стандартная библиотека heapq.nsmallest и heapq.nlargest функции для возврата самых маленьких или самых больших элементов из коллекции в отсортированном порядке. Реализация поддерживает двоичную кучу , ограниченную хранением $k$ элементы и инициализируется первым $k$ элементы в коллекции. Тогда каждый последующий элемент коллекции может заменить самый большой или самый маленький элемент в куче, если он меньше или больше этого элемента. Использование памяти алгоритмом превосходит алгоритм heapselect (первый поддерживает только $k$ элементы в памяти одновременно, в то время как последний требует манипулирования всем набором данных в памяти). Время выполнения зависит от порядка данных. В лучшем случае это $O((n-k)+k\log k)$ для уже отсортированных данных. Худший случай $O(n\log k)$ для обратно отсортированных данных. В обычных случаях обновлений кучи, скорее всего, будет немного, и большинство входных элементов обрабатываются только с одним сравнением. Например, извлечение 100 наибольших или наименьших значений из 10 000 000 случайных входных данных дает в среднем 10 009 401 сравнение.

С 2017 года в состав Matlab входит maxk() и mink() функции, которые возвращают максимальное (минимальное) $k$ значения в векторе, а также их индексы. В документации Matlab не указано, какой алгоритм используют эти функции или каково время их работы.

История

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

См. также

• Геометрическая медиана § Вычисления , алгоритмы многомерного обобщения медиан
• Медианный фильтр , применение алгоритмов поиска медианы при обработке изображений