Dict ordonné par clé en Python
Je cherche une implémentation solide d'un tableau associatif ordonné, c'est-à-dire un dictionnaire ordonné. Je veux la commande en termes de clés, Pas d'ordre d'insertion.
Plus précisément, je cherche une implémentation efficace dans l'espace d'une structure de mappage int-to-float (ou string-to-float pour un autre cas d'utilisation) pour laquelle:
- L'itération ordonnée est O (n)
- L'accès aléatoire est O (1)
Le meilleur que j'ai trouvé était de coller un dict et une liste de clés, garder le dernier commandé avec bisect et insert.
De meilleures idées?
10 réponses
"Random access O (1)" est une exigence extrêmement exigeante qui impose fondamentalement une table de hachage sous-jacente-et j'espère que vous ne voulez dire que des lectures aléatoires, parce que je pense qu'il peut être mathématiquement prouvé qu'il est impossible dans le cas général D'avoir des Écritures O(1) ainsi Qu'une itération ordonnée O(N).
Je ne pense pas que vous trouverez un conteneur préemballé adapté à vos besoins parce qu'ils sont si extrêmes -- L'accès O(log N) ferait bien sûr toute la différence dans le monde. Obtenir le comportement big-O que vous voulez pour les lectures et les itérations, vous devrez coller deux structures de données, essentiellement un dict et un tas (ou une liste triée ou un arbre), et les synchroniser. Bien que vous ne spécifiez pas, je pense que vous obtiendrez seulement amorti comportement du genre que vous voulez - à moins que vous ne soyez vraiment prêt à payer des performances pour les insertions et les suppressions, ce qui est l'implication littérale des spécifications que vous exprimez mais semble une exigence réelle assez improbable.
Au lieu de O (1) Lire et amortized O(N) itération ordonnée, gardez simplement une liste de toutes les clés du côté d'un dict. Par exemple:
class Crazy(object):
def __init__(self):
self.d = {}
self.L = []
self.sorted = True
def __getitem__(self, k):
return self.d[k]
def __setitem__(self, k, v):
if k not in self.d:
self.L.append(k)
self.sorted = False
self.d[k] = v
def __delitem__(self, k):
del self.d[k]
self.L.remove(k)
def __iter__(self):
if not self.sorted:
self.L.sort()
self.sorted = True
return iter(self.L)
Si vous n'aimez pas l'ordre " amorti O (N)", Vous pouvez supprimer self.trié et répétez simplement self.L.sort() dans __setitem__ lui-même. Cela fait des Écritures O (N log n), Bien sûr (alors que j'avais encore des Écritures à O (1)). L'approche est viable et qu'il est difficile de penser à l'un comme intrinsèquement supérieur à l'autre. Si vous avez tendance à faire un tas d'Écritures puis un tas d'itérations puis l'approche dans le le code ci-dessus est le meilleur; si c'est généralement une écriture, une itération, une autre écriture, une autre itération, alors il s'agit d'un lavage.
BTW, cela profite sans vergogne des caractéristiques de performance inhabituelles (et merveilleuses; -) du tri de Python (aka "timsort"): parmi eux, trier une liste qui est la plupart du temps triée mais avec quelques éléments supplémentaires cloués à la fin est fondamentalement O (N) (si les éléments cloués sont assez peu par rapport à la partie préfixe triée). J'ai entendu dire que Java gagnerait ce genre bientôt, comme Josh Block a été tellement impressionné par un discours technique sur le genre de Python qu'il a commencé à le coder pour la JVM sur son ordinateur portable alors et là. La plupart des sytems(y compris je crois Jython à partir d'aujourd'hui et IronPython aussi) ont fondamentalement le tri comme une opération O (N log n), ne profitant pas des entrées "principalement ordonnées"; "Natural mergesort", que Tim Peters a façonné dans le timsort de Python d'Aujourd'hui, est une merveille à cet égard.
Le modulesortedcontainers fournit un typeSortedDict qui répond à vos besoins. Il colle essentiellement un SortedList et le type dict ensemble. Le dict fournit une recherche O (1) et la SortedList fournit une itération O(N) (c'est extrêmement rapide). L'ensemble du module est pur-Python et a graphiques de référence pour sauvegarder les revendications de performance (implémentations fast-as-C). SortedDict est également entièrement testé avec une couverture de 100% et des heures de stress. Il est compatible avec La version 2.6 de Python à 3.4.
Voici ma propre implémentation:
import bisect
class KeyOrderedDict(object):
__slots__ = ['d', 'l']
def __init__(self, *args, **kwargs):
self.l = sorted(kwargs)
self.d = kwargs
def __setitem__(self, k, v):
if not k in self.d:
idx = bisect.bisect(self.l, k)
self.l.insert(idx, k)
self.d[k] = v
def __getitem__(self, k):
return self.d[k]
def __delitem__(self, k):
idx = bisect.bisect_left(self.l, k)
del self.l[idx]
del self.d[k]
def __iter__(self):
return iter(self.l)
def __contains__(self, k):
return k in self.d
L'utilisation de bisect garde soi-même.l ordonné, et l'insertion est O (n) (à cause de l'insertion, mais pas un tueur dans mon cas, parce que j'ajoute beaucoup plus souvent que vraiment insert, donc le cas habituel est amorti O (1)). L'accès est O (1), et l'itération O (n). Mais peut-être que quelqu'un avait inventé (en C) quelque chose avec une structure plus intelligente ?
Un arbre ordonné est généralement meilleur pour ce cas, mais l'accès aléatoire sera log (n). Vous devez tenir compte également des coûts d'insertion et de suppression...
, Vous pouvez construire un dict qui permet la traversée en stockant une paire (value, next_key) dans chaque position.
Accès aléatoire:
my_dict[k][0] # for a key k
Traversée:
k = start_key # stored somewhere
while k is not None: # next_key is None at the end of the list
v, k = my_dict[k]
yield v
Gardez un pointeur sur start et end et vous aurez une mise à jour efficace pour les cas où vous avez juste besoin d'ajouter à la fin de la liste.
L'insertion au milieu est évidemment O (n). Peut - être que vous pourriez construire une liste de saut au-dessus de celui-ci si vous avez besoin de plus de vitesse.
Je ne sais pas dans quelle version python travaillez-vous, mais au cas où vous aimeriez expérimenter, Python 3.1 inclut et implémente officiellement les dictionnaires ordonnés: http://www.python.org/dev/peps/pep-0372/ http://docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries
Le paquet ordereddict ( http://anthon.home.xs4all.nl/Python/ordereddict/) que j'ai implémenté en 2007 inclut sorteddict. sorteddict est un dictionnaire KSO (Key tried Order). Il est implémenté en C et très peu encombrant et plusieurs fois plus rapide qu'une implémentation Python pure. L'inconvénient est que cela ne fonctionne qu'avec CPython.
>>> from _ordereddict import sorteddict
>>> x = sorteddict()
>>> x[1] = 1.0
>>> x[3] = 3.3
>>> x[2] = 2.2
>>> print x
sorteddict([(1, 1.0), (2, 2.2), (3, 3.3)])
>>> for i in x:
... print i, x[i]
...
1 1.0
2 2.2
3 3.3
>>>
Désolé pour la réponse tardive, peut-être que cette réponse peut aider les autres à trouver la bibliothèque.
Voici un pastie: j'avais besoin de quelque chose de similaire. Notez cependant que cette implémentation spécifique est immuable, il n'y a pas d'insertions, une fois l'instance créée: la performance exacte ne correspond pas tout à fait à ce que vous demandez, cependant. La recherche est O (log n) et l'analyse complète est O (n). Cela fonctionne en utilisant le module bisect sur un tuple de paires clé/valeur (tuple). Même si vous ne pouvez pas l'utiliser précisément, vous pourriez avoir un certain succès en l'adaptant à vos besoins.
import bisect
class dictuple(object):
"""
>>> h0 = dictuple()
>>> h1 = dictuple({"apples": 1, "bananas":2})
>>> h2 = dictuple({"bananas": 3, "mangoes": 5})
>>> h1+h2
('apples':1, 'bananas':3, 'mangoes':5)
>>> h1 > h2
False
>>> h1 > 6
False
>>> 'apples' in h1
True
>>> 'apples' in h2
False
>>> d1 = {}
>>> d1[h1] = "salad"
>>> d1[h1]
'salad'
>>> d1[h2]
Traceback (most recent call last):
...
KeyError: ('bananas':3, 'mangoes':5)
"""
def __new__(cls, *args, **kwargs):
initial = {}
args = [] if args is None else args
for arg in args:
initial.update(arg)
initial.update(kwargs)
instance = object.__new__(cls)
instance.__items = tuple(sorted(initial.items(),key=lambda i:i[0]))
return instance
def __init__(self,*args, **kwargs):
pass
def __find(self,key):
return bisect.bisect(self.__items, (key,))
def __getitem__(self, key):
ind = self.__find(key)
if self.__items[ind][0] == key:
return self.__items[ind][1]
raise KeyError(key)
def __repr__(self):
return "({0})".format(", ".join(
"{0}:{1}".format(repr(item[0]),repr(item[1]))
for item in self.__items))
def __contains__(self,key):
ind = self.__find(key)
return self.__items[ind][0] == key
def __cmp__(self,other):
return cmp(self.__class__.__name__, other.__class__.__name__
) or cmp(self.__items, other.__items)
def __eq__(self,other):
return self.__items == other.__items
def __format__(self,key):
pass
#def __ge__(self,key):
# pass
#def __getattribute__(self,key):
# pass
#def __gt__(self,key):
# pass
__seed = hash("dictuple")
def __hash__(self):
return dictuple.__seed^hash(self.__items)
def __iter__(self):
return self.iterkeys()
def __len__(self):
return len(self.__items)
#def __reduce__(self,key):
# pass
#def __reduce_ex__(self,key):
# pass
#def __sizeof__(self,key):
# pass
@classmethod
def fromkeys(cls,key,v=None):
cls(dict.fromkeys(key,v))
def get(self,key, default):
ind = self.__find(key)
return self.__items[ind][1] if self.__items[ind][0] == key else default
def has_key(self,key):
ind = self.__find(key)
return self.__items[ind][0] == key
def items(self):
return list(self.iteritems())
def iteritems(self):
return iter(self.__items)
def iterkeys(self):
return (i[0] for i in self.__items)
def itervalues(self):
return (i[1] for i in self.__items)
def keys(self):
return list(self.iterkeys())
def values(self):
return list(self.itervalues())
def __add__(self, other):
_sum = dict(self.__items)
_sum.update(other.__items)
return self.__class__(_sum)
if __name__ == "__main__":
import doctest
doctest.testmod()
Pour le problème "string to float", vous pouvez utiliser un Trie-il fournit un temps D'accès O(1) et une itération triée O(N). Par "trié", je veux dire "trié par ordre alphabétique par clé" - il semble que la question implique la même chose.
Quelques implémentations (chacune avec ses propres points forts et faibles):
- https://github.com/biopython/biopython a Bio.module trie avec un trie complet; d'autres paquets Trie sont plus mémoire-effcace;
- https://github.com/kmike/datrie - les insertions aléatoires peuvent être lentes, l'alphabet des touches doit être connu à l'avance;
- https://github.com/kmike/hat-trie - Toutes les opérations sont rapides, mais de nombreuses méthodes dict ne sont pas implémentées; la bibliothèque C sous-jacente supporte l'itération triée, mais elle n'est pas implémentée dans un wrapper;
- https://github.com/kmike/marisa-trie - très efficace en mémoire, mais ne supporte pas les insertions; l'itération ne l'est pas trié par défaut mais peut être trié (il y a un exemple dans docs);
- https://github.com/kmike/DAWG - peut être considéré comme un Trie minimisé; très rapide et efficace en mémoire, mais ne supporte pas les insertions; a des limites de taille (plusieurs Go de données)
Voici une option qui n'a pas été mentionnée dans d'autres réponses, je pense:
- Utiliser un arbre de recherche binaire (Treap/AVL/RB) pour garder la cartographie.
- aussi utilisez un HashMap (alias dictionnaire) pour conserver le même mappage (encore).
Cela fournira O(n) traversée ordonnée (via l'arborescence), O(1) accès aléatoire (via le hashmap) et O (log n) insertion / suppression (car vous devez mettre à jour à la fois l'arbre et le hachage).
L'inconvénient est la nécessité de conserver toutes les données deux fois, mais les alternatives qui suggèrent de garder une liste de clés à côté d'un hashmap ne sont pas beaucoup mieux dans ce sens.