Dictionnaire réversible pour python

Question

Je voudrais stocker des données en Python sous une forme similaire à un dictionnaire: {1:'a', 2:'b'}. Chaque valeur sera unique, non seulement entre autres valeurs, mais parmi les touches trop.

Y at-il une structure de données simple que je peux utiliser pour obtenir l'objet correspondant, peu importe si je demande à l'aide de la « clé » ou la « valeur »? Par exemple:

>>> a = {1:'a', 2:'b'}
>>> a[1]
'a'
>>> a['b']
2
>>> a[3]
KeyError

Les 'clés' sont ints python standards, une des valeurs sont des chaînes courtes (<) de 256char.

Ma solution actuelle est de créer un dictionnaire inversé et la recherche si je ne peux pas trouver un résultat dans le dictionnaire d'origine:

pointsreversed = dict((v, k) for k, v in points.iteritems())
def lookup(key):
    return points.get(key) or pointsreversed.key()

Il utilise deux fois plus d'espace, ce qui est grand (mes dictionnaires peuvent être jusqu'à quelques centaines de mégas) et 50% en moyenne plus lente.

EDIT:. Comme mentionné dans quelques réponses, deux dicts ne utilisation de la mémoire non double, car il est seulement le dictionnaire, et non les éléments contenus dans c'est la duplication

Y at-il une solution qui améliore à ce sujet?

Answer 1

Related posts:

inverse de mappage python

python 1: 1 mappages

Bien sûr, si toutes les valeurs et les clés sont uniques, ne pourriez-vous utiliser un seul dictionnaire, et d'insérer à la fois clé: valeur et de la valeur: touche d'abord

Answer 2

Si vos clés et des valeurs ne se chevauchent pas, une approche évidente consiste à les stocker simplement dans le même dict. à-dire:

class BidirectionalDict(dict):
    def __setitem__(self, key, val):
        dict.__setitem__(self, key, val)
        dict.__setitem__(self, val, key)

    def __delitem__(self, key):
        dict.__delitem__(self, self[key])
        dict.__delitem__(self, key)

d = BidirectionalDict()
d['foo'] = 4
print d[4]   # Prints 'foo'

(Vous aurez également probablement envie de mettre en œuvre des choses comme le __init__, et update méthodes pour agir iter* comme un vrai dict, selon la quantité de fonctionnalités dont vous avez besoin).

Il ne devrait impliquer une recherche, mais ne peut vous faire économiser beaucoup en mémoire (vous avez encore le nombre d'entrées dict après tout deux fois). A noter cependant que ni ceci, ni original utilisera deux fois plus d'espace: le dict ne prend de l'espace pour les références (pointeurs efficacement), ainsi que des frais généraux de surutilisation. L'espace occupé par vos données lui-même ne sera pas répétée deux fois depuis les mêmes objets sont pointés.

Answer 3

Dans l'art de la programmation informatique, Vokume 3 Knuth a une section sur les clés secondaires des recherches. Pour les besoins de votre question, la valeur peut être considérée comme la clé secondaire.

La première suggestion est de faire ce que vous avez fait. Rendre un indice efficace des clés par valeur

La deuxième suggestion consiste à configurer un grand btree qui est un indice composite des données groupées, où les noeuds de branche contiennent des valeurs et les feuilles contiennent des données essentielles et des pointeurs vers l'enregistrement plus grand (si elle existe).

Si les données sont géométriques (comme le vôtre semble) il y a des choses appelées arbres post-office. Il peut répondre à des questions telles que, ce qui est objet le plus proche du point x. Quelques exemples sont ici: http://simsearch.yury.name/russir/01nncourse- hand.pdf Une autre option simple pour ce genre de requête est le quadtree et l'arbre kd. http://en.wikipedia.org/wiki/Quadtree

Une autre option finale est hachage combinatoire, où vous combinez la clé et la valeur dans un type particulier de hachage qui vous permet d'effectuer des recherches efficaces sur le hachage, même si vous n'avez pas les deux valeurs. Je ne pouvais pas trouver une bonne explication de hachage combinatoire en ligne, mais il est en TAOCP, Volume 3 deuxième édition à la page 573.

Certes, pour certains d'entre eux vous pouvez avoir à écrire votre propre code. Mais si la mémoire ou la performance est vraiment la clé, vous voudrez peut-être prendre le temps.

Answer 4

Il ne faut pas utiliser « deux fois l'espace ». Dictionnaires simplement stocker des références à des données, et non les données elles-mêmes. Donc, si vous avez un million de chaînes prenant un milliard d'octets, chaque dictionnaire prend peut-être un 10-20 millions supplémentaires octets - une petite fraction du stockage global. L'utilisation de deux dictionnaires est la bonne chose à faire.

Answer 5

Insert inversée paire de (clé, valeur) en même dict:

a = {1:'a', 2:'b'}
a.update(dict((v, k) for k, v in a.iteritems()))

Ensuite, vous serez en mesure de faire les deux, comme vous devez:

print a[1]
print a['a']

Answer 6

Voici une autre solution en utilisant une classe définie par l'utilisateur.

Et le code ...

# search a dictionary for key or value
# using named functions or a class
# tested with Python25 by Ene Uran 01/19/2008

def find_key(dic, val):
    """return the key of dictionary dic given the value"""
    return [k for k, v in symbol_dic.iteritems() if v == val][0]

def find_value(dic, key):
    """return the value of dictionary dic given the key"""
    return dic[key]

class Lookup(dict):
    """
    a dictionary which can lookup value by key, or keys by value
    """
    def __init__(self, items=[]):
        """items can be a list of pair_lists or a dictionary"""
        dict.__init__(self, items)

    def get_key(self, value):
        """find the key(s) as a list given a value"""
        return [item[0] for item in self.items() if item[1] == value]

    def get_value(self, key):
        """find the value given a key"""
        return self[key]

Answer 7

Je l'ai fait ainsi depuis de nombreuses années. Personnellement, je aime la simplicité de plus que les autres solutions là-bas.

d = {1: 'a', 2: 'b'}
dict(zip(d.values(), d.keys()))