burrahobbit – persistent Datenstrukturen

[name]

Hallo!

Nachdem ich mich in den vergangenen Wochen intensiv mit unveränderbaren Datenstrukturen à la Clojure beschäftigt habe, präsentiere ich euch jetzt das Ergebnis dieser Arbeit: burrahobbit 0.1.0. Dieses erste Release stellt unveränderbare Dictionaries und Sets, bei welchen das Erstellen einer Kopie mit einem geänderten Wert eine Zeit-Komplexität von O(log32 n) – was bei den meisten Datensätzen nahezu äquivalent zu O(1) gehandhabt werden kann, im Vergleich zu O(n) nur zur Erstellung einer Kopie eines regulären Dictionaries, innehat.

Zur Zeit ist es ausgelegt auf und wird getestet mit CPython 2.4 bis 3.2 und PyPy 1.4. Die Internetseite könnt ihr auf GitHub pages finden, lizenziert ist der Code unter der MIT/X11 Lizenz und wird in einem Git-Repositiory auf GitHub gehostet; der Bug-Tracker befindet sich ebenso dort.

Ich wünsche weiterhin einen schönen Tag.

[lunar]

@name: O(log32 n)?!

[BlackJack]

@name: Weder Deine Ankündigung noch die Doku beantworten die IMHO wichtigste Frage: Wo kommt der Name her?

[name]

@name: O(log32 n)?!

Was ist daran denn auszusetzen?

@name: Weder Deine Ankündigung noch die Doku beantworten die IMHO wichtigste Frage: Wo kommt der Name her?

Wenn ich das jetzt so plump und direkt verriete, wäre da nicht der ganze Reiz weg, den so ein eigenartiger Name hat?

[BlackJack]

@name: Die 32 hat in der O-Notation nichts verloren, oder? Gilt nicht O(log_2 n) == O(log_32 n) O(log_m n) == O(log n)?

[cofi]

@name: Die 32 hat in der O-Notation nichts verloren, oder? Gilt nicht O(log_2 n) == O(log_32 n) O(log_m n) == O(log n)?

Ja. Die Basenumrechnung drueckt sich nur in konstanten Faktoren aus und sind damit bzgl der Klasse aequivalent, aber ich seh da jetzt nichts schlimmes darin die Information mitzugeben.

[name]

@name: Die 32 hat in der O-Notation nichts verloren, oder? Gilt nicht O(log_2 n) == O(log_32 n) O(log_m n) == O(log n)?

Ja. Die Basenumrechnung drueckt sich nur in konstanten Faktoren aus und sind damit bzgl der Klasse aequivalent, aber ich seh da jetzt nichts schlimmes darin die Information mitzugeben.

Das stimmt. Ich habe mich mit log32 nach der Diktion der Clojure Dokumentation gehalten, danke jedenfalls für den Hinweis; ich werde mir überlegen, ob ich das abändere.

[sma]

Der konstante Faktor ist schon wichtig, weil er erklärt, warum die "persistent hash trie"-Implementierung fast genau so gut ist, wie eine array-basierte Hashtable.

Wenn hash(k) eine Funktion ist, die jedem Schlüssel k einen Hash h zuordnet, der für jeden Schlüssel anders ist und index(h, l) aus einem Hash h einen Index i für ein Array der Länge l bestimmt, dann kann man mit array[index(hash(key))] einen Wert lesen bzw. entsprechend schreiben. In der Praxis muss man damit umgehen, dass zwei Schlüssel doch unterschiedliche Hashes haben oder unterschiedliche Hashes auf den selben Index abgebildet werden, doch im Prinzip ist es ein Array-Zugriff, daher spricht man von O(1) für den Zugriff auf eine Hashtable.

Dumm nur, dass man das unterliegende Array ändern muss, wenn man die Hashtable ändern will. Als Alternative kann man einen binären Baum zur Speicherung nutzen, und statt seine Knoten zu ändern, einfach immer wieder neue Knoten erzeugen. Abhängig von h wird dann links oder recht geschaut:

Code: Alles auswählen

    def get(ht, key):
        if not ht: return nil
        if key == ht[0]: return ht[1]
        return get(ht[1 if hash(key) < hash(ht[0]) else 2], key)

    def set(ht, key, val):
        if not ht or key == ht[0]: return (key, val)
        if hash(key) < hash(ht[0]):
            return (ht[0], set(ht[1], key, val), ht[2])
        else: return (ht[0], ht[1], set(ht[2], key, val))

Bei idealer Verteilung braucht man bei n=1024 Elementen bis zu 10 Vergleiche, also log2(n). Daher spricht man hier von O(log n) für den Zugriff auf eine TreeMap.

Die Hash Tries von Clojure speichern jedoch pro Knoten nicht nur 2 Kinder, sondern bis zu 32. Dadurch ist der Baum viel flacher. Bei n=1024 Elementen werden nur 2 Vergleiche benutzt,also log32(n). Außerdem müssen so viel weniger Knoten kopiert werden, wenn man neue Objekte speichern will.

Da es eigentlich egal ist, ob nun 1 oder 2 vergleiche stattfinden, liegt das O für n=1024 näher an O(1) als O(log n). Für 1 Million Schlüssel ist der Unterschied 4 zu 20 und auch hier kann man vielleicht noch argumentieren, dass 4 fast so gut wie 1 ist, jedenfalls besser als log n.

Stefan

[name]

…

Ja, deswegen habe ich das 32 auch dringelassen, aber es ist und bleibt ein konstanter Faktor, der eigentlich wegfällt.