Por que coreutils é mais lento que Python?

20

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)

Comparei isso com o sortcomando coreutils 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 usou todas as quatro CPUs (Python usou apenas uma), mas levou cerca de três vezes mais tempo para ser executado! O que da?

Estou usando o Ubuntu 12.04.5 (32 bits), Python 2.7.3 e sort8.13

augurar
fonte
@ goldilocks Sim, é, olhe para o usuário vs em tempo real.
Augurar
Huh - você está certo. Aparentemente, foi paralelizado em coreutils 8.6.
precisa
Você pode usar --buffer-sizepara especificar que sortuse toda a memória física disponível e ver se isso ajuda?
Iruvar
@ 1_CR Tentei com 1 GB de buffer, nenhuma mudança significativa no tempo. Ele usou apenas cerca de 0,6 GB disso, portanto, aumentar ainda mais o tamanho do buffer não ajudaria.
Augurar

Respostas:

22

O comentário de Izkata revelou a resposta: comparações específicas de localidade. O sortcomando usa o código do idioma indicado pelo ambiente, enquanto o Python usa como padrão uma comparação de ordem de bytes. Comparar cadeias de caracteres UTF-8 é mais difícil do que comparar cadeias de bytes.

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

Que tal isso.

augurar
fonte
E como eles se comparam para as cadeias UTF-8?
Gilles 'SO- stop be evil'
@Gilles Modificando o script Python locale.strxfrmpara classificá-lo, o script levou ~ 32 segundos, ainda mais rápido do que sortmas muito menos.
Augurar
3
O Python 2.7.3 está fazendo uma comparação de bytes, mas o Python3 está fazendo uma comparação de palavras unicode. Python3.3 é duas vezes mais lento que Python2.7 para este "teste". A sobrecarga de compactação dos bytes brutos na representação Unicode é ainda maior do que os objetos de compactação já significativos que o Python 2.7.3 precisa executar.
Anthon
2
Eu encontrei o mesmo abrandamento cut, e outros também. Em várias máquinas agora tenho export LC_ALL=Cem .bashrc. Mas cuidado: isso essencialmente quebra wc(exceto wc -l), apenas para citar um exemplo. "Bytes ruins" não são contados ...
Walter Tross 27/11
11
Esse problema de desempenho também ocorre com grep: você pode obter uma melhoria substancial de desempenho ao receber arquivos enormes desativando o UTF-8, especialmente ao fazêgrep -i
Adrian Pronk
7

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

$ 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 é muito mais rápido. No entanto, você pode sortacelerar o coreutils 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 vence por uma ampla margem. Agora, vamos tentar novamente, mas com uma lista não classificada de 1 milhão de números:

$ 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 classificados (embora você possa ajustar o cmpparâmetro da classificação python para torná-lo mais rápido). Coreutils sortainda é significativamente mais lento sem a -nbandeira. Então, e os caracteres aleatórios, não os 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 por uma margem muito menor do que o 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

Curiosamente, a --buffer-sizeopção não pareceu fazer muita (ou nenhuma) diferença nos meus testes. Em conclusão, presumivelmente por causa dos diferentes algoritmos mencionados na resposta do goldilock, o python sortparece ser mais rápido na maioria dos casos, mas o GNU numérico osort supera em números não classificados 1 .


O OP provavelmente encontrou a causa raiz, mas, para fins de completude, 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

1 Alguém com mais python-fu do que eu deveria tentar testar os ajustes list.sort()para ver a mesma velocidade pode ser alcançado especificando o método de classificação.

terdon
fonte
5
A classificação Python possui uma vantagem adicional de velocidade, com base no seu último exemplo: ordem numérica ASCII. sortparece estar fazendo um pouco de trabalho extra para comparações em maiúsculas / minúsculas.
Izkata
@Izkata É isso aí! Veja minha resposta abaixo.
Augurar
11
Na verdade, o python possui um pouco de sobrecarga, criando suas seqüências internas a partir da stdinentrada bruta . Convertendo os aos números ( lines = map(int, list(stdin))) e para trás ( stdout.writelines(map(str,lines))) faz com que toda a ordenação ir mais devagar, até de 0.234s real para 0.720s na minha máquina.
Anthon
6

Ambas as implementações estão em C, portanto, há condições iguais. sort Aparentemente, Coreutils usa o algoritmo mergesort . O Mergesort faz um número fixo de comparações que aumenta logaritmicamente com o tamanho da entrada, ou seja, O grande (n log n).

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

Dados dois tipos logarítmicos diferentes, um pode ter uma vantagem sobre o outro em alguns conjuntos de dados específicos. Uma classificação de mesclagem tradicional não varia, portanto, o mesmo será executado independentemente dos dados, mas, por exemplo, o 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, uma vez que sorté paralelo) é bastante, o que me faz pensar se não há alguma contingência aqui, como a sorttroca para o disco (a -Topção parece implicar). No entanto, seu baixo sistema versus tempo de usuário implica que esse não é o problema.

Cachinhos Dourados
fonte
Bom ponto de vista que ambas as implementações são escritas em C. Tenho certeza de que, se eu implementasse um algoritmo de classificação em Python, seria muito, muito mais lento.
Augurar
A propósito, o arquivo consiste em valores flutuantes gerados aleatoriamente entre 0 e 1, portanto, não deve haver muita estrutura para explorar.
Augurar 24/11