Una struttura dati per i mapping 1: 1 in python?

Question

Ho un problema che richiede una mappatura 1: 1 reversibile delle chiavi ai valori.

Ciò significa che a volte desidero trovare il valore fornito da una chiave, ma in altri casi desidero trovare la chiave in base al valore. Sia le chiavi che i valori sono garantiti come unici.

x = D[y] 
y == D.inverse[x] 

La soluzione più ovvia è quella di invertire semplicemente il dizionario ogni volta che voglio una ricerca inversa: Inversione di un dizionario è molto semplice, there's a recipe here but for a large dictionary it can be very slow.

L'altra alternativa è creare una nuova classe che unisca due dizionari, uno per ogni tipo di ricerca. Molto probabilmente sarebbe veloce, ma consumerebbe il doppio della memoria di un singolo dettato.

Quindi c'è una struttura migliore che posso usare?

• La mia applicazione richiede che questo dovrebbe essere molto veloce e utilizzare il minimo di memoria possibile.
• La struttura deve essere modificabile ed è fortemente auspicabile che la mutazione dell'oggetto non causi più rallentamento (ad es. Forzare un reindicizzazione completo)
• Possiamo garantire che la chiave o il valore (o entrambi) sarà un numero intero
• È probabile che la struttura sarà necessaria per memorizzare migliaia o forse milioni di elementi.
• Keys & Valus sono garantiti per essere unico, cioè len (set (x)) == len (x) per for x in [d.keys(), D.valuies()]

Answer 1

class TwoWay: 
    def __init__(self): 
     self.d = {} 
    def add(self, k, v): 
     self.d[k] = v 
     self.d[v] = k 
    def remove(self, k): 
     self.d.pop(self.d.pop(k)) 
    def get(self, k): 
     return self.d[k] 

Answer 2

L'altra alternativa è creare una nuova classe che unisce due dizionari, uno per ciascun tipo di ricerca. Molto probabilmente consumerebbe il doppio della memoria di un singolo dettato.

Non proprio, dal momento che sarebbe solo essere tenuta due riferimenti agli stessi dati. Nella mia mente, questa non è una cattiva soluzione.

Avete considerato una ricerca nel database in memoria? Non sono sicuro di come verrà confrontato in termini di velocità, ma le ricerche nei database relazionali possono essere molto molto veloce.

Answer 3

Supponendo di avere una chiave con cui si ricerca un oggetto mutevole più complesso, basta rendere la chiave una proprietà di tale oggetto. Sembra che tu stia meglio pensando un po 'al modello di dati.

Answer 4

L'altra alternativa è quella di effettuare una nuova classe che unisce due dizionari, uno per ogni tipo di ricerca. Quello molto probabilmente sarebbe veloce ma consumerebbe il doppio della memoria di un singolo dict .

Non proprio. L'hai misurato? Poiché entrambi i dizionari utilizzerebbero riferimenti allo stesso oggetto come chiavi e valori, la memoria spesa sarebbe solo la struttura del dizionario. Questo è molto meno di due volte ed è un importo fisso indipendentemente dalle dimensioni dei dati.

Ciò che intendo è che i dati effettivi non verranno copiati. Quindi spenderebbe poca memoria in più.

Esempio:

a = "some really really big text spending a lot of memory" 

number_to_text = {1: a} 
text_to_number = {a: 1} 

Solo una singola copia della stringa "davvero grande" esiste, così si finisce per spendere un po 'più di memoria. Questo è generalmente conveniente.

Non riesco a immaginare una soluzione in cui si avrebbe la velocità di ricerca della chiave quando si cerca per valore, se non si spendono almeno memoria sufficiente per memorizzare una tabella di ricerca inversa hash (che è esattamente ciò che è stato fatto nella tua soluzione "unite two dict s").

Answer 5

"Siamo in grado di garantire che sia la chiave o il valore (o entrambi) sarà un numero intero"

che è stranamente scritto - "o il valore (o entrambi)" non sentire. O sono tutti interi, o non sono tutti interi.

Sembra che siano tutti numeri interi.

Oppure, sembra che si stia pensando di sostituire l'oggetto di destinazione con un valore intero in modo da avere una sola copia a cui fa riferimento un numero intero. Questa è una falsa economia. Tieni solo l'oggetto bersaglio. Tutti gli oggetti Python sono - in effetti - riferimenti. Viene eseguita pochissima copia effettiva.

