O que pode um 'TreeDict' (Ou Treemap) seja usado para na prática?

Question

Estou desenvolvendo uma classe 'TreeDict' em Python. Esta é uma basicamente um dicionário que permite que você recupere seus pares chave-valor na ordem de classificação, assim como a classe de coleção Treemap em Java.

Eu tenho implementado algumas funcionalidades com base na maneira índices únicos em bancos de dados relacionais pode ser usado, por exemplo, funções para deixá-lo recuperar valores correspondentes a um conjunto de chaves, chaves maior que, menor ou igual a um determinado valor na ordem de classificação, cordas ou tuplas que têm um prefixo específico na ordem de classificação, etc.

Infelizmente, eu não posso pensar de qualquer problema da vida real que vai exigir uma classe como este. Eu suspeito que a razão que nós não ter resolvido dicts em Python é que, na prática eles não são obrigados muitas vezes suficiente para valer a pena, mas eu quero ser provado errado.

Você pode pensar em todas as aplicações específicas de um 'TreeDict'? Qualquer problema da vida real que seria melhor resolvido por esta estrutura de dados? Eu só quero saber com certeza se isso vale a pena.

Answer 1

É útil quando você precisa passar por um dicionário na ordem das chaves; que surge na ocasião. Eu realmente encontrou o seu infinitamente mais comum em certos concursos de programação, em seguida, qualquer outra coisa (acho ACM, etc).

O recurso mais útil de um TreeMap é quando você quer encontrar rapidamente a min ou tecla MAX; usando um ordenado dicionário esta é muitas vezes uma única chamada de método; e algoritmos pode ser feito em O (log (n)), em oposição a iteração sobre cada tecla procurando um min / max se a recolha é indiferenciados. Basicamente, uma interface mais amigável muito.

Um dos momentos mais comuns eu me deparo é quando os objetos são identificados por um nome específico, e você quer imprimir os objetos ordenados de acordo com o nome; dizer um mapeamento de nome do diretório para o número de arquivos em um diretório.

Um outro lugar que eu usei ele está em um invólucro planilha excel; mapeamento de número de linha para linha objecto. Isto permite-lhe encontrar rapidamente o último índice de linha, sem loop através de cada linha.

Além disso, é útil quando você pode facilmente definir uma relação de comparação sobre as teclas, mas não necessariamente uma função hash, conforme necessário para HashMaps. A melhor (embora fraco) exemplo que eu posso pensar é caso chaves string insensível.

Answer 2

Já vi várias respostas que apontam para a "caminhada em ordenada seqüência" característica, que é realmente importante, mas nenhum destacando a outra grande característica, que é "encontrar primeira entrada com uma chave> = este". Isto tem muitos usos, mesmo quando não há nenhuma necessidade real para "andar" de lá.

Por exemplo (este surgiu em uma resposta tão recente), digamos que você deseja gerar valores pseudo-aleatórios com dados frequências relativas - isto é, você está dado, digamos, um d dict:

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

e precisa de uma forma de gerar 'lobo' com uma probabilidade de 42 de 100 (uma vez que 100 é a soma das frequências relativas indicadas), 'ovelhas' 15 de 100, e assim por diante; e o número de valores distintos pode ser bastante grande, como podem as frequências relativas.

Em seguida, armazenar os valores dados (em qualquer ordem) como os valores em um mapa de árvore, com as teclas correspondentes sendo a "frequência cumulativa total" até aquele ponto. Ou seja:.

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

Agora, gerando um valor pode ser bastante rápido (O(log(len(d)))), como segue:

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

onde firstGTKey é um método que retorna a primeira entrada (com .key e .value atributos, neste exemplo hipotético) com uma chave> o argumento dado. Eu usei essa abordagem com grandes arquivos armazenados como B-árvores, por exemplo (usando por exemplo o método bsddb.bt_open set_location e).

Answer 3

A razão para manter os elementos na ordem de classificação é para uma mais rápida recuperação. Digamos que eu queria todos os valores no dicionário em um intervalo classificado. Isto é muito mais rápido com um TreeDict em seguida, com o hashmap regular. Ele basicamente permite-lhe manter tudo no dicionário na ordem de classificação. Eu sei que na aplicação que estou trabalhando atualmente em uso uma classe como este para consultar basicamente a estrutura de dados.

Answer 4

Costumo usar Dict<DateTime, someClassOrValue> quando se trabalha com processo industrial data-- Válvula de abrir / fechar, início máquinas / stop, etc.

Ter as chaves classificadas é especialmente útil quando eu preciso comparar intervalos de tempo entre start / stop ou eventos de abrir / fechar em uma quantidade razoável de tempo.

No entanto, desde que eu fui capaz de usar LINQ em C # Descobri que muitas vezes é mais fácil de trabalhar apenas com IEnumerables e usar os métodos de extensão IQueryable para obter a necessidade informações.

Answer 5

Quase todos "GROUP BY" relatórios requer um dicionário ordenado.

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

Isto é feito tantas vezes em Data Warehousing aplicações, que é difícil expressar quão central é isso.

Se a chamada de função sorted não faz nenhum trabalho, ele economiza uma tonelada de tempo no longo prazo.

Answer 6

Você viu que: http://code.activestate.com/recipes/576998/ ?

zuo

Answer 7

Eles podem fazer vários algoritmos mais fácil de implementar.