J'ai écrit le script suivant pour tester la vitesse de la fonctionnalité de tri de Python:
from sys import stdin, stdout
lines = list(stdin)
lines.sort()
stdout.writelines(lines)
J'ai ensuite comparé cela à la sort
commande coreutils sur un fichier contenant 10 millions de lignes:
$ 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
La commande intégrée a utilisé les quatre processeurs (Python n'en a utilisé qu'un) mais a pris environ 3 fois plus de temps à s'exécuter! Ce qui donne?
J'utilise Ubuntu 12.04.5 (32 bits), Python 2.7.3 et sort
8.13
--buffer-size
pour spécifier l'sort
utilisation de toute la mémoire physique disponible et voir si cela aide?Réponses:
Le commentaire d'Izkata a révélé la réponse: des comparaisons locales spécifiques. La
sort
commande utilise les paramètres régionaux indiqués par l'environnement, tandis que Python utilise par défaut une comparaison de l'ordre des octets. La comparaison de chaînes UTF-8 est plus difficile que la comparaison de chaînes d'octets.Et ça.
la source
locale.strxfrm
pour trier, le script a pris ~ 32 secondes, encore plus vite quesort
mais beaucoup moins.cut
, et d'autres aussi. Sur plusieurs machines , j'ai maintenantexport LC_ALL=C
dans.bashrc
. Mais attention: cela casse essentiellementwc
(saufwc -l
), pour ne citer qu'un exemple. Les "mauvais octets" ne comptent pas du tout ...grep
: vous pouvez obtenir une amélioration substantielle des performances lors de la réception de fichiers volumineux en désactivant UTF-8, en particulier lors de l'exécutiongrep -i
Il s'agit plus d'une analyse supplémentaire que d'une réponse réelle, mais elle semble varier en fonction des données triées. Tout d'abord, une lecture de base:
OK, python est beaucoup plus rapide. Cependant, vous pouvez rendre les coreutils
sort
plus rapides en lui disant de trier numériquement:C'est beaucoup plus rapide mais python gagne toujours par une large marge. Maintenant, réessayons mais avec une liste non triée de numéros 1M:
Le coreutils
sort -n
est plus rapide pour les données numériques non triées (bien que vous puissiez modifier lecmp
paramètre du tri python pour le rendre plus rapide). Coreutilssort
est encore beaucoup plus lent sans le-n
drapeau. Alors, qu'en est-il des caractères aléatoires, pas des nombres purs?Python bat toujours coreutils mais avec une marge beaucoup plus petite que ce que vous montrez dans votre question. Étonnamment, il est encore plus rapide lorsque l'on regarde des données alphabétiques pures:
Il est également important de noter que les deux ne produisent pas la même sortie triée:
Curieusement, l'
--buffer-size
option ne semblait pas faire beaucoup (ou aucune) différence dans mes tests. En conclusion, probablement en raison des différents algorithmes mentionnés dans la réponse de goldilock, le pythonsort
semble être plus rapide dans la plupart des cas, mais GNU numérique lesort
bat sur les nombres non triés 1 .L'OP a probablement trouvé la cause première, mais pour être complet, voici une comparaison finale:
1 Quelqu'un avec plus de python-fu que je devrais essayer de tester l'ajustement
list.sort()
pour voir la même vitesse peut être obtenu en spécifiant la méthode de tri.la source
sort
semble faire un peu de travail supplémentaire pour les comparaisons majuscules / minuscules.stdin
entrée brute . Conversion ceux des numéros (lines = map(int, list(stdin))
) et arrière (stdout.writelines(map(str,lines))
) rend plus lent aller tout le tri, jusqu'à de 0.234s réel 0.720s sur ma machine.Les deux implémentations sont en C, donc des règles du jeu équitables. Coreutils utilise
sort
apparemment l' algorithme de fusion . Mergesort effectue un nombre fixe de comparaisons qui augmente logarithmiquement à la taille d'entrée, c'est-à-dire grand O (n log n).Le tri de Python utilise un tri hybride de fusion / insertion unique, timsort , qui effectuera un nombre variable de comparaisons avec le meilleur des cas O (n) - vraisemblablement, sur une liste déjà triée - mais est généralement logarithmique (logiquement, vous ne peut pas être meilleur que logarithmique pour le cas général lors du tri).
Étant donné deux types logarithmiques différents, l'un pourrait avoir un avantage sur l'autre sur un ensemble de données particulier. Un tri de fusion traditionnel ne varie pas, il fonctionnera donc de la même manière quelles que soient les données, mais par exemple, le tri rapide (également logarithmique), qui varie, fonctionnera mieux sur certaines données mais pire sur d'autres.
Un facteur de trois (ou plus de 3, car il
sort
est parallélisé) est assez important, ce qui me fait me demander s'il n'y a pas de contingence ici, comme le passagesort
au disque (l'-T
option semble impliquer que c'est le cas). Cependant, votre faible temps système vs utilisateur implique que ce n'est pas le problème.la source