Mapping std :: map to Python

Question

A veces tiene sentido tener un diccionario ordenado por teclado. En C++, esto a menudo se implementa con un árbol Rojo-negro. Pero cualquier árbol de búsqueda binaria autoequilibrante servirá (sin embargo, Knuth es particularmente claro en este tema). La mejor solución que he podido encontrar hasta ahora es tomar R. McGraw's AVL-tree type y crear una clase contenedora que básicamente implemente la interfaz de mapa STL (también contando con el práctico orden de pares (dos elementos tuplas) en Python). Tal tupla corresponde básicamente a std :: map :: value_type.

Sí, hay un módulo bisectrónico de Python, y aunque eso es logarítmico en el momento de la inserción de la misma manera que los árboles binarios autoequilibrantes son logarítmicos en el momento de la inserción (¿verdad?), Francamente solo quiero un objeto. Llamado OrderedDict o algo así (y no, el Python 3.1 OrderedDict no califica, eso es para pedidos de "tiempo de inserción" y, francamente, lo que el orden de inserción tiene que ver con ordenar no es del todo obvio).

Nota, un diccionario ordenado por clave es muy útil en muchas industrias (en finanzas, por ejemplo, es común hacer un seguimiento de los precios de los libros de datos, que son básicamente diccionarios ordenados de precio - cantidad, información de orden agregada, etc. .).

Si alguien tiene alguna otra idea, es genial. Todo lo que sé es que acabo de obtener cinco millones de veces más inteligente con las "respuestas" de Alex Martelli. Así que pensé en preguntar.

Answer 1

Como usted ha dicho, puede rodar su propia aplicación con bisect:

class OrderedDict: 
    def __init__(self, keyvalues_iter): 
    self.__srtlst__ = sorted(keyvalues_iter) 
    def __len__(self): 
    return len(self.__srtlst__) 
    def __contains__(self, key): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return True 
    else: 
     return False  
    def __getitem__(self, key): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     raise KeyError(key) 
    def __setitem__(sekf, key, value): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     self.__srtlst__[index][1] = value 
    else: 
     self.__srtlst__[index]=(key, value) 
    def __delitem__(sekf, key, value): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     del __srtlst__[index] 
    else: 
     raise KeyError(key) 
    def __iter__(self): 
    return (v for k,v in self.__srtlst__) 
    def clear(self): 
    self.__srtlst__ = [] 
    def get(self, key, default=None): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     return default 
    def items(self): 
    return self.__srtlst__[:] 
    def iteritems(self): 
    return iter(self.__srtlst__) 
    def iterkeys(self): 
    return (k for k,v in self.__srtlst__) 
    def itervalues(self): 
    return (v for k,v in self.__srtlst__) 
    def keys(self): 
    return [k for k,v in self.__srtlst__] 
    def values(self): 
    return [v for k,v in self.__srtlst__] 
    def setdefault(self, key, default): 
    index = bisect(self.__srtlst__, key) 
    if index<len(self.__srtlst__) and self.__srtlst__[index][0] == key: 
     return self.__srtlst__[index][1] 
    else: 
     self.__srtlst__[index]=(key, default) 
     return default 
    def update(self, other): 
    #a more efficient implementation could be done merging the sorted lists 
    for k, v in other.iteritems(): 
     self[k] = v 

hmmm ... parece que ya lo hice por ti, D'oh!

Answer 2

Obtuve exactamente la misma necesidad, y la respuesta de Alex Martelli me ha convencido por completo: lo mejor es mantener un diccionario y una lista de claves parcialmente ordenadas, luego ordenar cuando sea necesario. Esto es eficiente debido al comportamiento muy particular del algoritmo de ordenación de pitón (AKA Timsort). Key-ordered dict in Python

me puso a prueba su aplicación y la mía y la suya era mejor (porque no se inserta en el medio de la lista)

(Te aconsejo que lea el documento vinculado en el comentario de AM sobre la timsort , que es una perla).

Answer 3

Las listas son un miserable sustituto de un árbol.

Las inserciones necesitan mover toda la lista para hacer espacio; las eliminaciones necesitan mover la lista hacia abajo. Agregar o eliminar cosas en lote está bien cuando es posible, pero a menudo no lo es, o toma contorsiones no naturales para organizarlo. Un atributo fundamental de un árbol es que las inserciones y eliminaciones son O (log n); ninguna cantidad de movimiento manual convertirá O (n) en O (log n).

