Une structure de données pour les mappages 1:1 en python?

L'autre alternative est de faire une nouvelle classe qui unit deux dictionnaires, un pour chaque type de recherche. Que serait très probablement rapide mais serait utilisez deux fois plus de mémoire qu'un dict unique.

Pas vraiment. Avez-vous mesuré qu'? Puisque les deux dictionnaires utiliseraient des références aux mêmes objets comme clés et valeurs, alors la mémoire dépensée serait juste la structure du dictionnaire. C'est beaucoup moins que deux fois et est un fixe ammount quelle que soit la taille de vos données.

Ce que je veux dire, c'est que les données réelles ne seraient pas copiées. Donc, vous dépenseriez peu de mémoire supplémentaire.

Exemple:

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

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

Une seule copie de la chaîne" really big " existe, donc vous finissez par dépenser un peu plus de mémoire. C'est généralement abordable.

Je ne peux pas imaginer une solution où vous auriez la vitesse de recherche de clé en regardant par valeur, si vous ne dépensez pas au moins assez de mémoire pour stocker une recherche inverse table de hachage (ce qui est exactement ce qui est fait dans votre solution" unite two dicts").

L'autre alternative est de créer une nouvelle classe qui unit deux dictionnaires, un pour chaque > type de recherche. Cela utiliserait probablement deux fois plus de mémoire qu'un seul dict.

Pas vraiment, puisqu'ils ne contiendraient que deux références aux mêmes données. Dans mon esprit, ce n'est pas une mauvaise solution.

Avez-vous envisagé une recherche de base de données en mémoire? Je ne sais pas comment cela va se comparer en vitesse, mais les recherches dans les bases de données relationnelles peuvent être Très rapide.

Voici mon propre solution à ce problème: http://github.com/spenthil/pymathmap/blob/master/pymathmap.py

Le but est de le rendre aussi transparent que possible pour l'utilisateur. Le seul attribut significatif introduit est partner.

OneToOneDict sous-classes de dict - je sais que n'est généralement pas recommandé, mais je pense que j'ai les cas d'utilisation courants couverts. Le backend est assez simple, il (dict1) conserve une weakref à un "partenaire' OneToOneDict (dict2) qui est son inverse. Lorsque {[4] } est modifié, dict2 est également mis à jour en conséquence et vice versa.

À partir de la 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'

Quand j'ai du temps libre, j'ai l'intention de faire une version qui ne stocke pas les choses deux fois. Aucune idée quand ce sera bien:)

En supposant que vous avez une clé avec laquelle vous recherchez un objet mutable plus complexe, faites simplement de la clé une propriété de cet objet. Il semble que vous feriez mieux de penser un peu au modèle de données.

"Nous pouvons garantir que la clé ou la valeur (ou les deux) sera un entier"

C'est bizarrement écrit - "clé ou la valeur (ou les deux)" ne se sent pas bien. Soit ils sont tous des entiers, soit ils ne sont pas tous des entiers.

On dirait que ce sont tous des entiers.

Ou, il semble que vous envisagiez de remplacer l'objet cible par une valeur entière afin que vous n'ayez qu'une seule copie référencée par un entier. C'est une fausse économie. Gardez simplement l'objet cible. Tout Les objets Python sont -- en effet -- des références. Très peu de copie réelle se fait.

Supposons que vous ayez simplement deux entiers et que vous puissiez faire une recherche sur l'une ou l'autre des paires. Une façon de le faire est d'utiliser des files d'attente de tas ou le module bisect pour maintenir des listes ordonnées de tuples clé-valeur entiers.

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

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

Vous avez un heapq (key,value) n-uplets. Ou, si votre objet sous-jacent est plus complexe, les tuples (key,object).

Vous avez un autre heapq (value,key) n-uplets. Ou, si votre objet sous-jacent est plus complexe, (otherkey,object) tuples.

Un "insert" devient deux inserts, un pour chaque liste structurée par heapq.

Clé de recherche est dans une file d'attente; une valeur de recherche est dans l'autre file d'attente. Faites les recherches en utilisant bisect(list,item).

Que diriez-vous d'utiliser sqlite? Créez simplement une base de données: memory: avec une table à deux colonnes. Vous pouvez même ajouter des index, puis interroger par l'un ou l'autre. L'envelopper dans une classe, si c'est quelque chose que vous allez utiliser beaucoup.

Il se trouve que je me retrouve à poser cette question tout le temps (hier en particulier). Je suis d'accord avec l'approche de faire deux dictionnaires. Faites un benchmarking pour voir combien de mémoire il prend. Je n'ai jamais eu besoin de le rendre mutable, Mais voici comment je l'abstrait, si c'est utile:

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')]