Интроселект

Интроселект (Мюссер)

Сорт	Алгоритм выбора
Структура данных	Множество
Худшая производительность	На ​ )
Лучшая производительность	На ​ )

Интроселект (Быстрый выбор – Куча)

Сорт	Алгоритм выбора
Структура данных	Множество
Худшая производительность	О нлогн ( )
Лучшая производительность	На ​ )

В информатике , интроселект (сокращение от «интроспективный выбор») — это алгоритм выбора , который представляет собой гибрид и быстрого выбора медианы медиан который имеет быструю среднюю производительность и оптимальную производительность в худшем случае. Introselect связан с introsort алгоритмом сортировки : это аналогичные усовершенствования базовых алгоритмов быстрого выбора и быстрой сортировки , поскольку они оба начинаются с быстрого алгоритма, который имеет хорошую среднюю производительность и низкие накладные расходы, но возвращаются к оптимальному алгоритму для наихудшего случая. (с более высокими накладными расходами), если быстрый алгоритм не выполняется достаточно быстро. Оба алгоритма были представлены Дэвидом Массером в ( Musser 1997 ) с целью предоставить общие алгоритмы для стандартной библиотеки C++ , которые имеют как высокую среднюю производительность, так и оптимальную производительность в худшем случае, что позволяет ужесточить требования к производительности.

Однако в большинстве реализаций стандартной библиотеки C++ используется другой алгоритм «introselect», который сочетает в себе быстрый выбор и heapselect и имеет время выполнения в наихудшем случае O ( n log n ). Проект стандарта C++ по состоянию на 2022 год не содержит требований к производительности в наихудшем случае, поэтому допускает такой выбор.

Алгоритмы

Introsort достигает практической производительности, сравнимой с быстрой сортировкой, сохраняя при этом O ( n log n ) поведение в наихудшем случае за счет создания гибрида быстрой сортировки и пирамидальной сортировки . Introsort начинается с быстрой сортировки, поэтому она достигает производительности, аналогичной быстрой сортировке, если быстрая сортировка работает, и возвращается к пирамидальной сортировке (которая имеет оптимальную производительность в худшем случае), если быстрая сортировка не выполняется достаточно быстро. Аналогичным образом, introselect сочетает в себе быстрый выбор с медианой медиан для достижения линейного выбора в худшем случае с производительностью, аналогичной быстрому выбору.

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

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

Оба подхода ограничивают глубину рекурсии до k ⌈log n ⌉ = O (log n ), а общее время выполнения до O ( n) .

В статье предполагалось, что в ближайшее время будут проводиться дополнительные исследования по интроселекту, но автор ушел на пенсию в 2007 году, так и не опубликовав никаких подобных дальнейших исследований.

См. также

• Алгоритм Флойда – Ривеста

Ссылки

• Массер, Дэвид Р. (1997). «Интроспективные алгоритмы сортировки и отбора» . Программное обеспечение: практика и опыт . 27 (8): 983–993. doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# .