coreutilsがPythonよりもソート速度が遅いのはなぜですか？

イズカルタの口コミ答えはロケール別の比較です。コマンドsortは環境に表示されるロケールを使用し、Pythonはデフォルトでバイト順序比較を使用します。 UTF-8文字列を比較するのは、バイト文字列を比較するよりも困難です。

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

どのように。

どちらの実装もCとなっているので、公平な競争の場です。コアツールsort 確かに使用マージソート演算。マージソートは、入力サイズに対して対数的に増加する固定数の比較を実行します。ビッグ(n ログ n).

Pythonのソートは、独自のハイブリッドマージ/挿入ソートを使用します。チームサウター、これはO（n）（おそらくすでにソートされたリストにあります）の最良のシナリオを使用してさまざまな数の比較を実行しますが、通常はログソート（論理的には一般的な場合は数値が良くない）ソートです。

2 つの異なるログランキングが与えられると、一部の特定のデータセットでは、1 つが他のものよりも有利になる可能性があります。従来のマージソートは変更されないため、データに関係なく同じことが行われますが、たとえば、クイックソート（ログソート）は変更され、一部のデータではより良いパフォーマンスが得られますが、他のデータではパフォーマンスが悪くなります。

それにもかかわらず、3回（または並列化されているので3回以上sort）はかなり大きく、ここにディスクに交換するなど、いくつかの偶発的な状況がないかどうか疑問に思いますsort（-Tオプションはそうすることを意味するようです）。しかし、システム時間がユーザー時間に比べて低いという事実は問題ではないことを意味します。

実際の答えではなく、追加の分析に近いですが、ソートされるデータによって異なります。まず、基本的な読み取り：

$ 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はたくさん急いで。ただし、sortcoreutilsに数値順に並べ替えるように指示すると、速度が速くなる可能性があります。

$ 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

coreutilsはsort -nソートされていない数値データに対して高速です（cmpPythonソートパラメータを調整することでより高速にすることはできますが）。このフラグがないと、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

また、2つが同じ整列出力を生成しないことに注意することも重要です。

$ 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の答えで言及されている他のアルゴリズムのために、ほとんどのsort場合、Pythonはより速いようです。数値GNUはソートされていない数字で^1つsort勝ちました。

---

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()}