Por que os coreutils são mais lentos que o Python?

Question

Eu escrevi o seguinte script para testar a velocidade da funcionalidade de classificação do Python:

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

Eu então comparei isso com o comando coreutils sort em um arquivo contendo 10 milhões de linhas:

$ 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

O comando interno usava todas as quatro CPUs (o Python usava apenas uma), mas demorava cerca de 3 vezes mais tempo para ser executado! O que dá?

Estou usando o Ubuntu 12.04.5 (32 bits), o Python 2.7.3 e sort 8.13

    

Answer 1

O comentário de Izkata revelou a resposta: localidade comparações específicas. O comando sort usa a localidade indicada pelo ambiente, enquanto o Python usa como padrão uma comparação de ordem de byte. Comparar strings UTF-8 é mais difícil do que comparar strings de bytes.

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

Que tal isso?

    

Answer 2

Esta é mais uma análise extra do que uma resposta real, mas parece variar dependendo dos dados que estão sendo classificados. Primeiro, uma leitura de base:

$ 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, o python é muito mais rápido. No entanto, você pode fazer coreutils sort mais rápido dizendo para ordenar numericamente:

$ 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

Isso é muito mais rápido, mas o Python ainda ganha por uma ampla margem. Agora, vamos tentar novamente, mas com uma lista não classificada de números de 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

O coreutils sort -n é mais rápido para dados numéricos não selecionados (embora você possa ajustar o parâmetro cmp do tipo python para torná-lo mais rápido). Coreutils sort ainda é significativamente mais lento sem o sinalizador -n . Então, e os caracteres aleatórios, não números puros?

$ 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

O Python ainda supera os coreutils, mas com uma margem muito menor do que a que você mostra na sua pergunta. Surpreendentemente, ainda é mais rápido quando se olha para dados alfabéticos puros:

$ 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

Também é importante observar que os dois não produzem a mesma saída classificada:

$ 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

Por incrível que pareça, a opção --buffer-size não pareceu fazer muita diferença (ou nenhuma) nos meus testes. Em conclusão, presumivelmente por causa dos diferentes algoritmos mencionados na resposta de Goldilock, python sort parece ser mais rápido na maioria dos casos, mas numérico GNU sort bate em números não selecionados ¹ .

O OP provavelmente encontrou a causa raiz , mas para fins de integridade, aqui está uma comparação final:

$ 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

¹ _{Alguém com mais python-fu do que eu deveria tentar testar tweaking list.sort() para ver da mesma velocidade pode ser alcançado especificando o método de classificação.}

    

Answer 3

Ambas as implementações estão em C, então há uma igualdade de condições lá. Coreutils sort aparentemente usa o algoritmo do mergesort . O Mergesort faz um número fixo de comparações que aumenta logaritmicamente ao tamanho de entrada, ou seja, grande O (n log n).

A classificação do Python usa um tipo híbrido / de inserção exclusivo, timsort , que fará um número variável de comparações com um O melhor cenário possível de O (n) - presumivelmente, em uma lista já classificada - mas é geralmente logarítmico (logicamente, você não pode ficar melhor do que logarítmico para o caso geral ao ordenar).

Dado dois tipos logarítmicos diferentes, um poderia ter uma vantagem sobre o outro em algum conjunto particular de dados. Uma ordenação de mesclagem tradicional não varia, portanto, ela será executada da mesma forma, independentemente dos dados, mas, por exemplo, quicksort (também logarítmico), que varia, terá um desempenho melhor em alguns dados, mas pior em outros.

Um fator de três (ou mais de 3, desde que sort é paralelizado) é um pouco, o que me faz pensar se não há alguma contingência aqui, como sort trocando para disco (o -T opção parece implicar que faz). No entanto, o seu tempo baixo versus tempo do usuário indica que esse não é o problema.