Insertar un elemento en un árbol cuando ya se sabe a dónde irá es O (1). De forma equivalente, eliminar un elemento de un árbol en función de su nodo también es O (1). std :: map es compatible con ambos. Estos son ambos O (n) con una lista.

Otra propiedad fundamental de un árbol es que la iteración sobre un rango de valores es O (1) por iteración. La combinación de lista y dict pierde esto, porque cada iteración necesita hacer una búsqueda de dict. (El enfoque de lista de tuplas no tiene este problema.)

Los árboles se encuentran entre los tipos de datos más básicos. La falta de Python de un tipo de contenedor de árbol es una verruga. Tal vez haya una biblioteca de terceros implementando una (por ejemplo, la vinculada por el Sr. "Desconocido", que no he probado, por lo que no puedo responder), pero no hay un tipo de Python estándar para ello.

Answer 4

Para obtener una lista que permanece ordenada, puede probar el módulo heapq.

Answer 5

Me encontré con esta pregunta que necesitaba un OrderedMap y descubrí con horror que la respuesta aceptada es basura completa. Así Rodé mi cuenta, en caso de que alguien le resulta útil:

from bisect import * 

class OrderedMap: 
    """Much less efficient than a dict, 
    but keys don't need to be hashable.""" 
    __default_arg = object() 
    def __init__(self, keyvalues_iter = None): 
     self.clear() 
     if keyvalues_iter is not None: 
      self.update(keyvalues_iter) 
    def clear(self): 
     self.__keys = [] 
     self.__values = [] 
    def __index(self, key): 
     if self.__keys: 
      index = bisect(self.__keys, key)-1 
      if self.__keys[index] == key: 
       return index 
     raise KeyError(key) 
    def __len__(self): 
     return len(self.__keys) 
    def __contains__(self, key): 
     try: 
      self.__index(key) 
      return True 
     except KeyError: 
      return False 
    def __getitem__(self, key): 
     index = self.__index(key) 
     return self.__values[index] 
    def __setitem__(self, key, value): 
     try: 
      index = self.__index(key) 
      # exists 
      self.__values[index] = value 
     except KeyError: 
      # new 
      index = bisect(self.__keys, key) 
      self.__keys.insert(index, key) 
      self.__values.insert(index, value) 
    def __delitem__(self, key): 
     index = self.__index(key) 
     self.__keys.pop(index) 
     self.__values.pop(index) 
    def __iter__(self): 
     return iter(self.__keys) 
    def get(self, key, default=__default_arg): 
     try: 
      return self[key] 
     except KeyError: 
      if default != OrderedMap.__default_arg: 
       return default 
      raise 
    def setdefault(self, key, default = None): 
     try: 
      return self[key] 
     except KeyError: 
      if default != OrderedMap.__default_arg: 
       self[key] = default 
       return default 
      raise 
    def items(self): 
     return zip(self.__keys, self.__values) 
    def iteritems(self): 
     return iter((self.__keys[x], self.__values[x]) 
        for x in xrange(len(self))) 
    def keys(self): 
     return self.__keys[:] 
    def iterkeys(self): 
     return iter(self.__keys) 
    def values(self): 
     return self.__values[:] 
    def itervalues(self): 
     return iter(self.__values) 
    def update(self, other): 
     for k, v in other.iteritems(): 
      self[k] = v 
    def __repr__(self): 
     s = ", ".join("%s: %s" % (repr(self.__keys[x]), 
            repr(self.__values[x])) 
         for x in xrange(len(self))) 
     return "OrderedMap{%s}" % (s,) 

Answer 6

Usted podría estar buscando una SortedCollection: http://code.activestate.com/recipes/577197-sortedcollection/

Answer 7

El módulo de Python sortedcontainers ofrece un tipo de datos SortedDict por exactamente estos fines. Utiliza una estructura de datos de tipo árbol B modificado y está escrito en Python puro. El módulo tiene una cobertura de prueba del 100% y horas de estrés. Aunque Python puro, es más rápido que las implementaciones C y tiene un performance comparison para respaldarlo.

Debido a que es puro en Python, la instalación es una brisa con pip:

pip install sortedcontainers 

Entonces sólo tiene que:

from sortedcontainers import SortedDict 
help(SortedDict) 

El performance comparison incluye una lista bastante completa de implementaciones alternativas. Vale la pena echarle un vistazo.