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

Я использую подход 5: Merge with Divide And Conquer для решения проблемы сортировки слиянием K в leetcode< /а>. Алгоритм очень быстрый и занимает около 100 мс. Однако я не понимаю, почему подход reduce требует гораздо более медленного времени выполнения (4000+ мс).

Вот разница кода:

# reduce
import functools
return functools.reduce(_mergeTwoLists, lists)

# divide and conquer
step = 1
while step < num:
   for i in range(0, num - step, step * 2):
       lists[i] = _mergeTwoLists(lists[i], lists[i + step])
   step *= 2
   return lists[0]

Если разделяй и властвуй работает в parallel, я могу понять, почему разделяй и властвуй быстрее, но я думал, что он все еще должен работать линейно, верно?

Я также пишу еще одну дорогую версию merge для проверки diff:

  def add(a, b):
       tmp = 0
       for i in range(1, 5000):
           tmp += i
       return a + b

Время работы этой версии reduce и divide and conquer практически идентично.

Есть ли тестовый пример отсортированного списка слияния K, который reduce не может обработать? Есть ли что-то, чего мне не хватает в разделяй и властвуй?


python algorithm fold divide-and-conquer
person Xiaohe Dong    schedule 16.06.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Сложность этих двух подходов различна. Двойное слияние — это O(m+n), где m и n — длины двух списков.

разделяй и властвуй занимает O (log N - log J) итераций (N = общее количество элементов, J = длина подсписков, с которых мы начинаем) каждая итерация составляет O (N), потому что каждый элемент участвует ровно в одном слиянии -> всего O (N (журнал N - журнал J))

сокращение занимает N/J - 1 шагов сложности O(2J), O(3J), O(4J). и т. д., поэтому общая сложность составляет O (N ^ 2 / J)

Обратите внимание, что общее количество двойных слияний одинаково в обоих случаях, разница в том, что разделяй и властвуй в среднем дешевле.

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

person Paul Panzer    schedule 16.06.2018