#algorithm #performance #big-o #mergesort
#алгоритм #Производительность #big-o #сортировка слиянием
Вопрос:
Сортировка слиянием — это алгоритм «разделяй и властвуй», который делит входные данные на несколько частей и решает части рекурсивно.
…Существует несколько подходов к функции разделения. Один из способов — разделить посередине. Этот подход обладает некоторыми приятными свойствами, однако мы сосредоточимся на методе, который немного быстрее: четно-нечетное разделение. Идея состоит в том, чтобы поместить каждый элемент с четной позицией в один список, а каждую нечетную позицию в другой.
Это прямо из моих конспектов лекций. Почему именно так происходит, что четно-нечетное разделение происходит быстрее, чем в середине массива?
Я предполагаю, что это как-то связано со списком, передаваемым в сортировку слиянием и имеющим качество уже отсортированного, но я не совсем уверен.
Кто-нибудь может пролить некоторый свет на это?
Редактировать: Я попытался запустить следующее на Python…
global K
K = []
for i in range (1, 100000):
K.append(i)
def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""
t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))
p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))
(Сортировка слиянием — это четно-нечетная сортировка слияния2, которая делится по центру)
И результатом было:
0.771506746608
0.843161219237
Комментарии:
1. Я пытаюсь выяснить, в чем преимущество при объединении отсортированных подсписков обратно вместе … может ли это быть связано с параллелизуемостью алгоритма?
2. Как насчет того, чтобы спросить в cstheory.stackexchange.com
3. Объединение двух отсортированных списков означает повторение списков один раз, поэтому для меня это выглядит как O (n). Не уверен, что слияние можно легко распараллелить. Что касается разделения, я понятия не имею, зачем выделять два вложенных списка, повторять список, перемещать значения в альтернативные списки, проверять, находится ли в конце списка и т.д. И т.п. Может считаться быстрее, чем ‘shr 1’ <g>.
4. Если это взято из ваших конспектов лекций, почему бы просто не спросить своего преподавателя?
5. @Не уверен, что в цитате из ваших заметок нигде не сказано «массив». Вы уверены, что не имеете дело со связанными списками, где преимущество очевидно?
Ответ №1:
Я вижу, что возможно, это лучше, потому что разделение его альтернативными элементами означает, что вам не нужно знать, с какой длины начинается ввод — вы просто берете элементы и помещаете их в чередующиеся списки, пока не закончатся.
Также вы потенциально могли бы начать разделение результирующих списков до того, как закончите перебор по первому списку, если будете осторожны, учитывая лучшую параллельную обработку.
Я должен добавить, что я не эксперт в этих вопросах, это просто то, что пришло на ум…
Комментарии:
1. Другими словами, четно-нечетное разделение может выполняться онлайн , а не оффлайн.
Ответ №2:
Чем ближе входной список к уже сортируемому, тем меньше время выполнения (это потому, что merge процедуре не нужно move вводить какие-либо значения, если все уже находится в правильном порядке; она просто выполняет O (n) сравнений. Поскольку сортировка слиянием рекурсивно вызывает себя для каждой половины разделения, требуется выбрать split функцию, которая увеличивает вероятность того, что результирующие половины списка находятся в отсортированном порядке. Если список в основном отсортирован, четно-нечетное разделение сделает это лучше, чем разделение посередине. Например,
MergeSort([2, 1, 4, 3, 5, 7])
приведет к
Merge(MergeSort([2, 1, 4]), MergeSort([3, 5, 7]))
если мы разделим посередине (обратите внимание, что оба вложенных списка имеют ошибки сортировки), тогда как если бы мы разделили четно-нечетное разделение, мы получили бы
Merge(MergeSort([2, 4, 5]), MergeSort([1, 3, 7]))
что приводит к двум уже отсортированным спискам (и наилучшей производительности для последующих вызовов MergeSort ). Однако, не зная ничего о входных списках, выбор функции разделения не должен асимптотически влиять на время выполнения.
Ответ №3:
Я подозреваю, что в вашем эксперименте есть шум. 🙂 Часть этого может быть вызвана тем, что compare-and-swap фактически не перемещает какие-либо элементы в списке, что позволяет избежать недействительности кэша и т.д.
Несмотря на это, здесь есть чат об этом: https://cstheory.stackexchange.com/questions/6732/why-is-an-even-odd-split-faster-for-mergesort/6764#6764 (и да, я опубликовал там аналогичный ответ (полное раскрытие))
В соответствующих статьях Википедии указывается, что сортировка слиянием равна O ( n log(n) ), в то время как сортировка слиянием по четным нечетам равна O (n log (n) ^ 2 ). Четно-нечетное, безусловно, «медленнее», но сеть сортировки статична, поэтому вы всегда знаете, какие операции собираетесь выполнить и (глядя на рисунок в статье Википедии) обратите внимание, что алгоритм остается параллельным до конца.
Когда сортировка слиянием, наконец, объединяет 2 списка вместе, последние сравнения сети сортировки из 8 элементов для сортировки слиянием по нечетно-четным числам все еще независимы.