Judy Array für verwaltete Sprachen

StackOverflow https://stackoverflow.com/questions/550204

Frage

Judy Array schnelle Datenstruktur ist, die einen Sparse-Array oder eine Reihe von Werten darstellen. Gibt es seine Umsetzung für verwaltete Sprachen wie C #? Dank

War es hilfreich?

Lösung

Es ist erwähnenswert, dass diese oft Judy Bäume oder Judy genannt Tries, wenn Sie für sie googeln.

Ich sah auch für eine .NET-Implementierung aber nichts gefunden. Auch erwähnenswert, dass:

Die Umsetzung ist stark um effiziente Cache-Nutzung ausgelegt, als solche Implementierung Besonderheiten auf die Größe bestimmter Konstrukte innerhalb der Teilstrukturen verwendet in hohem Maße abhängig sein kann. Ein .NET verwaltete Implementierung kann etwas anders in dieser Hinsicht.

Es gibt einige bedeutende Hürden dafür, dass ich sehen kann (und es gibt wahrscheinlich mehr, dass meine kurze Scan verpasst)

  • Das API hat einige ziemlich anti OO Aspekte (zum Beispiel ein Null-Zeiger wird als leeren Baum betrachtet) so stark vereinfacht, um den Zustand Zeiger auf die LHS bewegen und Funktionen Instanzmethoden Umwandlung zu C machen ++ nicht funktionieren würde.
  • Die Umsetzung der Unterstrukturen ich machte starken Gebrauch von Zeigern sah. Ich kann nicht diese effizient sehen zu Referenzen in verwalteten Sprachen übersetzt werden.
  • Die Implementierung ist eine Destillation von vielen sehr komplexen Ideen, die die Einfachheit des öffentlichen api täuschen.
  • Die Codebasis ist über 20K Linien (die meisten davon Komplex), das mich nicht als einfach Port schlagen.

Sie können die Bibliothek nehmen und den C-Code in C ++ / CLI wickeln (wahrscheinlich einfach intern einen Zeiger hält, die die c api trie ist und mit allen c Anrufe zu diesem einen Punkt). Dies würde eine vereinfachte Implementierung aber die verknüpften Bibliotheken für die native Implementierung kann problematisch sein (wie es Speicherzuweisung). Sie müßten wahrscheinlich auch mit der Umwandlung von .Net Strings Plain Old Byte * auf dem Übergang als auch (oder gerade arbeiten mit Bytes direkt)

beschäftigen

Andere Tipps

Judy wirklich paßt nicht gut mit verwalteten Sprachen. Ich glaube nicht, Sie in der Lage sein werden so etwas wie SWIG zu verwenden und die erste Schicht automatisch getan.

Ich schrieb PyJudy und ich landete mit einigen nicht-trivialen API Änderungen vornehmen passen gut in Python. Zum Beispiel schrieb ich in der Dokumentation:

  

JudyL Arrays Karte Maschine Worte   Maschine Worte. In der Praxis der Worte   speichern ganze Zahlen ohne Vorzeichen oder Zeiger.   PyJudy unterstützt alle vier Zuordnungen als   verschiedene Klassen.

  • pyjudy.JudyLIntInt - Karte ohne Vorzeichen integer Tasten unsigned integer Werte
  • pyjudy.JudyLIntObj - Karte ohne Vorzeichen integer Schlüssel zu Python Objektwerte
  • pyjudy.JudyLObjInt - Karte Python Objektschlüssel zu unsigned integer Werte
  • pyjudy.JudyLObjObj - Karte Python Objektschlüssel zu Python Objektwerte

Ich habe nicht auf den Code für ein paar Jahre sah so meine Erinnerungen über sie ziemlich trüb sind. Es war meine erste Python-Erweiterungsbibliothek, und ich erinnere mich, ich gehackt zusammen eine Art Template-System für die Codegenerierung. Heute würde ich so etwas wie genshi verwenden.

Ich kann nicht auf Alternativen zu Judy Punkt -, dass ein Grund ist, warum ich bin auf der Suche Stackoverflow

.

Edit:. Ich habe gesagt, dass mein Timing Nummern in der Dokumentation sind ab von dem, was Judys Dokumentation schlägt vor, weil Judy für 64-Bit-Cache-Zeilen entwickelt und mein Powerbook war nur 32 Bits

Einige andere Verbindungen:

Der letzte Vergleich Nummern für verschiedene High-Performance-Trie-Implementierungen hat.

Dies erweist sich schwieriger als ich dachte. PyJudy könnte einen Blick wert sein, wie Tie :: Judy . Es gibt etwas auf Softpedia und etwas Rubin-ish . Das Problem ist, keine von diesen speziell .NET.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top