Discutez de la complexité de diverses méthodes python pour obtenir N éléments les plus importants d'une liste

Question

Je connais deux approches. La première: la documentation est here

heapq.nlargest(n, iterable, key=None) 

et la seconde approche traditionnelle consistant à utiliser triée

sorted(iterable, key=key, reverse=True)[:K] 

La documentation mentionne que ces deux sont équivalents. Cependant, je voulais juste savoir si la complexité des deux est la même ou si la première approche a été implémentée avec moins de complexité dans le temps.

Je me souviens de mon cours d'algorithmes que l'obtention de haut K éléments d'une liste peut être fait dans moins l'ordre des opérations par rapport à trier la liste complète, puis aller avec la cueillette haut K. -moi si je me trompe

Editer: Quelles librairies python standard peuvent effectuer cette tâche dans les opérations O (N) ou quelle est la meilleure complexité que nous pouvons obtenir de Python?

Answer 1

Je ne suis pas un grand mathématicien, mais je suppose que cela devrait dépendre principalement de deux choses:

1. relation entre K et la longueur d'une relation itérables
2. entre la quantité de python et le code CPython réalisé.

En général, vous avez raison, et les tests rapides montrent la différence en nombre:

>>> timeit(stmt='sorted(i)[-100:]', setup='from random import seed,random;seed(666);i=[random() for _ in range(10000)]', number=1000) 
2.086820379132405 
>>> timeit(stmt='heapq.nlargest(n, i)', setup='from random import seed,random;import heapq;seed(666);n=100;i=[random() for _ in range(10000)]', number=1000) 
0.5397011679597199 

Answer 2

Il y a plus d'algorithme rapide QuickSelect qui ne fonctionne pas le tri complet - fait juste partition, et a la complexité moyenne environ O(N).

Merci à @Violet Red Commentaire: numpy.partition

complexité de l'approche du tas est O(NlogK), l'approche de tri est O(NlogN).

C++ STL contient la méthode partial_sort qui peut s'exécuter plus rapidement que le tri complet.

Answer 3

trouver des éléments supérieurs de K, peut être fait avec complexité moindre que O (N * log) avec

• solution à base de segments de mémoire en O (N * log K)
• solution Median of Median en O (N)