python - python 中的合并排序 - 太慢？

Question

我正在尝试学习合并排序，但我不确定我是否完全正确。它有效，我已经尝试优化它，例如对于 leftpop 使用双端队列，但我仍然得到的时间比内置的 Sorted() 函数慢大约 4 倍。这应该发生吗？或者我错过了一些明显的瓶颈？

import random
from time import time
from collections import deque

unsorted = [random.randint(0, 1000) for r in xrange(101101)]


def merge_sort(unsorted_list):
    length = len(unsorted_list)
    if length <= 1:
        return unsorted_list

    left = unsorted_list[:length / 2]
    right = unsorted_list[length / 2:]

    left_sorted = deque(merge_sort(left))
    right_sorted = deque(merge_sort(right))

    new = []
    while left_sorted and right_sorted:
        if left_sorted[0] < right_sorted[0]:
            new.append(left_sorted.popleft())
            if not left_sorted:
                new += right_sorted
        else:
            new.append(right_sorted.popleft())
            if not right_sorted:
                new += left_sorted
    return new


s = time()
print merge_sort(unsorted)
e = time()
print e - s

s = time()
print sorted(unsorted)
e = time()
print e - s

编辑:下面是一些优化的版本:

def merge_sort(unsorted_list):
    length = len(unsorted_list)
    if length <= 1:
        return unsorted_list

    left = unsorted_list[:length / 2]
    right = unsorted_list[length / 2:]

    left_sorted = deque(merge_sort(left))
    right_sorted = deque(merge_sort(right))

    new = []

    new_append = new.append
    left_pop = left_sorted.popleft
    right_pop = right_sorted.popleft

    while left_sorted and right_sorted:
        if left_sorted[0] < right_sorted[0]:
            new_append(left_pop())
        else:
            new_append(right_pop())

    if not left_sorted:
        new += right_sorted
    if not right_sorted:
        new += left_sorted

    return new

Answer 1

您可以缓存一些名称查找。我看到你经常使用 .append 和 .popleft 。尝试将它们存储在局部变量中:

new_append = new.append
left_pop = left_sorted.popleft
right_pop = right_sorted.popleft

 ...

new_append(left_pop())

...

new_append(right_pop())

这应该消除一些操作码。

此外，您的 if not left_sorted: 和 right_sorted 逻辑可以移到循环之外。

如果您始终使用索引变量 - left[li] 和 right[ri] 而不是 left[0] 和 right[0]，则可能不需要使用出队。一次销毁一个子列表是没有用的。 (但是，我不知道这是否会加快速度。出队可能会缓存开始索引并以这种方式执行。)

最后的 if 语句应该是正数，而不是负数。有可能(甚至可能)同时用完两者。