SRT Поиск и сортировка Алгоритм
Быстрый выбор
Также: Quickselect · Hoare's selection algorithm · Find · k-я порядковая статистика · медиана медиан · BFPRT · introselect · nth_element
Медиану, любой процентиль, k-й по величине элемент можно найти без сортировки: разбить массив вокруг опорного, как в быстрой сортировке, и продолжить только в той части, где лежит ответ. В среднем это линейное время, а медиана медиан даёт линейное время и в худшем случае. Чем пользуются numpy, C++ и Rust и почему их гарантии разные.
Сколько обычно проходит между двумя землетрясениями силой от 5? В каталоге USGS за 2015–2025 годы 19 072 перерыва между соседними событиями, и средний из них — 5 часов 3 минуты. Но «средний» обманывает: землетрясения ходят толпами, за сильным толчком идут повторные с интервалом в минуты, а потом бывают затишья по двое суток. Типичный перерыв — медиана, половина перерывов короче, половина длиннее. Чтобы её найти, массив обычно сортируют. Ниже её находят, не сортируя.
Медиана — 2 часа 55 минут, на два с лишним часа меньше среднего. Быстрому выбору понадобилось 50 761 сравнение, около 2,7 на элемент. Сортировка сравнениями сделала бы порядка n log₂ n ≈ 271 тысячи. Подвигайте ползунок: десятый процентиль — 9 минут 24 секунды (каждый десятый перерыв короче: так часто толчки идут сериями), девяностый — почти 13 часов, девяносто девятый — 27 часов 39 минут. Каждый процентиль ищется заново, и каждый раз почти весь массив отбрасывается за первые несколько раундов.
Идея
Выберем опорный элемент и разобьём массив, как в быстрой сортировке: меньшие опорного — влево, большие — вправо. После разбиения известно, сколько элементов слева, а значит, в какой части лежит k-й по величине. Вторую часть можно забыть: никакой её элемент ответом быть не может. Повторяем разбиение в оставшейся части, пока она не сожмётся до одного элемента.
Быстрая сортировка после разбиения уходит в обе части, быстрый выбор — только в одну. Отсюда вся разница в цене. У сортировки на каждом уровне рекурсии работают все n элементов, а уровней около log n. У выбора каждый следующий кусок в среднем заметно меньше предыдущего, и работа складывается в убывающую последовательность: n, потом примерно n/2, n/4… — в сумме несколько n. В первой сцене это видно по столбикам раундов: на логарифмической шкале размер куска падает почти ровной лесенкой.
Попутно быстрый выбор делает и полезную работу: после него в позиции k стоит ответ, левее — всё, что не больше, правее — всё, что не меньше. Это и есть частичная упорядоченность, ради которой функция nth_element в C++ и называется так, как называется: она не сортирует, а ставит на место один, n-й, элемент и разбивает вокруг него остальные.
Почему линейно в среднем
Если опорный элемент в каждом раунде выбирается случайно и равновероятно, а разбиение куска длины m стоит не больше cm сравнений, то среднее число сравнений быстрого выбора на любом входе и для любого k не больше 8cn.
Назовём опорный удачным, если он попал в средние две четверти куска по величине: тогда от куска длины m остаётся не больше 3m/4, в какую сторону ни пойти. Удачный опорный выпадает с вероятностью не меньше 1/2.
Разобьём работу на фазы: фаза j — пока длина куска лежит между (3/4)j+1n и (3/4)jn. Удачный раунд обязательно заканчивает фазу, а удачи приходится ждать в среднем не больше двух раундов — как первого орла у монетки, честной или выгоднее. Каждый раунд фазы j стоит не больше c(3/4)jn. Значит, средняя цена фазы — не больше 2c(3/4)jn, а всех фаз вместе — не больше 2cn(1 + 3/4 + 9/16 + …) = 8cn.
Оценка 8n грубая: она нужна, чтобы увидеть линейность, а не константу. Точное среднее посчитал Дональд Кнут: для медианы это около 2(1 + ln 2)n ≈ 3,39n сравнений, а для k у края массива — около 2n. Наша монетка на медиане перерывов дала 2,66n — ей повезло. Нажмите в сцене «тысяча монеток»: на тысяче других запусков среднее выходит 3,42n (разбиение Хоара делает чуть больше сравнений, чем считал Кнут), половина запусков укладывается в 3,31n, самый удачный — в 1,57n, самый неудачный — в 7,14n. Как и у быстрой сортировки, среднее берётся по броскам монетки, а не по входам: плохого входа для случайного опорного нет, бывают только неудачные броски.
Медиана медиан
Неудачные броски маловероятны, но возможны: если опорный раз за разом оказывается почти крайним, кусок уменьшается на один элемент за раунд, и сравнений выходит около n²/2. С детерминированным правилом «первый элемент» или «медиана трёх» такой вход можно и подобрать нарочно — так же, как против быстрой сортировки. Можно ли выбирать опорный так, чтобы худший случай оставался линейным?
Можно, и способ красивый. Разобьём элементы на группы по пять, найдём медиану каждой группы, а потом — тем же алгоритмом, рекурсивно — медиану этих медиан. Её и возьмём опорным.
Медиана медиан групп по пять не меньше чем 3⌈⌈n/5⌉/2⌉ − 6 ≥ 3n/10 − 6 элементов и не больше чем столько же. Поэтому выбор с таким опорным делает O(n) сравнений на любом входе.
Групп ⌈n/5⌉, медиана медиан x не меньше половины медиан групп — не меньше ⌈⌈n/5⌉/2⌉ из них. В каждой такой группе её медиана и два элемента под ней не больше x — по три элемента на группу. Исключим группу самого x и последнюю, неполную: остаётся не меньше 3(⌈⌈n/5⌉/2⌉ − 2) ≥ 3n/10 − 6 элементов, гарантированно не больших x. Симметрично — столько же не меньших. Значит, после разбиения рекурсия получает не больше 7n/10 + 6 элементов.
Время: поиск медиан групп — O(n), поиск медианы медиан — T(n/5), разбиение — O(n), продолжение — не больше T(7n/10 + 6). Получаем T(n) ≤ T(n/5) + T(7n/10 + 6) + an. Доли 1/5 + 7/10 = 9/10 меньше единицы, поэтому подстановка T(m) ≤ Cm проходит индукцией при C ≥ 10a с запасом на константы: работа на каждом следующем уровне рекурсии — не больше 9/10 от предыдущего, и сумма — геометрическая прогрессия.
Почему пять? Группы по три дают гарантию около n/3 с каждой стороны, и доли складываются в 1/3 + 2/3 = 1: работа на всех уровнях одинакова, и выходит O(n log n). Группы по семь тоже работают (1/7 + 5/7 < 1), но медиану семи искать дороже. Пять — самое маленькое нечётное число, при котором сумма долей меньше единицы.
Платить за гарантию приходится константой. Листинг mom ниже ищет ту же медиану перерывов медианой медиан: 187 406 сравнений на входе как в каталоге, 9,8 на элемент — почти вчетверо больше, чем у случайного опорного. На отсортированном и на развёрнутом входе — 6,7n и 10,1n, и за все раунды от куска ни разу не оставалось больше 60 %. Ради этой предсказуемости медиану медиан и держат в библиотеках — но как запасной путь, а не как основной.
Код
Быстрый выбор со случайным опорным и разбиением Хоара — те же числа, что в первой сцене. Генератор случайных чисел свой, чтобы Python и Go выбирали одни и те же опорные.
Строка pieces — размеры куска по раундам: 19 072, 10 739, 10 512, 4236… Второй раунд почти ничего не отрезал — опорный попал к самому краю. Такие раунды и делают среднее больше 2n.
Медиана медиан — ради ясности не на месте, а с новыми списками на каждом шаге. Счётчик учитывает все сравнения, включая сортировку групп и рекурсивный поиск медианы медиан.
Сколько это стоит
| Способ | Среднее | Худший случай | Память |
|---|---|---|---|
| отсортировать и взять k-й | O(n log n) | O(n log n) | как у сортировки |
| быстрый выбор, случайный опорный | O(n), ≈ 3,4n для медианы | O(n²) | O(1) |
| медиана медиан | O(n), ≈ 10n в нашей реализации | O(n) | O(1) на месте |
| introselect | как у быстрого выбора | O(n) или O(n log n) — смотря чем подстрахован | O(1) |
Замер — медиана n случайных чисел. На Python рядом с нашим быстрым выбором — сортировка встроенной sorted и numpy.partition.
На Go выбор обгоняет сортировку в 6 раз на миллионе чисел и в 16 — на четырёх миллионах: разрыв растёт, как и обещает асимптотика. На Python интереснее. Быстрый выбор, написанный на Python, медленнее встроенной сортировки, написанной на C, — вдвое на десятках тысяч чисел, но к миллиону почти догоняет её: логарифм сортировки почти перевешивает разницу языков. А numpy.partition, написанный на C, обгоняет их обоих почти в сорок раз.
Где работает
numpy. Функции numpy.partition и numpy.median выбирают, а не сортируют. Алгоритм по умолчанию называется introselect: быстрый выбор с медианой трёх в роли опорного, а если поиск затянулся — после 2⌊log₂ n⌋ раундов — переход на медиану медиан групп по пять. В комментарии к исходному коду прямо сказано зачем: медиана трёх обычно быстрее всех, но на некоторых входах квадратична, а медиана медиан даёт линейный худший случай. В документации у partition так и записано: худший случай — O(n).
C++. Функция std::nth_element в libstdc++ — тоже introselect: медиана трёх и предел глубины 2⌊log₂ n⌋. Но запасной путь здесь другой — не медиана медиан, а куча: в оставшемся куске нужный элемент находит выбор через кучу, и худший случай получается O(n log n), а не линейный. На обычных данных до запасного пути дело не доходит, так что разница видна только на входах, подобранных нарочно.
Rust. select_nth_unstable устроена как introselect на основе той же схемы, что сортировка sort_unstable, а запасной путь — медиана медиан с выбором опорного «девяткой Тьюки»; документация обещает линейное время на любом входе.
Python и Go. statistics.median в стандартной библиотеке Python просто сортирует данные, а в стандартной библиотеке Go готового выбора нет вовсе — его пишут сами, как в листинге выше. Если нужны k наибольших целиком, а не только k-й, обычно берут кучу из k элементов — см. top-k.
Медианы вместо средних. Процентили задержки сервера, медианная зарплата, медианная цена квартиры — везде, где распределение скошено и среднее тянут вверх редкие большие значения, как затишья тянут вверх средний перерыв между землетрясениями. Задача в конце статьи — ещё одно применение: точка, сумма расстояний от которой до заданных точек наименьшая, — это медиана.
История
Быстрый выбор старше многих сортировок. В июле 1961 года журнал Communications of the ACM напечатал подряд три алгоритма Тони Хоара: Partition, Quicksort и Find. Find — это быстрый выбор: то же разбиение, что у быстрой сортировки, но с продолжением в одной части. К нему Хоар вернулся через десять лет: статья «Proof of a program: FIND» (1971) — подробное доказательство того, что программа Find верна, построенное вместе с самой программой.
Линейный худший случай нашли в 1972–1973 годах Мануэль Блюм, Роберт Флойд, Воган Пратт, Рональд Ривест и Роберт Тарьян: их статья «Time bounds for selection» вышла в Journal of Computer and System Sciences. Алгоритм по первым буквам фамилий называют BFPRT. Четверо из пяти авторов потом получили премию Тьюринга — не за эту работу, а каждый за свою: Флойд, Тарьян, Блюм и Ривест; не получил её только Пратт. В статье есть и вариант, который укладывается в 5,43n сравнений. А в 1975 году Флойд и Ривест опубликовали алгоритм SELECT: он выбирает опорные по небольшой случайной выборке и тратит в среднем n + min(k, n − k) + o(n) сравнений — для медианы около 1,5n, вдвое меньше быстрого выбора.
Introselect — быстрый выбор со страховкой — предложил Дэвид Массер в той же статье 1997 года, что и introsort.
Задачи
Склад на сетке улиц: где поставить точку, чтобы сумма взвешенных расстояний до магазинов была наименьшей. Ответ — медиана, но не та, что кажется сначала, и не среднее.
Склад на сетке улицДанные: Землетрясения: каталог USGS, общественное достояние