Является ли quicksort с рандомизированной медианной из трех заметно лучше, чем рандомизированная quicksort?

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

Хорошо известно, что реализация quicksort, которая выбирает свои своды равномерно случайным образом, будет работать в ожидаемом времени O (n lg n) (там есть хорошее доказательство этого в Википедии). Однако из-за стоимости генерации случайных чисел многие реализации quicksort не выбирают случайные колебания, а вместо этого полагаются на "медианный из трех" подход, в котором три элемента выбираются детерминистически и из которых медиана выбирается как стержень. Это, как известно, вырождается в O (n ²) в худшем случае (см. эту замечательную статью о том, как например, для генерации этих наихудших входов).

Теперь предположим, что мы объединим эти два подхода, выбирая три случайных элемента из последовательности и используя их медиану как выбор поворота. Я знаю, что это также гарантирует среднее время выполнения O (n lg n), используя немного другое доказательство, чем одно для обычной рандомизированной быстрой сортировки. Тем не менее, я понятия не имею, что постоянный фактор перед n lg n термином относится к этой конкретной реализации quicksort. Для регулярной рандомизированной быстрой сортировки Wikipedia перечисляет фактическое время выполнения рандомизированных quicksort как требующее не более 1,39 n lg n сравнений (используя lg как двоичный логарифм).

Мой вопрос таков: знает ли кто-нибудь о способе получения постоянного коэффициента для количества сравнений, сделанных с помощью рандомизированной быстрой сортировки "медианная из трех" ? Если мы идем в более общем плане, есть ли выражение для постоянного фактора для быстрой сортировки с использованием рандомизированного подхода медианы k? Мне любопытно, потому что я думаю, было бы интересно узнать, есть ли какое-то "сладкое пятно" этого подхода, что делает меньше сравнений, чем другие рандомизированные реализации quicksort. Я имею в виду, было бы здорово, если бы можно было сказать, что рандомизированная быстродействующая сортировка с рандомизированным выбором медианного шестисегмента позволяет сделать меньшее количество сравнений? Или уметь окончательно сказать, что вы должны просто выбрать элемент поворота наугад?

Ответ 1

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

Я не решаюсь попытаться ответить на ваш смелый вопрос, потому что я могу ответить на ваш "основной" вопрос: асимптотически говоря, нет "сладкого пятна". Суммарная добавленная стоимость вычислений медианов из k элементов, даже элементов O (n ^{1 - ε}), является линейной, а константа для n log n-члена уменьшается с тем, что массив разделяется более равномерно. Улов - это, конечно, константы линейного термина, которые являются эффектно непрактичными, подчеркивая один из недостатков асимптотического анализа.

На основании моих комментариев ниже, я полагаю, что k = O (n ^α) для 0 < α < 1 - это "сладкое пятно".

Ответ 2

Здесь эвристический вывод константы. Я думаю, что это можно сделать строгим, с гораздо большим усилием.

Пусть P - непрерывная случайная величина со значениями в [0, 1]. Интуитивно, P - это доля значений, меньших точки поворота. Мы хотим найти константу c такую, что

c n lg n = E [n + c P n lg (P n) + c (1 - P) n lg ((1 - P) n)].

Немного позже алгебра, мы имеем

c = 1/ E [- P lg P - (1 - P) lg (1 - P))].

Другими словами, c является обратной ожидаемой энтропией распределения Бернулли со средним P. Интуитивно для каждого элемента нам нужно сравнить его с поворотными путями таким образом, чтобы получить около lg n бит информации.

Когда P равномерно, PDF P равен 1. Константа

In[1]:= -1/NIntegrate[x Log[2, x] + (1 - x) Log[2, 1 - x], {x, 0, 1}]

Out[1]= 1.38629

Когда стержень является медианом 3, PDF P равен 6 x (1 - x). Константа

In[2]:= -1/NIntegrate[6 x (1 - x) (x Log[2, x] + (1 - x) Log[2, 1 - x]), {x, 0, 1}]

Out[2]= 1.18825

Ответ 3

Если исходное состояние набора произвольно упорядочено, вы получите тот же постоянный коэффициент для случайного выбора трех элементов для вычисления медианы, как при детерминированном выборе трех элементов.

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

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

Единственный верный способ снизить постоянный коэффициент - увеличить количество элементов, которые вы используете для вычисления медианной величины, но в какой-то момент расчет медианной будет дороже, чем то, что вы получите, получив лучшее медианное значение.

Ответ 4

Да, да. Bentley и McIlroy, авторы C стандартной библиотеки qsort функция, писали в своей статье Создание функции сортировки в следующих номерах:

1.386 n lg n среднее сравнение с использованием первого, среднего или рандомизированного стержня
1.188 n lg n среднее сравнение с использованием медианы 3-х опорных элементов
1.094 n lg n среднее сравнение с использованием медианы из 3 медианных опорных элементов

Согласно приведенному выше документу:

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

Ответ 5

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

В принципе, чтобы выбрать свой элемент сворачивания в качестве элементов медианы-m, вы сортируете эти m элементов, правильно? Поэтому я просто догадываюсь, что одна из констант, которую вы ищете, это "2": путем первой сортировки 3 элементов для выбора вашего стержня вы выполняете сколько дополнительных сравнений? Давайте скажем его 2. Вы делаете это внутри быстрой сортировки снова и снова. Основной вывод состоял бы в том, что медиана-3, следовательно, в 2 раза медленнее, чем простая случайная quicksort.

Но что здесь работает для вас? То, что вы получаете лучшее распределение устройств и поколений, и вы лучше защищены от вырожденного футляра (немного).

Итак, вернемся к моему печально известному вопросу вначале: почему бы не выбрать элемент поворота из медианы-m, m - 5, 7, n/3 или около того. Там должно быть сладкое пятно, где сортировка m-элементов хуже, чем выигрыш от лучшего поведения с разницей и победой и быстрой сортировки. Наверное, это сладкое пятно происходит очень рано - сначала нужно бороться с постоянным коэффициентом 2 сравнений, если вы выберете медианную из 3. Я считаю, что эксперимент стоит, но я бы не слишком ожидал результата:-) Но если я ошибаюсь, и выигрыш огромен: не останавливайтесь на 3!