create - Dict ordenado por clave en Python

python set

Question

Estoy buscando una implementación sólida de una matriz asociativa ordenada, es decir, un diccionario ordenado. Quiero el pedido en términos de claves, no de orden de inserción.

Más precisamente, estoy buscando una implementación de espacio-efficent de una estructura de mapeo int-to-float (o cadena a flotar para otro caso de uso) para la cual:

• La iteración ordenada es O (n)
• El acceso aleatorio es O (1)

Lo mejor que se me ocurrió fue pegar un dict y una lista de llaves, manteniendo el último ordenado con bisectriz e inserto.

Alguna mejor idea?

Answer 1

"Acceso aleatorio O (1)" es un requisito extremadamente exigente que básicamente impone una tabla hash subyacente, y espero que signifique LECTURAS aleatorias solamente, porque creo que puede ser matemáticamente probado de lo que es imposible en el caso general tener O (1) escribe tan bien como O (N) ordenó la iteración.

No creo que encuentres un contenedor preempaquetado que se adapte a tus necesidades porque son tan extremos: el acceso O (log N) marcaría por supuesto toda la diferencia en el mundo. Para obtener el comportamiento de O grande que desea para lecturas e iteraciones, deberá pegar dos estructuras de datos, esencialmente un diccionario y un montón (o una lista ordenada o un árbol), y mantenerlos sincronizados. Aunque no especifique, creo que obtendrá un comportamiento amortizado del tipo que desea, a menos que esté realmente dispuesto a pagar los hits de rendimiento por inserciones y eliminaciones, que es la implicación literal de las especificaciones que expresa, pero lo hace parece un requisito muy poco probable en la vida real.

Para O (1) lectura y amortización de la iteración ordenada O (N), simplemente mantenga una lista de todas las teclas en el lado de un dict. P.ej:

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 no le gusta la "orden O (N) amortizada", puede eliminar self.sorted y simplemente repetir self.L.sort() en __setitem__ . Eso hace que las escrituras O (N log N), por supuesto (mientras yo todavía tenía escritos en O (1)). Cualquiera de los enfoques es viable y es difícil pensar en uno como intrínsecamente superior al otro. Si tiende a hacer un montón de escrituras y luego un montón de iteraciones, entonces el enfoque en el código anterior es mejor; si es típicamente una escritura, una iteración, otra escritura, otra iteración, entonces es casi un lavado.

Por cierto, esto aprovecha descaradamente las características de rendimiento inusuales (y maravillosas ;-) del tipo de Python (también conocido como "timsort"): entre ellas, ordenar una lista que está principalmente ordenada pero con algunos elementos adicionales añadidos al final es básicamente O (N) (si los elementos añadidos son pocos en comparación con la parte del prefijo ordenado). Escuché que Java gana este tipo pronto, ya que Josh Block quedó tan impresionado por una charla sobre tecnología de Python que comenzó a codificarla para la JVM en su computadora portátil en ese momento. La mayoría de los sistemas (incluso creo que Jython a partir de hoy e IronPython también) básicamente tienen una clasificación como una operación O (N log N), sin aprovechar las entradas "mayormente ordenadas"; "natural mergesort", que Tim Peters diseñó en el timsort de hoy en día de Python, es una maravilla en este sentido.

Answer 2

Aquí está mi propia implementación:

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

El uso de bisect se mantiene ordenado por mí mismo, y la inserción es O (n) (debido a la inserción, pero no es un asesino en mi caso, porque añado mucho más a menudo que realmente insertar, por lo que el caso habitual se amortiza O (1) )). El acceso es O (1) y la iteración O (n). Pero tal vez alguien había inventado (en C) algo con una estructura más inteligente?

Answer 3

Aquí hay una opción que no se ha mencionado en otras respuestas, creo:

• Utilice un árbol de búsqueda binario ( Tr e ap / AVL / RB ) para mantener la asignación.
• También use un hashmap (también conocido como diccionario) para mantener el mismo mapeo (nuevamente).

