effiziente funktionelle Datenstruktur für endliche Bijektionen

Question

Ich bin auf der Suche nach einer funktionalen Datenstruktur, die endliche Bijektionen zwischen zwei Arten darstellt, das ist platzsparend und zeiteffizient.

Zum Beispiel würde ich glücklich sein, wenn, eine Bijektion F der Größe n Berücksichtigung

• f mit einem neuen Paar von Elementen erstrecken Komplexität O (ln n) hat
• Abfrage von f (x) oder f^1 (x) hat die Komplexität O (ln n)
• die interne Darstellung für f mehr Raum als mit 2 finite Karten (f darstellen und seine inverse effizient ist)

ich kenne effiziente Darstellung der Permutation s, wie this paper, aber es scheint mein Problem nicht zu lösen.

Answer 1

Bitte werfen Sie einen Blick auf my answer für eine relativ ähnliche Frage. Die provided code kann allgemeine NxM-Beziehungen behandeln, aber auch auf Bijektionen spezialisiert sein (genau wie bei einem binären Suchbaum).

Einfügen die Antwort hier der Vollständigkeit halber:

Der einfachste Weg, ein Paar von unidirektionalen Karten zu verwenden ist. Es kostet etwas, aber Sie werden nicht viel besser (Sie könnten ein bisschen besser mit dedizierten binären Bäumen, aber Sie haben eine große Komplexität Kosten zu zahlen, wenn Sie es selbst implementieren). Im Prinzip sind Suchvorgänge genauso schnell, aber das Hinzufügen und Löschen ist doppelt so lang. Was für eine logarithmische Operation nicht so schlecht ist. Ein weiterer Vorteil dieser Technik besteht darin, dass Sie für den Schlüssel- oder Werttyp spezielle Zuordnungstypen verwenden können, wenn Sie einen verfügbar haben. Sie werden nicht so viel Flexibilität mit einer bestimmten generalistischen Datenstruktur erhalten. Eine andere Lösung besteht darin, einen Quadtree zu verwenden (anstatt eine NxN-Relation als ein Paar von 1xN- und Nx1-Relationen zu betrachten, sehen Sie sie als eine Menge von Elementen im kartesischen Produkt (Key * Value) Ihrer Typen, das heißt ist, eine räumliche Ebene), aber mir ist nicht klar, dass die Zeit- und Speicherkosten besser sind als bei zwei Karten. Ich nehme an, dass es getestet werden muss.

Answer 2

Obwohl es Ihre dritte Anforderung nicht erfüllt, scheinen bimap s wie der Weg zu gehen. (Sie machen nur zwei endliche Karten, eine in jeder Richtung, bequem zu verwenden.)