Mapeo std :: mapa a Python

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

Sí, hay un módulo bisect de Python, y aunque eso es logarítmico en el momento de la inserción de la misma manera que los árboles binarios de auto-equilibrio son logarítmicos en el momento de la inserción (¿verdad?), Francamente, solo quiero un objeto. Llamado OrderedDict o algo así (y no, Python 3.1 OrderedDict no califica, eso es para el orden de “tiempo de inserción”, y francamente, lo que tiene que ver el orden de tiempo de inserción con el orden no es muy obvio).

Tenga en cuenta que un diccionario ordenado por claves es muy útil en muchas industrias (en finanzas, por ejemplo, es normal hacer un seguimiento de los libros de precios de los datos, que son básicamente diccionarios ordenados de precios -> cantidad, información agregada de pedidos, etc.).

Si alguien tiene alguna otra idea, eso es genial. Todo lo que sé es que acabo de ser cinco millones más inteligente gracias a las “respuestas” de Alex Martelli aquí. Así que pensé en preguntar.

Como dijiste, puedes rodar tu propia implementació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 

hmmm ... parece que ya hice eso por ti, ¡ohh!

Tengo 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 ordenarlas cuando sea necesario. Esto es eficiente debido al comportamiento muy particular del algoritmo de ordenación de python (AKA Timsort). Dictado por llave en Python

Probé su implementación y la mía, y la suya fue la mejor (porque no se inserta en el medio de la lista)

(Le recomiendo encarecidamente que lea el documento vinculado en el comentario de AM sobre el timsort, que es una perla).

Las listas son un sustituto miserable de un árbol.

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

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

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

Los árboles están 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 eso.

Me encontré con esta pregunta que necesitaba un OrderedMap, y encontré para mi horror que la respuesta aceptada es una completa basura. Así que hice mi propio rollo, en caso de que alguien lo encuentre ú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,) 

Podría estar buscando una colección Sorted: http://code.activestate.com/recipes/577197-sortedcollection/

Para una lista que se mantiene ordenada, puede probar el módulo heapq.

El módulo de contenedores ordenados de Python proporciona un tipo de datos SortedDict para estos fines exactamente. Utiliza una estructura de datos de tipo B-tree modificada y está escrito en pure-Python. El módulo tiene 100% de cobertura de prueba y horas de estrés. Aunque es puro Python, es más rápido que las implementaciones en C y tiene una comparación de rendimiento para respaldarlo.

Debido a que es Pure-Python, la instalación es muy sencilla con pip:

 pip install sortedcontainers 

Entonces simplemente:

 from sortedcontainers import SortedDict help(SortedDict) 

La comparación de rendimiento incluye una lista bastante completa de implementaciones alternativas. Vale la pena echarle un vistazo.