struttura efficiente dei dati funzionali per le biiezioni finite

Question

Sto cercando una struttura dati funzionale che rappresenti le biografie finite tra due tipi, che sia efficiente in termini di spazio ed efficiente nel tempo.

Ad esempio, sarei felice se, considerando una biiezione f di dimensione n:

• estendentesi f con un nuovo paio di elementi ha complessità O (ln n)
• interrogazione f (x) o f^-1 (x) ha complessità o (ln n)
• la rappresentazione interna di f è più efficiente dello spazio che avere 2 mappe finiti (che rappresenta f e la sua inversa)

sono consapevole rappresentazione efficiente della permutazione s, come this paper, ma non sembra risolvere il mio problema.

Answer 1

Si prega di dare un'occhiata a my answer per una domanda relativamente simile. Lo provided code è in grado di gestire relazioni NxM generali, ma è anche specializzato in sole biiezioni (proprio come si farebbe per un albero di ricerca binario).

Incollare la risposta per completezza:

Il modo più semplice è quello di utilizzare un paio di mappe unidirezionali. Ha un certo costo, ma non migliorerai molto (potresti ottenere un po 'meglio usando gli alberi binari dedicati, ma hai un enorme costo per la complessità se devi implementarlo tu stesso). In sostanza, le ricerche saranno altrettanto veloci, ma l'aggiunta e la cancellazione saranno due volte più lente. Il che non è poi così male per un'operazione logaritmica. Un altro vantaggio di questa tecnica è che puoi utilizzare tipi di mappe specializzate per il tipo di chiave o valore se ne hai uno disponibile. Non avrai la stessa flessibilità con una specifica struttura di dati generalista.

Una soluzione diversa consiste nell'utilizzare un quadruplo (invece di considerare una relazione NxN come una coppia di relazioni 1xN e Nx1, la si vede come un insieme di elementi nel prodotto cartesiano (Chiave * Valore) dei tipi, che è, un piano spaziale), ma non mi è chiaro che i costi di tempo e memoria sono migliori rispetto a due mappe. Suppongo che debba essere testato.

Answer 2

Anche se non soddisfa il terzo requisito, bimap s sembra la strada da percorrere. (Si limitano a fare due mappe finite, una in ciascuna direzione, comoda da usare.)