¿Qué Puede Hacer Un 'TreeDict' (O Treemap) Se Utiliza En La Práctica?

Question

Estoy desarrollando un 'TreeDict' clase en Python.Este es básicamente un diccionario que le permite recuperar sus pares clave-valor en orden, como el Treemap clase de colección en Java.

He aplicado algunas funcionalidad basada en la forma única de los índices en las bases de datos relacionales se pueden utilizar, por ejemplo,funciones para permitir recuperar los valores correspondientes a un intervalo de teclas, teclas de mayor que, menor que o igual a un valor determinado en orden, cadenas o tuplas que tienen un prefijo específico en orden, etc.

Por desgracia, no puedo pensar en cualquier problema de la vida real, que requerirá de una clase como esta.Sospecho que la razón por la que no haya clasificado dicts en Python es que en la práctica no está obligado a menudo lo suficiente como para merecer la pena, pero quiero estar equivocado.

Puede usted pensar en alguna aplicación específica de un 'TreeDict'?Cualquier problema de la vida real que sería mejor resuelto por esta estructura de datos?Sólo quiero saber si esto es digno de él.

Answer 1

Es útil cuando necesita pasar por un Diccionario en orden de teclas; que surge de vez en cuando. De hecho, he encontrado que es infinitamente más común en ciertos concursos de programación que cualquier otra cosa (piense en ACM, etc.).

La característica más útil de un TreeMap es cuando desea encontrar rápidamente la clave mínima o máxima; usando un diccionario ordenado, esto es a menudo una llamada de método único; y algorítmicamente se puede hacer en tiempo O (log (n)), en lugar de iterar sobre cada tecla buscando un mínimo / máximo si la colección no está ordenada. Básicamente, una interfaz mucho más amigable.

Una de las veces más comunes con las que me encuentro es cuando los objetos se identifican por un nombre específico y desea imprimir los objetos ordenados de acuerdo con el nombre; diga una asignación del nombre del directorio al número de archivos en un directorio.

Otro lugar donde lo he usado es en una envoltura de hoja de cálculo de Excel; mapeo del número de fila al objeto de fila. Esto le permite encontrar rápidamente el índice de la última fila, sin recorrer cada fila.

Además, es útil cuando puede definir fácilmente una relación de comparación en las teclas, pero no necesariamente una función de hash, como es necesario para HashMaps. El mejor (aunque débil) ejemplo que se me ocurre son las teclas de cadena que no distinguen entre mayúsculas y minúsculas.

Answer 2

He visto varias respuestas que apunta a "caminar en secuencia ordenada", la cual es realmente importante, pero ninguno destacando la otra gran característica, que es "encontrar la primera entrada con una tecla >= esto".Esto tiene muchos usos, incluso cuando no hay una necesidad real de "caminar" a partir de ahí.

Por ejemplo (esto ocurrió en un reciente PARA responder), dicen que usted quiere generar pseudo-aleatoria de valores con frecuencias relativas -- i.e está dado, por ejemplo, un dict d:

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}

y necesitan una forma de generar 'lobo', con una probabilidad de 42 de cada 100 (ya que 100 es el total de las frecuencias relativas dada), 'oveja' 15 de cada 100, y así sucesivamente;y el número de valores distintos que puede ser bastante grande, como las frecuencias relativas.

A continuación, almacenar los valores dados (en cualquier orden) de los valores de un árbol de mapas, con las claves correspondientes de ser el "total de frecuencias acumuladas" hasta ese punto.I. e.:

def preprocess(d):
    tot = 0
    for v in d:
        tot += d[v]
        treemap.insert(key=tot, value=v)
    return tot, treemap

Ahora, la generación de un valor puede ser bastante rápido (O(log(len(d)))), de la siguiente manera:

def generate(tot, treemap, r=random):
    n = r.randrange(tot)
    return treemap.firstGTkey(n).value

donde firstGTKey es un método que devuelve la primera entrada (con .key y .value atributos, en este ejemplo hipotético) con una clave > el argumento dado.He utilizado este método con grandes archivos almacenados como Árboles B, por ejemplo (usando, por ejemplo, bsddb.bt_open y el set_location el método).

Answer 3

La razón para mantener los elementos ordenados es para una recuperación más rápida. Digamos que quería todos los valores en el diccionario en un rango ordenado. Esto es mucho más rápido con un TreeDict que con el hashmap normal. Básicamente le permite mantener todo en el diccionario en orden ordenado. Sé que en la aplicación en la que estoy trabajando actualmente se usa una clase como esta para consultar básicamente la estructura de datos.

Answer 4

A menudo uso Dict<DateTime, someClassOrValue> cuando trabajo con datos de procesos industriales: Válvula abierta / cerrada, arranque / parada de maquinaria, etc.

Tener las claves ordenadas es especialmente útil cuando necesito comparar intervalos de tiempo entre iniciar / detener o abrir / cerrar eventos en un período de tiempo decente.

Sin embargo, dado que pude usar linq en C #, descubrí que a menudo es más fácil trabajar con IEnumerables y usar los métodos de extensión IQueryable para obtener la información que necesito.

Answer 5

Casi todos " GROUP BY " los informes requieren un diccionario ordenado.

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

Esto se hace con tanta frecuencia en las aplicaciones de almacenamiento de datos, que es difícil expresar cuán central es esto.

Si la llamada a la función sorted no funciona, ahorra un montón de tiempo a largo plazo.

Answer 6

¿Has visto eso: http://code.activestate.com/recipes/576998/ ?

zuo

Answer 7

Pueden facilitar la implementación de varios algoritmos.