Was kann ein ‚TreeDict‘ (Oder Treemap) Für in der Praxis verwendet werden?

Question

Ich entwickle eine 'TreeDict' Klasse in Python. Dies ist ein im Grunde ein dict, die Sie ihre Schlüssel-Wert-Paare in sortierter Reihenfolge abrufen kann, ebenso wie die Treemap Collection-Klasse in Java.

ich einige Funktionen implementiert haben auf dem Weg basierend eindeutige Indizes in relationalen Datenbanken verwendet werden können, beispielsweise Funktionen, die Sie Werte lassen abrufen zu einer Reihe von Tasten entsprechen, Tasten größer als, kleiner als oder gleich einen bestimmten Wert in sortierter Reihenfolge, Strings oder Tupeln, die ein bestimmtes Präfix in sortierter Reihenfolge hat, etc.

Leider kann ich mich kein wirklichen Leben Problem, dass eine Klasse wie diese benötigt. Ich vermute, dass der Grund, warum wir dicts in Python haben nicht sortiert ist, dass sie in der Praxis nicht oft genug erforderlich sein lohnt sich, aber ich will falsch erwiesen.

Kann denken Sie über alle spezifischen Anwendungen eines ‚TreeDict‘? Jeder wirkliche Leben Problem, das sich am besten durch diese Datenstruktur gelöst werden würde? Ich will nur, um sicher wissen, ob es sich lohnt.

Answer 1

Es ist sinnvoll, wenn Sie durch ein Wörterbuch in der Reihenfolge der Tasten gehen müssen; die gelegentlich aufkommt. Ich habe festgestellt, tatsächlich seine unendlich häufiger bei bestimmten Programmierung Wettbewerbe dann alles andere (man denke ACM usw.).

Die nützlichste Funktion eines TreeMap ist, wenn man schnell den Min- oder Max-Taste finden will; mit einem sortierte Wörterbuch dies oft ein einzelner Methodenaufruf; und algorithmisch können in O (log (n)) Zeit durchgeführt werden, im Gegensatz zu über jeder Taste Suche eine Min / Max-Iterieren wenn die Sammlung unsortiert ist. Grundsätzlich ist eine viel freundlicher Schnittstelle.

Eine der häufiger mal ich laufe in es ist, wenn Objekte, die von einem bestimmten Namen identifiziert werden, und Sie wollen aus den Objekten drucken dem Namen geordnet nach; sagt eine Zuordnung von Verzeichnisnamen Anzahl der Dateien in einem Verzeichnis.

Ein weiterer Ort, den ich verwendet habe, ist es in einem Excel-Tabelle Wrapper; Abbildung von Zeilennummer Zeilenobjekt. Auf diese Weise können Sie schnell die letzte Zeile Index finden, ohne durch jede Zeile Looping.

Außerdem ist es hilfreich, wenn Sie leicht einen Vergleich Beziehung auf Schlüssel definieren können, aber nicht notwendigerweise eine Hash-Funktion, wie für HashMaps benötigt. Die besten (wenn auch schwach) Beispiel, das ich denken kann Groß- und Kleinschreibung String-Schlüssel ist.

Answer 2

Ich habe zeigen mehrere Antworten gesehen Funktion der „walk in geordneter Reihenfolge“, die in der Tat wichtig ist, aber keiner das andere große Merkmal hervorheben, die „mit einem Schlüssel finde first entry> = this“ ist. Dies hat viele Anwendungen, auch wenn es gibt keine wirkliche Notwendigkeit, „zu Fuß“ von dort aus.

Zum Beispiel (dies kam kürzlich in einem SO beantworten up), sagen Sie Pseudo-Zufallswerte mit bestimmten relativen Häufigkeiten erzeugt werden soll - das heißt, Sie sind gegeben, sagen wir, ein dict d:

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

und braucht einen Weg ‚Wolf‘ mit einer Wahrscheinlichkeit von 42 von 100 zu erzeugen (da 100 die Summe der relativen Frequenzen gegeben ist), ‚sheep‘ 15 von 100, und so weiter; und die Anzahl der unterschiedlichen Werte können sehr groß sein, genau wie die relativen Häufigkeiten.

Dann speichert die angegebenen Werte (in beliebiger Reihenfolge) als Wert in einer Baumkarte, mit den entsprechenden Tasten als die „Gesamtsummenhäufigkeit“ bis zu diesem Punkt. Das heißt:.

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

Nun kann einen Wert zu erzeugen ziemlich schnell sein (O(log(len(d)))) wie folgt:

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

wobei firstGTKey eine Methode, die den ersten Eintrag zurückgibt (mit .key und .value Attribute, in diesem hypothetischen Beispiel) mit einem Schlüssel> der gegebenen Arguments. Ich habe diesen Ansatz mit großen Dateien wie B-Bäume, zum Beispiel (unter Verwendung von beispielsweise bsddb.bt_open und die set_location Methode).

gespeichert verwendet

Answer 3

Der Grund, die Elemente in sortierter Reihenfolge zu halten, ermöglicht einen schnelleren Abruf ist. Sagen, dass ich alle Werte im Wörterbuch in einem sortierten Bereich gesucht. Das ist viel schneller mit einem TreeDict dann mit dem regulären hashmap. Es ermöglicht im Grunde alles, was man im Wörterbuch in sortierter Reihenfolge zu halten. Ich weiß, dass in der Anwendung, die ich gerade arbeite verwendet eine Klasse wie diese grundsätzlich die Datenstruktur abzufragen.

Answer 4

ich oft verwenden Dict<DateTime, someClassOrValue>, wenn sie mit industriellen Prozess arbeiten data-- Ventil zum Öffnen / Schließen, Maschinen Start / Stop, etc.

Nachdem sortierte der Schlüssel ist besonders nützlich, wenn ich brauche, um die Zeitintervalle zwischen Start / Stopp oder Öffnen / Schließen-Ereignissen in einem angemessenen Betrag von Zeit.

vergleichen

Da ich in der Lage gewesen bin Linq in C # zu verwenden, ich habe festgestellt, dass es oft einfacher, nur mit IEnumerables zu arbeiten und die IQueryable Erweiterungsmethoden verwenden, um die Informationen zu bekommen was ich brauche.

Answer 5

Fast alle "GROUP BY" Berichterstattung erfordert eine sortierte Wörterbuch.

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

Dies wird so oft in Data Warehousing-Anwendungen gemacht, dass es schwierig ist, zum Ausdruck bringen, wie zentral das ist.

Wenn die sorted Funktionsaufruf keine Arbeit tut, es spart eine Menge Zeit auf lange Sicht.

Answer 6

Haben Sie das gesehen: http://code.activestate.com/recipes/576998/

zuo

Answer 7

Sie können verschiedene Algorithmen einfacher zu implementieren machen.