Действительно ли быстрая сортировка с рандомизированной медианой-тремя заметно лучше, чем рандомизированная быстрая сортировка?

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

---

Основываясь на моих комментариях ниже, я предполагаю, что k = O (n ^α) для 0 <α <1 - «сладкое пятно». </p>

Answer 3

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

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

Answer 4

Да, это так.Бентли и Макилрой, авторы 1002 * стандартной библиотеки qsort функции , написали в своей статье Разработка функции сортировки следующих чисел:

• 1.386 n lg n средних сравнений с использованием первого, среднего или рандомизированного пивота
• 1.188 n lg n средних сравнений с использованием медианы 3 пивот
• 1.094 n lg n средних сравнений с использованием медианы 3pivot медианы

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

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

Answer 5

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

В принципе, чтобы выбрать элемент сводки в качестве элементов median-of-m , вы сортируете эти элементы m , верно? Поэтому я бы просто предположил, что одной из искомых констант является «2»: сначала отсортировав 3 элемента, чтобы выбрать свою опорную точку, вы выполняете сколько дополнительных сравнений? Скажем, его 2. Вы делаете это внутри быстрой сортировки снова и снова. Основной вывод состоит в том, что медиана 3 , следовательно, в 2 раза медленнее, чем простая случайная быстрая сортировка.

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

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