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

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

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

Отбор по сортировке

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

Вместо сортировки всего списка или массива можно использовать частичная сортировка выбрать k самый маленький или k самые большие элементы. В kth наименьший (соотв., kth наибольший элемент) тогда является наибольшим (соответственно наименьшим элементом) частично отсортированного списка - тогда для доступа к массиву требуется O (1) и O (k) для доступа в списке.

Неупорядоченная частичная сортировка

Если частичная сортировка ослаблена, чтобы k наименьшие элементы возвращаются, но не по порядку, коэффициент O (k бревно k) можно исключить. Дополнительный максимальный выбор (взяв O (k) time) требуется, но поскольку ${ Displaystyle к Leq п}$ , это по-прежнему дает асимптотическую сложность O (п). Фактически, алгоритмы выбора на основе разделов дают как k-й наименьший элемент и k самые маленькие элементы (с другими элементами не по порядку). Это можно сделать за O (п) время - средняя сложность быстрый выбор и сложность наихудшего случая уточненных алгоритмов выбора на основе разделов.

И наоборот, имея алгоритм выбора, можно легко получить неупорядоченную частичную сортировку (k наименьшие элементы, а не по порядку) в O (п) время, перебирая список и записывая все элементы, меньшие kй элемент. Если это приведет к менее чем k - 1 элемент, все остальные элементы равны kй элемент. Следует проявлять осторожность из-за возможности равенства элементов: нельзя включать все элементы, меньшие, чем или равно то kth элемент, поскольку элементы больше, чем kth элемент также может быть равен ему.

Таким образом, неупорядоченная частичная сортировка (наименьшая k элементы, но не упорядоченные) и выбор kй элемент очень похож на проблемы. Мало того, что они имеют одинаковую асимптотическую сложность, O (п), но решение одного из них может быть преобразовано в решение другого с помощью простого алгоритма (нахождение макс. k элементы или фильтрующие элементы списка ниже порогового значения kth элемент).

Сортировка с частичным выбором

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

Очевидный алгоритм линейного времени для поиска минимума (соответственно максимума) - итерация по списку и отслеживание минимального (соответственно максимального) элемента - можно рассматривать как сортировку с частичным выбором, которая выбирает 1 наименьший элемент. Однако многие другие частичные сортировки также сводятся к этому алгоритму для случая k = 1, например частичная сортировка кучи.

В более общем смысле, сортировка с частичным выбором дает простой алгоритм выбора, который принимает O (кн) время. Это асимптотически неэффективно, но может быть достаточно эффективным, если k небольшой, и его легко реализовать. Конкретно, мы просто находим минимальное значение и перемещаем его в начало, повторяя в оставшемся списке, пока не накопим k элементы, а затем вернуть kй элемент. Вот алгоритм, основанный на частичном выборе:

функция select (список [1..n], k) за я из 1 к k minIndex = i minValue = список [i] за j из я + 1 к п делать            если список [j] тогда                minIndex = j minValue = list [j] список подкачки [i] и список [minIndex] возвращаться список [k]

Выбор по разделам

Линейная производительность может быть достигнута с помощью алгоритма выбора на основе разделов, в основном быстрый выбор. Quickselect - это вариант быстрая сортировка - в обоих случаях один выбирает точку поворота, а затем разбивает данные по ней, но в то время как Quicksort рекурсирует с обеих сторон раздела, Quickselect рекурсирует только с одной стороны, а именно с той стороны, на которой находится желаемый kth элемент есть. Как и в случае с быстрой сортировкой, он имеет оптимальную среднюю производительность, в данном случае линейную, но низкую производительность в худшем случае, в данном случае квадратичную. Это происходит, например, взяв первый элемент в качестве опоры и поиска максимального элемента, если данные уже отсортированы. На практике это можно избежать путем выбора случайного элемента в качестве шарнира, что дает почти наверняка линейная производительность. В качестве альтернативы можно использовать более осторожную детерминированную стратегию разворота, например медиана медиан. Они объединены в гибрид интроселект алгоритм (аналог интросорт ), который начинается с Quickselect, но возвращается к медиане медиан, если прогресс идет медленно, что приводит как к быстрой средней производительности, так и к оптимальной производительности в худшем случае O (п).

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

Медианный выбор как стратегия разворота