Supponiamo di avere semplicemente due numeri interi e di poter eseguire una ricerca su uno dei due. Un modo per farlo è utilizzare le code di heap o il modulo bisect per mantenere gli elenchi ordinati di tuple di valori-chiave interi.

Vedi http://docs.python.org/library/heapq.html#module-heapq

Vedi http://docs.python.org/library/bisect.html#module-bisect

Hai uno heapq (key,value) tuple. Oppure, se l'oggetto sottostante è più complesso, le tuple (key,object).

Si dispone di un altro heapq (value,key) tuple. Oppure, se l'oggetto sottostante è più complesso, tuple (otherkey,object).

Un "inserimento" diventa due inserti, uno per ogni elenco strutturato heapq.

Una ricerca chiave è in una coda; una ricerca di valore è nell'altra coda. Effettua le ricerche utilizzando bisect(list,item).

Answer 6

Accade così che mi ritrovi a fare questa domanda tutto il tempo (ieri in particolare). Sono d'accordo con l'approccio di creare due dizionari. Fai un benchmarking per vedere quanta memoria sta prendendo. Non ho mai avuto bisogno di renderlo mutevole, ma ecco come lo astraggo, se è di qualche utilità:

class BiDict(list): 
    def __init__(self,*pairs): 
     super(list,self).__init__(pairs) 
     self._first_access = {} 
     self._second_access = {} 
     for pair in pairs: 
      self._first_access[pair[0]] = pair[1] 
      self._second_access[pair[1]] = pair[0] 
      self.append(pair) 

    def _get_by_first(self,key): 
     return self._first_access[key] 

    def _get_by_second(self,key): 
     return self._second_access[key] 

    # You'll have to do some overrides to make it mutable 
    # Methods such as append, __add__, __del__, __iadd__ 
    # to name a few will have to maintain ._*_access 

class Constants(BiDict): 
    # An implementation expecting an integer and a string 
    get_by_name = BiDict._get_by_second 
    get_by_number = BiDict._get_by_first 

t = Constants(
     (1, 'foo'), 
     (5, 'bar'), 
     (8, 'baz'), 
    ) 

>>> print t.get_by_number(5) 
bar 
>>> print t.get_by_name('baz') 
8 
>>> print t 
[(1, 'foo'), (5, 'bar'), (8, 'baz')] 

Answer 7

Che ne dici di usare sqlite? Basta creare un: memoria: database con una tabella a due colonne. È anche possibile aggiungere indici, quindi eseguire una query da uno dei due. Avvolgilo in una classe se è qualcosa che userai molto.

Answer 8

Ecco la mia soluzione a questo problema: http://github.com/spenthil/pymathmap/blob/master/pymathmap.py

L'obiettivo è quello di rendere il più trasparente per l'utente il più possibile. L'unico attributo significativo introdotto è partner.

OneToOneDict sottoclassi da dict - So che isn't generally recommended, ma penso di avere i casi di utilizzo comune coperto. Il backend è piuttosto semplice, (dict1) mantiene un weakref per un 'partner' OneToOneDict (dict2), che è la sua inversa. Quando dict1 viene modificato, dict2 viene aggiornato di conseguenza e viceversa.

Dal docstring:

>>> dict1 = OneToOneDict() 
>>> dict2 = OneToOneDict() 
>>> dict1.partner = dict2 
>>> assert(dict1 is dict2.partner) 
>>> assert(dict2 is dict1.partner) 
>>> dict1['one'] = '1' 
>>> dict2['2'] = '1' 
>>> dict1['one'] = 'wow' 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict1['one'] = '1' 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict1.update({'three': '3', 'four': '4'}) 
>>> assert(dict1 == dict((v,k) for k,v in dict2.items())) 
>>> dict3 = OneToOneDict({'4':'four'}) 
>>> assert(dict3.partner is None) 
>>> assert(dict3 == {'4':'four'}) 
>>> dict1.partner = dict3 
>>> assert(dict1.partner is not dict2) 
>>> assert(dict2.partner is None) 
>>> assert(dict1.partner is dict3) 
>>> assert(dict3.partner is dict1) 
>>> dict1.setdefault('five', '5') 
>>> dict1['five'] 
'5' 
>>> dict1.setdefault('five', '0') 
>>> dict1['five'] 
'5' 

Quando ho del tempo libero, ho intenzione di fare una versione che non memorizza le cose due volte. Nessun indizio quando sarà così :)