Mengapa coreutils lebih lambat dari Python?

Saya menulis skrip berikut untuk menguji kecepatan fungsi semacam Python:

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

Saya kemudian membandingkan ini dengan sortperintah coreutils pada file yang berisi 10 juta baris:

$ 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

Perintah bawaan menggunakan keempat CPU (Python hanya menggunakan satu) tetapi membutuhkan waktu sekitar 3 kali lebih lama untuk dijalankan! Apa yang menyebabkannya?

Saya menggunakan Ubuntu 12.04.5 (32-bit), Python 2.7.3, dan sort8.13

Komentar Izkata mengungkapkan jawabannya: perbandingan spesifik-lokal. The sortperintah menggunakan lokal yang ditunjukkan oleh lingkungan, sedangkan default Python untuk perbandingan urutan byte. Membandingkan string UTF-8 lebih sulit daripada membandingkan string byte.

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

Bagaimana tentang itu.

Ini lebih merupakan analisis tambahan daripada jawaban yang sebenarnya tetapi tampaknya bervariasi tergantung pada data yang diurutkan. Pertama, bacaan dasar:

$ 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, python jauh lebih cepat. Namun, Anda dapat membuat core sortlebih cepat dengan menyuruhnya mengurutkan secara numerik:

$ 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

Itu jauh lebih cepat tetapi python masih menang dengan selisih yang lebar. Sekarang, mari kita coba lagi tetapi dengan daftar nomor 1M yang tidak disortir:

$ 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 -nlebih cepat untuk data numerik yang tidak disortir (meskipun Anda mungkin dapat mengubah cmpparameter python sort untuk membuatnya lebih cepat). Coreutils sortmasih jauh lebih lambat tanpa -nflag. Jadi, bagaimana dengan karakter acak, bukan angka murni?

$ 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 masih mengalahkan coreutils tetapi dengan margin yang jauh lebih kecil dari apa yang Anda tunjukkan dalam pertanyaan Anda. Yang mengejutkan, ini masih lebih cepat ketika melihat data alfabet murni:

$ 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

Penting juga untuk dicatat bahwa keduanya tidak menghasilkan output yang diurutkan yang sama:

$ 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

Anehnya, --buffer-sizepilihan itu tampaknya tidak membuat banyak (atau ada) perbedaan dalam tes saya. Sebagai kesimpulan, mungkin karena berbagai algoritma yang disebutkan dalam jawaban goldilock, python sorttampaknya lebih cepat dalam banyak kasus tetapi GNU numeriksort mengalahkannya pada angka ^{1 yang tidak} disortir .

OP mungkin telah menemukan akar penyebabnya tetapi demi kelengkapan, inilah perbandingan terakhir:

$ 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

¹ _{Seseorang dengan lebih banyak python-fu daripada saya harus mencoba menguji tweaking list.sort()untuk melihat dengan kecepatan yang sama dapat dicapai dengan menentukan metode penyortiran.}

Kedua implementasinya ada di C, jadi level playing field di sana. Coreutils sort rupanya menggunakan algoritma mergesort . Mergesort melakukan sejumlah perbandingan tetap yang meningkatkan secara logaritma ke ukuran input, yaitu O besar (n log n).

Penyortiran Python menggunakan penggabungan / penyisipan hibrid unik, timsort , yang akan melakukan sejumlah variabel perbandingan dengan skenario kasus terbaik O (n) - mungkin, pada daftar yang sudah disortir - tetapi umumnya logaritmik (secara logis, Anda tidak bisa lebih baik daripada logaritmik untuk kasus umum saat menyortir).

Dengan dua jenis logaritmik yang berbeda, yang satu dapat memiliki keunggulan di atas yang lain pada beberapa kumpulan data tertentu. Semacam gabungan tradisional tidak bervariasi, sehingga akan melakukan hal yang sama terlepas dari data, tetapi misalnya, quicksort (juga logaritmik), yang memang bervariasi, akan berkinerja lebih baik pada beberapa data tetapi lebih buruk pada yang lain.

Faktor tiga (atau lebih dari 3, karena sortdiparalelkan) agak sedikit, yang membuat saya bertanya-tanya apakah tidak ada beberapa kemungkinan di sini, seperti sortbertukar ke disk ( -Topsi tampaknya menyiratkan itu tidak). Namun, sistem rendah Anda vs waktu pengguna menyiratkan ini bukan masalah.