Алгоритм выбора медианы можно использовать для получения общего алгоритма выбора или алгоритма сортировки, применяя его в качестве стратегии поворота в Quickselect или Quicksort; если алгоритм выбора медианы является асимптотически оптимальным (линейное время), результирующий алгоритм выбора или сортировки также. На самом деле точная медиана не требуется - достаточно приблизительной медианы. в медиана медиан Алгоритм выбора, стратегия поворота вычисляет приблизительную медиану и использует ее как точку поворота, рекурсивно просматривая меньший набор для вычисления этой точки поворота. На практике накладные расходы на вычисление опорных точек значительны, поэтому эти алгоритмы обычно не используются, но этот метод представляет теоретический интерес для соотнесения алгоритмов выбора и сортировки.

Подробно, учитывая алгоритм выбора медианы, его можно использовать в качестве стратегии поворота в Quickselect, получая алгоритм выбора. Если алгоритм выбора медианы оптимален, то есть O (п), то итоговый общий алгоритм выбора также будет оптимальным, что опять же означает линейный. Это потому, что Quickselect - это разделяй и властвуй алгоритм, и использование медианы на каждом повороте означает, что на каждом шаге набор поиска уменьшается вдвое, поэтому общая сложность геометрическая серия раз сложность каждого шага, и, таким образом, просто постоянное умножение сложности отдельного шага, фактически ${ Displaystyle 2 = 1 / (1- (1/2))}$ раз (суммируя ряд).

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

Инкрементальная сортировка по выбору

В отличие от выбора путем сортировки, можно постепенно выполнять сортировку путем повторного выбора. Абстрактно выбор дает только один элемент, kй элемент. Однако практические алгоритмы выбора часто включают частичную сортировку или могут быть модифицированы для этого. Естественно, что выбор с помощью частичной сортировки выполняется с сортировкой элементов до k, и выбор с помощью разделения также сортирует некоторые элементы: оси сортируются по правильным позициям с k-й элемент является последней точкой поворота, а элементы между точками поворота имеют значения между значениями поворота. Разница между выбором на основе разделов и сортировкой на основе разделов, как и в случае quickselect и quicksort, заключается в том, что при выборе выполняется рекурсия только на одной стороне каждой точки поворота, сортируя только точки поворота (среднее значение log (п) используются точки поворота), а не повторяются по обеим сторонам оси.

Это можно использовать для ускорения последующего выбора тех же данных; в крайнем случае, полностью отсортированный массив допускает выбор O (1). Кроме того, по сравнению с первым выполнением полной сортировки, постепенная сортировка путем повторного выбора амортизирует стоимость сортировки по множественному выбору.

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

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

Использование структур данных для выбора в сублинейном времени

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

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

Когда требуется только минимум (или максимум), хорошим подходом является использование куча, который может найти минимальный (или максимальный) элемент за постоянное время, в то время как все остальные операции, включая вставку, выполняются O (log п) или лучше. В более общем плане самобалансирующееся двоичное дерево поиска можно легко дополнить, чтобы можно было как вставить элемент, так и найти k-й наибольший элемент в O (log п) время; это называется дерево статистики заказов. Мы просто сохраняем в каждом узле количество его потомков и используем его, чтобы определить, по какому пути следовать. Информация может быть обновлена эффективно, поскольку добавление узла влияет только на количество его O (журнал п) предков и вращения дерева влияют только на количество узлов, участвующих в повороте.

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

Если мы выберем час размером примерно sqrt (п), а вход близок к равномерно распределенному, эта схема может выполнять выборки за ожидаемые O (sqrt (п)) время. К сожалению, эта стратегия также чувствительна к кластеризации элементов в узком интервале, что может привести к корзинам с большим количеством элементов (кластеризацию можно исключить с помощью хорошей хеш-функции, но найдя элемент с k-е наибольшее значение хеш-функции не очень полезно). Кроме того, как и в случае с хеш-таблицами, эта структура требует изменения размеров таблицы для поддержания эффективности при добавлении элементов и п становится намного больше, чем час². Полезный случай этого - нахождение статистики порядка или экстремума в конечном диапазоне данных. Использование приведенной выше таблицы с интервалом корзины 1 и поддержание счетчиков в каждой корзине намного превосходит другие методы. Такие хеш-таблицы похожи на частотные таблицы используется для классификации данных в описательная статистика.

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

В Искусство программирования, Дональд Э. Кнут обсудили ряд нижних границ количества сравнений, необходимых для определения местоположения т наименьшие записи неорганизованного списка п предметы (используя только сравнения). Существует тривиальная нижняя оценка п - 1 для минимального или максимального входа. Чтобы убедиться в этом, рассмотрим турнир, в котором каждая игра представляет собой одно сравнение. Поскольку каждый игрок, кроме победителя турнира, должен проиграть игру, прежде чем мы узнаем победителя, у нас есть нижняя граница п - 1 сравнение.

