基于 that answer这是用于合并排序的合并函数的两个版本。 你能帮我理解为什么第二个要快得多吗？ 我已经针对 50000 的列表对其进行了测试，第二个快了 8 倍(Gist)。

def merge1(left, right):
    i = j = inv = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left[i:])

    merged += left[i:]
    merged += right[j:]
    return merged, inv

.

def merge2(array1, array2):
    inv = 0
    merged_array = []
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
            inv += len(array2)
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array, inv

排序函数如下:

def _merge_sort(list, merge):
    len_list = len(list)
    if len_list < 2:
        return list, 0
    middle = len_list / 2
    left, left_inv   = _merge_sort(list[:middle], merge)
    right, right_inv = _merge_sort(list[middle:], merge)
    l, merge_inv = merge(left, right)
    inv = left_inv + right_inv + merge_inv
    return l, inv

.

import numpy.random as nprnd
test_list = nprnd.randint(1000, size=50000).tolist()

test_list_tmp = list(test_list) 
merge_sort(test_list_tmp, merge1)

test_list_tmp = list(test_list) 
merge_sort(test_list_tmp, merge2)

最佳答案

与kreativitea 类似的答案以上，但有更多信息(我认为!)

因此分析实际的合并函数，用于合并两个 50K 数组，

合并1

         311748 function calls in 15.363 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001   15.363   15.363 <string>:1(<module>)
        1   15.322   15.322   15.362   15.362 merge.py:3(merge1)
   221309    0.030    0.000    0.030    0.000 {len}
    90436    0.010    0.000    0.010    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

合并2

         250004 function calls in 0.104 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.104    0.104 <string>:1(<module>)
        1    0.074    0.074    0.103    0.103 merge.py:20(merge2)
    50000    0.005    0.000    0.005    0.000 {len}
   100000    0.010    0.000    0.010    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   100000    0.014    0.000    0.014    0.000 {method 'pop' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}

所以对于 merge1，它是 221309 len，90436 append，耗时 15.363 秒。 所以对于 merge2，它是 50000 len、100000 append 和 100000 pop，耗时 0.104 秒。

len 和 append pop 都是 O(1)(更多信息 here)，所以这些配置文件没有显示什么实际上花时间，因为只是那样，它应该更快，但只有大约 20%。

好吧，如果您只是阅读代码，原因实际上相当明显:

在第一种方法中，有这一行:

inv += len(left[i:])

所以每次调用它时，它都必须重建一个数组。如果您注释掉这一行(或者只是将其替换为 inv += 1 或其他内容)，那么它会比其他方法更快。这是导致时间增加的单行。

注意到这是原因，可以通过改进代码来解决这个问题；将其更改为此以加快速度。这样做之后，会比merge2

inv += len(left) - i

更新为:

def merge3(left, right):
    i = j = inv = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left) - i

    merged += left[i:]
    merged += right[j:]
    return merged, inv

关于python - 为什么那个版本的合并排序更快，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13688084/