为什么这个 Python 函数对作为字符串包含的整数进行排序比这慢？

Question

我有两个 python 函数用于对作为字符串包含的整数列表进行排序。它们如下：

import random

n = 10000000
unsorted = [str(x) for x in range(n)]
random.shuffle(unsorted)

def sort_alg1(unsorted):
    unsorted.sort(key = lambda x: int(x))
    return unsorted

def sort_alg2(unsorted):
    l=list(map(int,unsorted))
    l.sort()
    s=list(map(str,l))
    return s

print(sort_alg1(unsorted))
print(sort_alg2(unsorted))

两者都按预期工作。然而，根据我的分析器（我使用的是 Robert Kern 的广受欢迎的 line_profiler），第一个函数，即 sort_alg1 的执行速度比 sort_alg2 慢 3 倍多。现在，如果我能查明原因，那将不是什么大问题，但我做不到。我尝试查找内置 sort() 方法和 map() 函数、lambda 等的差异，但都无济于事。如果有人能告诉我为什么会这样，那就太好了！

Answer 1

做一些基准测试：

from timeit import timeit
import random

n = 1_000_000
unsorted = [str(x) for x in range(n)]
random.shuffle(unsorted)


def sort_alg1(unsorted):
    unsorted.sort(key=lambda x: int(x))
    return unsorted


def sort_alg2(unsorted):
    l = list(map(int, unsorted))
    l.sort()
    s = list(map(str, l))
    return s


t1 = timeit(lambda: sort_alg1(unsorted), number=1)
t2 = timeit(lambda: sort_alg2(unsorted), number=1)

print(t1)
print(t2)

打印：

0.4568827738985419
0.2486396620515734

所以看起来 sort_alg2 更快。但原因是 sort_alg2 从 sort_alg1 接收到已经排序的数组。如果稍微更改基准：

t1 = timeit(lambda: sort_alg1(unsorted), number=1)
random.shuffle(unsorted)                      # <---- shufle again the array
t2 = timeit(lambda: sort_alg2(unsorted), number=1)

print(t1)
print(t2)

打印：

0.456114097032696
0.5958397497888654

所以第一个函数更快。

Answer 2

函数 sort_alg1 中的

unsorted.sort 对列表进行适当的排序，这样 sort_alg2 就不会从与 unsorted 列表完全相同的版本开始。此外，一旦 sort_alg2 执行语句 l = list(map(int, unsorted))，如果我们按整数值排序，l 现在是一个完全排序的列表。所以 l.sort() 将在微不足道的时间内达到运行。

注意sort_alg2函数中的assert语句：

import random

n = 10000000
unsorted = [str(x) for x in range(n)]
random.shuffle(unsorted)

def sort_alg1(unsorted):
    unsorted.sort(key = lambda x: int(x))
    return unsorted

def sort_alg2(unsorted):
    l=list(map(int,unsorted))
    # make a copy of l:
    l2 = l.copy()
    l.sort()
    assert(l == l2) # proof!
    s=list(map(str,l))
    return s

sort_alg1(unsorted)
sort_alg2(unsorted)

为什么这个 Python 函数对作为字符串包含的整数进行排序比这慢？

Why is this Python function to sort integers contained as strings slower than this?

python

performance

sorting

profiling

reasoning