Для других индексов история становится более сложной. Мы определяем ${ Displaystyle W_ {т} (п)}$ как минимальное количество сравнений, необходимое для нахождения т наименьшие значения. Кнут ссылается на статью С.С. Кислицына, в которой показана верхняя граница этого значения:

{ Displaystyle W_ {T} (N) Leq N-T + Sum _ {N + 1-T

Эта оценка достижима при т= 2, но лучше известны более сложные оценки для больших т.^{[нужна цитата ]}

Космическая сложность

Требуемая пространственная сложность выбора составляет O (1) дополнительного хранилища в дополнение к хранению массива, в котором выполняется выбор. Такая пространственная сложность может быть достигнута при сохранении оптимальной временной сложности O (n).^[1]

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

В сети выбор может относиться узко к вычислению kнаименьший элемент потока, в этом случае алгоритмы частичной сортировки - с k + O (1) пространство для k самые маленькие элементы - можно использовать, но нельзя использовать алгоритмы, основанные на разделах.

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

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

Связанные проблемы

Можно обобщить проблему выбора, применив ее к диапазонам в списке, что приведет к проблеме диапазон запросов. Вопрос о диапазон медианных запросов (вычисление медиан нескольких диапазонов).

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

Очень немногие языки имеют встроенную поддержку общего выбора, хотя многие предоставляют средства для поиска самого маленького или самого большого элемента списка. Заметным исключением является C ++, который обеспечивает шаблонный nth_element метод с гарантией ожидаемого линейного времени, а также разбивает данные, требуя, чтобы пth элемент должен быть отсортирован в правильное место, элементы перед пth элемент меньше, а элементы после пth элемент больше, чем он. Подразумевается, но не требуется, чтобы он был основан на алгоритме Хоара (или некотором его варианте) в силу требований ожидаемого линейного времени и разделения данных.^[2]^[3]

За Perl, модуль Сортировать :: Ключ :: Вверх, Доступна с CPAN, предоставляет набор функций для выбора первых n элементов из списка с использованием нескольких порядков и пользовательских процедур извлечения ключей. Кроме того, Статистика :: CaseResampling Модуль предоставляет функцию для расчета квантилей с помощью быстрого выбора.

Python стандартная библиотека (начиная с версии 2.4) включает heapq.nsmallest () и nlargest (), возвращая отсортированные списки, за O (п бревно k) время.^[4]

Matlab включает maxk () и норка () функции, которые возвращают максимальные (минимальные) значения k в векторе, а также их индексы.

Потому что языковая поддержка для сортировки является более распространенным, упрощенный подход сортировки с последующим индексированием предпочтителен во многих средах, несмотря на его недостаток в скорости. Действительно, для ленивые языки, этот упрощенный подход может даже обеспечить максимальную сложность для k наименьший / наибольший отсортированный (с максимальным / минимальным в качестве особого случая), если сортировка достаточно ленивая^{[нужна цитата ]}.

Смотрите также

Порядковая оптимизация

Библиография

Блюм, М.; Флойд, Р. В.; Пратт, В.; Ривест, Р. Л.; Тарьян, Р.Э. (Август 1973 г.). «Сроки отбора» (PDF). Журнал компьютерных и системных наук. 7 (4): 448–461. Дои:10.1016 / S0022-0000 (73) 80033-9.CS1 maint: ref = harv (связь)
Флойд, Р. В.; Ривест, Р. Л. (Март 1975 г.). «Ожидаемые сроки отбора». Коммуникации ACM. 18 (3): 165–172. Дои:10.1145/360680.360691.
Кивил, К. С. (2005). «Об алгоритме SELECT Флойда и Ривеста». Теоретическая информатика. 347: 214–238. Дои:10.1016 / j.tcs.2005.06.032.
Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0. Раздел 5.3.3: Выбор минимального сравнения, стр. 207–219.
Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7. Глава 9: Медианы и статистика порядка, стр. 183–196. Раздел 14.1: Динамическая статистика заказов, стр. 302–308.
Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. "Выбирать". Словарь алгоритмов и структур данных.

внешняя ссылка

"Конспект за 25 января 1996 г .: Статистика выбора и заказа ", ICS 161: Разработка и анализ алгоритмов, Дэвид Эппштейн

[1] Лай Т.В., Вуд Д. (1988) Неявный отбор. В: Karlsson R., Lingas A. (eds) SWAT 88. SWAT 1988. Lecture Notes in Computer Science, vol 318. Springer, Berlin, Heidelberg

[2] Раздел 25.3.2 ISO / IEC 14882: 2003 (E) и 14882: 1998 (E)

[3] th_element, SGI STL

[4] ttps://stackoverflow.com/a/23038826

[1]

[2]

[3]

[4]