为什么 coreutils 排序比 Python 慢？

Question

我编写了以下脚本来测试 Python 排序功能的速度：

from sys import stdin, stdout
lines = list(stdin)
lines.sort()
stdout.writelines(lines)

然后，我将其与sort包含 1000 万行的文件上的 coreutils命令进行了比较：

$ time python sort.py <numbers.txt >s1.txt
real    0m16.707s
user    0m16.288s
sys     0m0.420s

$ time sort <numbers.txt >s2.txt 
real    0m45.141s
user    2m28.304s
sys     0m0.380s

内置命令使用了所有四个 CPU（Python 只使用了一个），但运行时间大约是其 3 倍！是什么赋予了？

我使用的是 Ubuntu 12.04.5（32 位）、Python 2.7.3 和sort8.13

Answer 1

Izkata 的评论揭示了答案：特定于语言环境的比较。该sort命令使用环境指示的语言环境，而 Python 默认使用字节顺序比较。比较 UTF-8 字符串比比较字节字符串更难。

$ time (LC_ALL=C sort <numbers.txt >s2.txt)
real    0m5.485s
user    0m14.028s
sys     0m0.404s

那个怎么样。

Answer 2

这两个实现都是用 C 语言实现的，所以那里有一个公平的竞争环境。Coreutilssort 显然使用归并排序算法。Mergesort 执行固定数量的比较，该比较以对数方式增加到输入大小，即大 O (n log n)。

Python 的排序使用独特的混合合并/插入排序timsort，它将与 O(n) 的最佳情况进行可变数量的比较——大概是在已经排序的列表上——但通常是对数的（逻辑上，你对于排序时的一般情况，不能比对数更好）。

给定两种不同的对数排序，在某些特定数据集上，一种可能比另一种更具优势。传统的归并排序不会发生变化，因此无论数据如何，它都会执行相同的操作，但是例如，快速排序（也是对数排序）确实会发生变化，在某些数据上表现更好，但在其他数据上表现更差。

不过，三倍（或大于 3，因为sort是并行化的）的因素相当多，这让我想知道这里是否有一些意外情况，例如sort交换到磁盘（该-T选项似乎暗示它确实如此）。但是，您的低系统与用户时间意味着这不是问题。

Answer 3

这与其说是实际答案，不如说是一种额外的分析，但它似乎确实因要排序的数据而异。首先，一个基础阅读：

$ printf "%s\n" {1..1000000} > numbers.txt

$ time python sort.py <numbers.txt >s1.txt
real    0m0.521s
user    0m0.216s
sys     0m0.100s

$ time sort <numbers.txt >s2.txt
real    0m3.708s
user    0m4.908s
sys     0m0.156s

OK，蟒蛇是多快。但是，您可以sort通过告诉它按数字排序来使 coreutils更快：

$ time sort <numbers.txt >s2.txt 
real    0m3.743s
user    0m4.964s
sys     0m0.148s

$ time sort -n <numbers.txt >s2.txt 
real    0m0.733s
user    0m0.836s
sys     0m0.100s

这要快得多，但 python 仍然以很大的优势获胜。现在，让我们再试一次，但使用 100 万个数字的未排序列表：

$ sort -R numbers.txt > randomized.txt

$ time sort -n <randomized.txt >s2.txt 
real    0m1.493s
user    0m1.920s
sys     0m0.116s

$ time python sort.py <randomized.txt >s1.txt
real    0m2.652s
user    0m1.988s
sys     0m0.064s

coreutilssort -n对于未排序的数值数据更快（尽管您可以调整 python sort 的cmp参数以使其更快）。Coreutilssort在没有-n标志的情况下仍然慢得多。那么，随机字符而不是纯数字呢？

$ tr -dc 'A-Za-z0-9' </dev/urandom | head -c1000000 | 
    sed 's/./&\n/g' > random.txt

$ time sort  <random.txt >s2.txt 
real    0m2.487s
user    0m3.480s
sys     0m0.128s

$ time python sort.py  <random.txt >s2.txt 
real    0m1.314s
user    0m0.744s
sys     0m0.068s

Python 仍然击败 coreutils，但比您在问题中显示的要小得多。令人惊讶的是，在查看纯字母数据时它仍然更快：

$ tr -dc 'A-Za-z' </dev/urandom | head -c1000000 |
    sed 's/./&\n/g' > letters.txt

$ time sort   <letters.txt >s2.txt 
real    0m2.561s
user    0m3.684s
sys     0m0.100s

$ time python sort.py <letters.txt >s1.txt
real    0m1.297s
user    0m0.744s
sys     0m0.064s

同样重要的是要注意，两者不会产生相同的排序输出：

$ echo -e "A\nB\na\nb\n-" | sort -n
-
a
A
b
B

$ echo -e "A\nB\na\nb\n-" | python sort.py 
-
A
B
a
b

奇怪的是，该--buffer-size选项在我的测试中似乎没有太大（或任何）差异。总之，大概是因为在 goldilock 的回答中提到了不同的算法，pythonsort在大多数情况下似乎更快，但数字GNUsort在未排序的数字¹上击败了它。

OP 可能已经找到了根本原因，但为了完整起见，这里是最后的比较：

$ time LC_ALL=C sort   <letters.txt >s2.txt 
real    0m0.280s
user    0m0.512s
sys     0m0.084s


$ time LC_ALL=C python sort.py   <letters.txt >s2.txt 
real    0m0.493s
user    0m0.448s
sys     0m0.044s

¹ _{python-fu 比我应该尝试测试调整list.sort()以查看相同速度的人可以通过指定排序方法来实现。}