A quoi peut servir 'TreeDict' (ou Treemap) en pratique?

Question

Je développe une classe 'TreeDict' en Python. Il s’agit en gros d’un dict qui vous permet de récupérer ses paires clé-valeur dans l’ordre trié, comme pour la classe de collection Treemap en Java.

J'ai implémenté certaines fonctionnalités basées sur la manière dont les index uniques dans les bases de données relationnelles peuvent être utilisés, par exemple. fonctions permettant de récupérer des valeurs correspondant à une plage de clés, des clés supérieures, inférieures ou égales à une valeur particulière dans l’ordre trié, des chaînes ou des nuplets ayant un préfixe spécifique dans l’ordre trié, etc.

Malheureusement, je ne peux penser à aucun problème de la vie réelle qui nécessitera un cours comme celui-ci. Je soupçonne que la raison pour laquelle nous n'avons pas de dict triés en Python est qu'en pratique ils ne sont pas nécessaires assez souvent pour en valoir la peine, mais je veux avoir tort.

Pouvez-vous penser à des applications spécifiques d’un 'TreeDict'? N'importe quel problème de la vie réelle qui serait mieux résolu par cette structure de données? Je veux juste savoir avec certitude si cela en vaut la peine.

Answer 1

C’est utile lorsque vous devez parcourir un dictionnaire dans l’ordre des clés; qui vient à l'occasion. En fait, j'ai trouvé son infiniment plus commun dans certains concours de programmation que n'importe quoi d'autre (pensez ACM, etc.).

La fonctionnalité la plus utile d'un TreeMap est lorsque vous voulez trouver rapidement la clé min ou max; en utilisant un dictionnaire trié, il s’agit souvent d’un seul appel de méthode; et algorithmiquement peut être fait en temps O (log (n)), par opposition à une itération sur chaque clé à la recherche d'un min / max si la collection n'est pas triée. Fondamentalement, une interface beaucoup plus conviviale.

L’un des cas les plus courants que je rencontre est celui où les objets sont identifiés par un nom spécifique et que vous souhaitez imprimer les objets ordonnés en fonction du nom; dire une correspondance entre le nom du répertoire et le nombre de fichiers dans un répertoire.

Un autre endroit où je l’ai utilisé est dans une feuille de calcul Excel; mappage d'un numéro de ligne à un objet de ligne. Cela vous permet de trouver rapidement le dernier index de ligne, sans avoir à parcourir chaque ligne.

En outre, il est utile lorsque vous pouvez facilement définir une relation de comparaison sur des clés, mais pas nécessairement une fonction de hachage, comme requis pour HashMaps. Le meilleur exemple (bien que faible) auquel je puisse penser est celui des clés de chaîne non sensibles à la casse.

Answer 2

J'ai vu plusieurs réponses pointant vers la "séquence ordonnée". fonctionnalité, ce qui est effectivement important, mais aucune ne met en évidence l’autre grande fonctionnalité, à savoir "trouver la première entrée avec une clé" = "ceci". Cela a de nombreuses utilisations même lorsqu'il n'y a pas vraiment besoin de "marcher". à partir de là.

Par exemple (ceci est apparu dans une réponse récente du responsable de la sécurité), disons que vous voulez générer des valeurs pseudo-aléatoires avec des fréquences relatives données, c'est-à-dire qu'un dict d vous est donné. :

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

et ont besoin d’un moyen de générer un «loup» avec une probabilité de 42 sur 100 (puisque 100 est le total des fréquences relatives données), un «mouton» de 15 sur 100, etc. et le nombre de valeurs distinctes peut être assez grand, de même que les fréquences relatives.

Ensuite, stockez les valeurs données (dans n'importe quel ordre) en tant que valeurs dans une arborescence, les clés correspondantes étant la "fréquence cumulée totale". jusqu'à ce point. I.e.:

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

Maintenant, générer une valeur peut être assez rapide ( O (log (len (d))) ), comme suit:

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

où firstGTKey est une méthode qui renvoie la première entrée (avec les attributs .key et .value , dans cet exemple hypothétique) avec un clé > l'argument donné. J'ai utilisé cette approche avec des fichiers volumineux stockés sous forme d'arbres B, par exemple (en utilisant, par exemple, bsddb.bt_open et la méthode set_location ).

Answer 3

La raison pour conserver les éléments dans un ordre de tri est pour une récupération plus rapide. Disons que je voulais toutes les valeurs du dictionnaire dans une plage triée. Ceci est beaucoup plus rapide avec un TreeDict qu'avec le hashmap régulier. En gros, cela vous permet de tout garder dans le dictionnaire dans un ordre trié. Je sais que dans l'application sur laquelle je travaille actuellement, une classe comme celle-ci est utilisée pour interroger la structure de données.

Answer 4

J'utilise souvent Dict < DateTime, someClassOrValue > lors de l'utilisation de processus industriels data-- Ouverture / fermeture de vanne, démarrage / arrêt de la machine, etc.

Le tri des clés est particulièrement utile lorsque je dois comparer les intervalles de temps entre les événements de démarrage / arrêt ou d'ouverture / fermeture dans un délai raisonnable.

Cependant, depuis que j'ai pu utiliser linq en C #, j'ai constaté qu'il est souvent plus simple de travailler avec IEnumerables et d'utiliser les méthodes d'extension IQueryable pour obtenir les informations dont j'ai besoin.

Answer 5

Presque tous " GROUP BY " les rapports nécessitent un dictionnaire trié.

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

Cela se fait si souvent dans les applications d'entreposage de données qu'il est difficile d'exprimer à quel point c'est central.

Si l'appel de fonction trié ne fonctionne pas, cela économise beaucoup de temps à long terme.

Answer 6

Avez-vous vu cela: http://code.activestate.com/recipes/576998/ ?

zuo

Answer 7

Ils peuvent faciliter la mise en œuvre de divers algorithmes.