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 sort
comando 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 sort
8.13
--buffer-size
para especificar quesort
use toda a memória física disponível e ver se isso ajuda?Respostas:
O comentário de Izkata revelou a resposta: comparações específicas de localidade. O
sort
comando 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.Que tal isso.
fonte
locale.strxfrm
para classificá-lo, o script levou ~ 32 segundos, ainda mais rápido do quesort
mas muito menos.cut
, e outros também. Em várias máquinas agora tenhoexport LC_ALL=C
em.bashrc
. Mas cuidado: isso essencialmente quebrawc
(excetowc -l
), apenas para citar um exemplo. "Bytes ruins" não são contados ...grep
: você pode obter uma melhoria substancial de desempenho ao receber arquivos enormes desativando o UTF-8, especialmente ao fazêgrep -i
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:
OK, python é muito mais rápido. No entanto, você pode
sort
acelerar o coreutils dizendo para ordenar numericamente: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:
O coreutils
sort -n
é mais rápido para dados numéricos não classificados (embora você possa ajustar ocmp
parâmetro da classificação python para torná-lo mais rápido). Coreutilssort
ainda é significativamente mais lento sem a-n
bandeira. Então, e os caracteres aleatórios, não os números puros?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:
Também é importante observar que os dois não produzem a mesma saída classificada:
Curiosamente, a
--buffer-size
opçã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 pythonsort
parece 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:
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.fonte
sort
parece estar fazendo um pouco de trabalho extra para comparações em maiúsculas / minúsculas.stdin
entrada 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.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 asort
troca para o disco (a-T
opção parece implicar). No entanto, seu baixo sistema versus tempo de usuário implica que esse não é o problema.fonte