Esto proporcionará O (n) recorrido ordenado (a través del árbol), O (1) acceso aleatorio (a través del hashmap) y O (registro n) inserción / eliminación (porque necesita actualizar el árbol y el hash).

El inconveniente es la necesidad de mantener todos los datos dos veces, sin embargo, las alternativas que sugieren mantener una lista de claves junto con un hashmap no son mucho mejores en este sentido.

Answer 4

El módulo sortedcontainers proporciona un tipo SortedDict que cumple con sus requisitos. Básicamente pega una SortedList y dict type juntos. El dict proporciona O (1) búsqueda y SortedList proporciona O (N) iteración (es extremadamente rápido). El módulo completo es puro-Python y tiene gráficos de referencia para realizar copias de seguridad de las afirmaciones de rendimiento (implementaciones rápidas como C). SortedDict también se prueba completamente con una cobertura del 100% y horas de estrés. Es compatible con Python 2.6 a 3.4.

Answer 5

El paquete ordereddict ( http://anthon.home.xs4all.nl/Python/ordereddict/ ) que implementé en 2007 incluye sorteddict. sorteddict es un diccionario KSO (Key Sorted Order). Se implementa en C y es muy eficiente en el uso del espacio y varias veces más rápido que una implementación pura de Python. Lo malo es que solo funciona con 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
>>> 

Perdón por la respuesta tardía, tal vez esta respuesta puede ayudar a otros a encontrar esa biblioteca.

Answer 6

No estoy seguro de qué versión de Python está trabajando, pero en caso de que quiera experimentar, Python 3.1 incluye la implementación oficial de diccionarios ordenados: http://www.python.org/dev/peps/pep-0372/ http://docs.python.org/3.1/whatsnew/3.1.html#pep-372-ordered-dictionaries

Answer 7

Para el problema "string to float" puede usar un Trie - proporciona O (1) tiempo de acceso y O (n) iteración ordenada. Por "ordenado" quiero decir "ordenados alfabéticamente por clave", parece que la pregunta implica lo mismo.

Algunas implementaciones (cada una con sus propios puntos fuertes y débiles):

• https://github.com/biopython/biopython tiene el módulo Bio.trie con un Trie completo; otros paquetes de Trie son más eficientes en la memoria;
• https://github.com/kmike/datrie - las inserciones aleatorias pueden ser lentas, las claves del alfabeto deben conocerse de antemano;
• https://github.com/kmike/hat-trie : todas las operaciones son rápidas, pero muchos métodos dict no se implementan; la biblioteca de C subyacente admite la iteración ordenada, pero no está implementada en un contenedor;
• https://github.com/kmike/marisa-trie : muy eficiente desde el punto de vista de la memoria, pero no admite inserciones; la iteración no está ordenada de manera predeterminada, pero puede hacerse ordenada (hay un ejemplo en documentos);
• https://github.com/kmike/DAWG - se puede ver como un Trie minimizado; muy rápido y eficiente en la memoria, pero no admite inserciones; tiene límites de tamaño (varios GB de datos)

Answer 8

Puedes construir un dict que permita el cruce almacenando un par (value, next_key) en cada posición.

Acceso aleatorio:

my_dict[k][0]   # for a key k

Recorrido:

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

Mantenga un puntero para start y end y tendrá una actualización eficiente para aquellos casos en los que solo necesita agregar al final de la lista.

Insertar en el medio es obviamente O (n). Posiblemente pueda construir una lista de omisiones encima si necesita más velocidad.

Answer 9

Un árbol ordenado suele ser mejor para estos casos, pero el acceso aleatorio será log (n). Debes tener en cuenta también los costos de inserción y eliminación ...

Answer 10

aquí hay un pastelito: necesitaba algo similar. Sin embargo, tenga en cuenta que esta implementación específica es inmutable, no hay insertos, una vez que se crea la instancia: sin embargo, el rendimiento exacto no coincide exactamente con lo que está solicitando. La búsqueda es O (log n) y la exploración completa es O (n). Esto funciona usando el módulo bisect sobre una tupla de pares clave / valor (tupla). Incluso si no puede usar esto con precisión, puede tener cierto éxito adaptándolo a sus necesidades.

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()