Pourquoi max est-il plus lent que le tri?

J'ai trouvé que maxc'est plus lent que la sortfonction en Python 2 et 3.

Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

Python 3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

Pourquoi est max ( O(n)) plus lente que la sortfonction ( O(nlogn))?

Vous devez être très prudent lorsque vous utilisez le timeitmodule en Python.

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

Ici, le code d'initialisation s'exécute une fois pour produire un tableau aléatoire a. Ensuite, le reste du code est exécuté plusieurs fois. La première fois, il trie le tableau, mais chaque fois que vous appelez la méthode de tri sur un tableau déjà trié. Seul le temps le plus rapide est renvoyé, vous chronométrez donc en fait le temps qu'il faut à Python pour trier un tableau déjà trié.

Une partie de l'algorithme de tri de Python consiste à détecter lorsque le tableau est déjà partiellement ou complètement trié. Une fois complètement trié, il doit simplement balayer une fois la matrice pour le détecter, puis il s'arrête.

Si à la place vous avez essayé:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

puis le tri se produit sur chaque boucle de synchronisation et vous pouvez voir que le temps de tri d'un tableau est en effet beaucoup plus long que de simplement trouver la valeur maximale.

Edit: la réponse de @ skyking explique la partie que j'ai laissée inexpliquée: a.sort()sait qu'elle travaille sur une liste et peut donc accéder directement aux éléments. max(a)fonctionne sur toute itération arbitraire doit donc utiliser une itération générique.

Tout d'abord, notez qu'il max()utilise le protocole itérateur , tout en list.sort()utilisant un code ad hoc . De toute évidence, l'utilisation d'un itérateur est une surcharge importante, c'est pourquoi vous observez cette différence de temps.

Cependant, à part cela, vos tests ne sont pas équitables. Vous exécutez a.sort()plusieurs fois sur la même liste. L' algorithme utilisé par Python est spécifiquement conçu pour être rapide pour les données déjà (partiellement) triées. Vos tests indiquent que l'algorithme fait bien son travail.

Ce sont des tests équitables:

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a[:])'
1000 loops, best of 3: 227 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a[:].sort()'
100 loops, best of 3: 2.28 msec per loop

Ici, je crée une copie de la liste à chaque fois. Comme vous pouvez le voir, l'ordre de grandeur des résultats est différent: micro- vs millisecondes, comme on pouvait s'y attendre.

Et rappelez-vous: big-Oh spécifie une limite supérieure! La limite inférieure de l'algorithme de tri de Python est Ω ( n ). Être O ( n log n ) n'implique pas automatiquement que chaque exécution prend un temps proportionnel à n log n . Cela n'implique même pas qu'il doit être plus lent qu'un algorithme O ( n ), mais c'est une autre histoire. Ce qu'il est important de comprendre, c'est que dans certains cas favorables, un algorithme O ( n log n ) peut s'exécuter en un temps O ( n ) ou moins.

Cela peut être dû au l.sortfait que est membre de listwhile maxest une fonction générique. Cela signifie que l.sortpeut s'appuyer sur la représentation interne de listwhilemax devra passer par le protocole générique d'itérateur.

Cela fait que chaque élément recherché l.sortest plus rapide que chaque élément extrait quemax fait.

Je suppose que si vous utilisez à la place, sorted(a)vous obtiendrez le résultat plus lentement que max(a).