☰

为什么 coreutils 排序比 Python 慢？

tag-icon • tag-icon python performance sort coreutils benchmark
为什么 coreutils 排序比 Python 慢？

我编写了以下脚本来测试 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

答案1

伊兹卡塔的评论答案揭晓：特定于语言环境的比较。该sort命令使用环境指示的区域设置，而 Python 默认使用字节顺序比较。比较 UTF-8 字符串比比较字节字符串更难。

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

那个怎么样。

答案2

这两个实现都是用 C 语言实现的，所以这是一个公平的竞争环境。核心工具sort 显然使用归并排序算法。合并排序进行固定数量的比较，这些比较以对数方式增加到输入大小，即大O(n log n)。

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

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

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

答案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

好的，Python 是很多快点。但是，您可以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 仍然以大幅优势获胜。现在，让我们再试一次，但使用 1M 数字的未排序列表：

$ 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 排序的cmp参数以使其更快）。如果没有该标志， Coreutils 的sort速度仍然会慢很多-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在未排序的数字上击败了它1。

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

1比我更懂 python 的人应该尝试测试调整，list.sort()看看通过指定排序方法可以达到相同的速度。

相关内容