Gibt es eine effiziente Index persistente Datenstruktur mit mehreren Indizes

Question

Ich bin auf der Suche nach einer effizienten indizierte persistente Datenstruktur. Ich arbeite normalerweise in .NET und bin mir dessen bewusst FSharp die Karte jedoch, dass die Umsetzung und die meisten anderen, die ich kenne, nur einen einzigen ‚Index‘ zur Verfügung stellen, auf der linken Seite der Abbildung.

Im Grunde ist hier das Szenario

public class MyObject
    public int Id { get; }
    public int GroupId { get; }
    public string Name { get; }

Wenn die ID eines Objekt wird hinzugefügt global eindeutiger Satz von Elementen sein. GroupId kann doppelte Werte haben, und ich möchte für alle Werte mit einem passenden GroupId und innerhalb GroupId Namen eindeutig sein wird abfragen können, sondern kann auf verschiedene GroupId die dupliziert werden. Dies ist keine Situation, wo ich einfach einen zusammengesetzten Schlüssel der drei Felder erstellen, wie ich einen unabhängigen Zugang zu den Gruppen der Einzelteile benötigen, basierend auf bestimmten Feldwerte.

Ich kann dies tun, und in der Vergangenheit hat, Wörterbücher des Wörterbücher verwenden, die in anderen Beiträgen hier auf Stackoverflow ... jedoch empfohlen wurden, mag ich auch die Datenstruktur sein, 1) Vollständig Persistent und alles, was bedeutet, 2) effizient in Speicher - was bedeutet, dass Versionen müssen so viele Knoten wie möglich teilen 3) effizient in Änderungen - Ich mag es schnell sein

Ich weiß, dass ich hier für ziemlich viel ich fragen, aber ich wollte auch fragen, zu vermeiden versucht, das Rad neu zu erfinden, wenn es bereits geschehen ist.

Danke

Answer 1

Ich bin nicht sicher, warum an anderer Stelle, und Antworten auf Ihre Frage in bestehenden, empfehlen Personen bestehende Strukturen imbricate. Schupp Strukturen (Karten von Karten, Karten von Listen, Wörterbücher Wörterbücher, ...) für zwei Indizes funktioniert nur, wenn man lockerer ist als die andere (zwei Werte den gleichen Index für Index1 mit impliziert diese beiden Werte den gleichen Index für Index2 haben ), die eine unnötige Einschränkung.

würde ich einen Rekord von Karten verwenden, da viele von ihnen, wie Sie verschiedene Indizes wollen, und ich würde die invariant hält, dass jeder Wert, der in einer Karte vorhanden ist, in allen anderen in demselben Datensatz vorhanden ist. Wert offensichtlich Hinzufügen erfordert es für alle Karten in dem Datensatz hinzufügen. Ähnliches gilt für die Entfernung. Die Invariante kann unmöglich gemacht wird von außen durch Verkapselung zu überschreiten.

Wenn Sie befürchten, dass die in Ihrer Datenstruktur gespeicherten Werte dupliziert werden würde, nicht. Jede Karte würde nur einen Zeiger enthalten. Sie würden alle auf die gleiche Einzel Darstellung des Wertes. Sharing wird so gut sein, wie es bereits mit einfachen Single-indexierte Karten ist.

Answer 2

Wie Sie ein Wörterbuch der Wörterbücher verwenden könnte, erwarte ich, dass z.B. eine F # Karte von Karten kann das sein, was Sie wollen, z.

Map<int, Map<string, MyObject> >  // int is groupid, string is name

vielleicht? Ich bin nicht klar, ob Sie auch einen schnellen Zugriff durch integer ID benötigen.

Sie können auch Clojure Bibliothek überprüfen; Ich weiß nicht viel über Clojure, sondern eine Reihe von effizienten persistenten Datenstrukturen scheint ein von Clojure Stärken zu sein.

Answer 3

Es scheint, dass Sie versuchen, OOP-Prinzipien auf Ihre FP Anwendung anzuwenden.

Wenn Sie in Bezug auf die Funktionen denken, was ist es, was Sie tun wollen?

Wenn Sie eine Liste verwenden, zum Beispiel, man kann es nur sagen wollen Sie alle Objekte ziehen, die eine bestimmte Gruppe Wert haben.

Wenn Sie einen schnellen Zugriff durch Gruppe brauchen Sie eine Karte von Listen, so dass Sie alle Objekte in einer Gruppe nach oben ziehen.

Es gibt verschiedene Datenstrukturen und viele Funktionen, die auf jedem arbeiten, aber Sie sollen zuerst über Ihr Problem von einem funktionellen denken, nicht objektorientiert, POV.