J'entends par là une structure avec:
- Complexité O (log n) pour les
x.push()
opérations - O (log n) complexité pour trouver un élément
- O (n) complexité à calculer
list(x)
qui sera triée
J'avais également une question connexe sur les performances list(...).insert(...)
dont est maintenant ici .
memcpy
est toujours une opération O (n) . Je ne sais pas comment Python implémente exactement les listes , mais mon pari serait qu'elles sont stockées dans une mémoire contiguë (certainement pas sous forme de liste chaînée). Si tel est bien le cas, l'insertion à l'aide debisect
laquelle vous démontrez aura une complexité O (n) .Réponses:
La liste Python standard n'est triée sous aucune forme. Le module heapq standard peut être utilisé pour ajouter dans O (log n) à une liste existante et supprimer la plus petite de O (log n), mais n'est pas une liste triée dans votre définition.
Il existe différentes implémentations d'arbres équilibrés pour Python qui répondent à vos besoins, par exemple rbtree , RBTree ou pyavl .
la source
Y a-t-il une raison particulière à vos exigences big-O? Ou voulez-vous juste que ce soit rapide? Le module sortedcontainers est pur-Python et rapide (comme dans les implémentations fast-as-C comme blist et rbtree).
La comparaison des performances montre qu'il se compare plus rapidement ou à égalité avec le type de liste triée de blist. Notez également que rbtree, RBTree et PyAVL fournissent des types de dict et d'ensemble triés mais n'ont pas de type de liste triée.
Si la performance est une exigence, n'oubliez pas de toujours faire un benchmark. Un module qui justifie l'affirmation d'être rapide avec la notation Big-O devrait être suspect jusqu'à ce qu'il montre également des comparaisons de référence.
Avertissement: Je suis l'auteur du module Python sortedcontainers.
Installation:
Usage:
la source
0.0845024989976
pour SortedList.add () vs0.596589182518
pour bisect.insort (), donc une différence de 7x en vitesse! Et je m'attends à ce que l'écart de vitesse augmente avec la longueur de la liste puisque le tri par insertion sortedcontainers fonctionne dans O (log n) tandis que bisect.insort () dans O (n).O(n)
Bien que je n'ai toujours jamais vérifié les vitesses "big O" des opérations de base sur les listes Python, le
bisect
module standard mérite probablement également d'être mentionné dans ce contexte:PS. Ah, désolé,
bisect
est mentionné dans la question référencée. Pourtant, je pense que ce ne sera pas beaucoup de mal si cette information sera ici)PPS. Et les listes CPython sont en fait des tableaux (pas, disons, des skplists ou etc.). Eh bien, je suppose qu'ils doivent être quelque chose de simple, mais quant à moi, le nom est un peu trompeur.
Donc, si je ne me trompe pas, les vitesses bissectrice / liste seraient probablement:
Upd. Suite à une discussion dans les commentaires, permettez-moi de lier ici ces questions SO: Comment la liste de Python est-elle implémentée et quelle est la complexité d'exécution des fonctions de liste python
la source
la source
Bien qu'il ne propose pas (encore) de fonction de recherche personnalisée, le
heapq
module peut répondre à vos besoins. Il implémente une file d'attente de tas en utilisant une liste régulière. Vous auriez à écrire votre propre test d'appartenance efficace qui utilise la structure interne de la file d'attente (cela peut être fait en O (log n) , je dirais ...). Il y a un inconvénient: l'extraction d'une liste triée a une complexité O (n log n) .la source
J'utiliserais les modules
biscect
ousortedcontainers
. Je n'ai pas vraiment d'expérience, mais je pense que leheapq
module fonctionne. Il contient unHeap Queue
la source
Il n'est peut-être pas difficile d'implémenter votre propre liste de tri sur Python. Voici une preuve de concept:
========= Résultats ============
[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]
[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]
101
3
50
la source