Python a-t-il une liste triée?

128

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 .

ilya n.
la source
memcpyest 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 de bisectlaquelle vous démontrez aura une complexité O (n) .
Stephan202
2
Malheureusement pas sorti de la boîte. Mais la bibliothèque sortedcontainers de Grant Jenk est excellente. stackoverflow.com/a/22616929/284795
Colonel Panic

Réponses:

52

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 .

Martin c.Löwis
la source
1
+1 pour rbtree, cela fonctionne très bien (mais contient du code natif; pas du python pur, pas si facile à déployer peut-être)
Sera
12
sortedcontainers est pur-Python et fast-as-C (comme rbtree) avec une comparaison des performances.
GrantJ
"n'est pas une liste triée dans votre définition." Comment?
Colonel Panic
4
heapq ne permet de trouver que le plus petit élément; l'OP demandait une structure qui puisse trouver n'importe quel élément dans O (log n), ce que les tas ne sont pas.
Martin v.Löwis
70

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:

pip install sortedcontainers

Usage:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5
GrantJ
la source
4
En effet j'ai comparé sortedcontainers contre bisect: 0.0845024989976pour SortedList.add () vs 0.596589182518pour 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).
gaborous le
1
@gaborous parce que bisect utilise toujours une liste, donc l'insertion resteO(n)
njzk2
34

Bien que je n'ai toujours jamais vérifié les vitesses "big O" des opérations de base sur les listes Python, le bisectmodule standard mérite probablement également d'être mentionné dans ce contexte:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS. Ah, désolé, bisectest 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:

  • pour un push (): O (n) pour le pire des cas;
  • pour une recherche: si nous considérons que la vitesse d'indexation des tableaux est O (1), la recherche doit être une opération O (log (n));
  • pour la création de liste: O (n) doit être la vitesse de copie de la liste, sinon c'est O (1) pour la même liste)

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
push () doit être dans O (log n) car la liste est déjà triée.
estani le
1
peut-être que j'aurais dû dire "pour une opération d'insertion" . de toute façon, c'était il y a environ un an, alors maintenant je peux facilement mélanger les choses ou manquer quelque chose
ジ ョ ー ジ
Vous pouvez toujours insérer une valeur dans une liste triée en O (log n), voir recherche binaire. push () est défini comme une opération d'insertion.
estani
2
Vrai. Mais alors que trouver l'emplacement d'insertion prendrait en effet O (log n) ops, l'insertion réelle (c'est-à-dire l'ajout de l'élément à la structure de données) dépend probablement de cette structure (pensez à insérer un élément dans un tableau trié). Et comme les listes Python sont en fait des tableaux , cela peut prendre O (n). En raison de la taille limite des commentaires, je vais lier deux questions SO connexes à partir du texte de la réponse (voir ci-dessus).
ジ ョ ー ジ
Bon argument. Je ne savais pas que la liste était gérée comme des tableaux en Python.
estani
7
import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)
Dave31415
la source
l'insert implicite () dans bisect.insort () est O (n)
j314erre
6

Bien qu'il ne propose pas (encore) de fonction de recherche personnalisée, le heapqmodule 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) .

Stephan202
la source
C'est bien mais difficile à couper en deux.
ilya n.
3
Comment peut-il y avoir un test d'appartenance O (log n) dans un tas? Si vous recherchez la valeur x, vous pouvez arrêter de regarder une branche si vous trouvez quelque chose de plus grand que x, mais pour une valeur aléatoire de x, il est probable que 50% se trouve sur une feuille, et vous ne pouvez probablement pas tailler beaucoup.
marchés
1

J'utiliserais les modules biscectou sortedcontainers. Je n'ai pas vraiment d'expérience, mais je pense que le heapqmodule fonctionne. Il contient unHeap Queue

Slass33
la source
0

Il n'est peut-être pas difficile d'implémenter votre propre liste de tri sur Python. Voici une preuve de concept:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= 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

Ventilateur
la source