Zweiwege- / Rückwärtskarte [Duplikat]

Ich mache diese Telefonzentrale in Python, wo ich nachverfolgen muss, wer mit wem spricht. Wenn also Alice -> Bob, dann bedeutet das, dass Bob -> Alice.

Ja, ich könnte zwei Hash-Karten füllen, aber ich frage mich, ob jemand eine Idee hat, dies mit einer zu tun.

Oder schlagen Sie eine andere Datenstruktur vor.

Es gibt keine Mehrfachgespräche. Nehmen wir an, dies ist für ein Kundendienst-Callcenter. Wenn Alice sich in die Telefonzentrale einwählt, wird sie nur mit Bob sprechen. Seine Antworten gehen auch nur an sie.

Sie können Ihren eigenen Wörterbuchtyp erstellen, dictindem Sie die gewünschte Logik unterordnen und hinzufügen. Hier ist ein einfaches Beispiel:

class TwoWayDict(dict):
    def __setitem__(self, key, value):
        # Remove any previous connections with these values
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)

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

    def __len__(self):
        """Returns the number of connections"""
        return dict.__len__(self) // 2

Und es funktioniert so:

>>> d = TwoWayDict()
>>> d['foo'] = 'bar'
>>> d['foo']
'bar'
>>> d['bar']
'foo'
>>> len(d)
1
>>> del d['foo']
>>> d['bar']
Traceback (most recent call last):
  File "<stdin>", line 7, in <module>
KeyError: 'bar'

Ich bin sicher, ich habe nicht alle Fälle abgedeckt, aber das sollte Ihnen den Einstieg erleichtern.

In Ihrem speziellen Fall können Sie beide in einem Wörterbuch speichern:

relation = {}
relation['Alice'] = 'Bob'
relation['Bob'] = 'Alice'

Denn was Sie beschreiben, ist eine symmetrische Beziehung. A -> B => B -> A

Ich weiß, dass es eine ältere Frage ist, aber ich wollte eine andere großartige Lösung für dieses Problem erwähnen, nämlich das Bidict des Python-Pakets . Es ist sehr einfach zu bedienen:

from bidict import bidict
map = bidict(Bob = "Alice")
print(map["Bob"])
print(map.inv["Alice"])

Ich würde nur einen zweiten Hash mit füllen

reverse_map = dict((reversed(item) for item in forward_map.items()))

Zwei Hash-Maps sind wahrscheinlich die Lösung mit der schnellsten Leistung, vorausgesetzt, Sie können Speicherplatz sparen. Ich würde diese in eine einzige Klasse einschließen - die Belastung für den Programmierer besteht darin, sicherzustellen, dass zwei der Hash-Maps korrekt synchronisiert werden.

Sie haben zwei separate Probleme.

1. Sie haben ein "Conversation" -Objekt. Es bezieht sich auf zwei Personen. Da eine Person mehrere Gespräche führen kann, haben Sie eine Viele-zu-Viele-Beziehung.

2. Sie haben eine Karte von Person zu einer Liste von Gesprächen. Eine Konvertierung hat zwei Personen.

Mach so etwas

from collections import defaultdict
switchboard= defaultdict( list )

x = Conversation( "Alice", "Bob" )
y = Conversation( "Alice", "Charlie" )

for c in ( x, y ):
    switchboard[c.p1].append( c )
    switchboard[c.p2].append( c )

Nein, es gibt wirklich keine Möglichkeit, dies zu tun, ohne zwei Wörterbücher zu erstellen. Wie wäre es möglich, dies mit nur einem Wörterbuch zu implementieren und gleichzeitig eine vergleichbare Leistung zu bieten?

Sie sollten einen benutzerdefinierten Typ erstellen, der zwei Wörterbücher enthält und die gewünschte Funktionalität bereitstellt.

Ein weniger ausführlicher Weg, immer noch umgekehrt:

dict(map(reversed, my_dict.items()))

Möglicherweise können Sie ein DoubleDictwie in Rezept 578224 im Python-Kochbuch gezeigt verwenden .

Eine andere mögliche Lösung besteht darin, eine Unterklasse von zu implementieren dict, die das ursprüngliche Wörterbuch enthält und eine umgekehrte Version davon verfolgt. Das Halten von zwei getrennten Diktaten kann nützlich sein, wenn sich Schlüssel und Werte überschneiden.

class TwoWayDict(dict):
    def __init__(self, my_dict):
        dict.__init__(self, my_dict)
        self.rev_dict = {v : k for k,v in my_dict.iteritems()}

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        self.rev_dict.__setitem__(value, key)

    def pop(self, key):
        self.rev_dict.pop(self[key])
        dict.pop(self, key)

    # The above is just an idea other methods
    # should also be overridden. 

Beispiel:

>>> d = {'a' : 1, 'b' : 2} # suppose we need to use d and its reversed version
>>> twd = TwoWayDict(d)    # create a two-way dict
>>> twd
{'a': 1, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b'}
>>> twd['a']
1
>>> twd.rev_dict[2]
'b'
>>> twd['c'] = 3    # we add to twd and reversed version also changes
>>> twd
{'a': 1, 'c': 3, 'b': 2}
>>> twd.rev_dict
{1: 'a', 2: 'b', 3: 'c'}
>>> twd.pop('a')   # we pop elements from twd and reversed  version changes
>>> twd
{'c': 3, 'b': 2}
>>> twd.rev_dict
{2: 'b', 3: 'c'}

Auf pypi befindet sich die Bibliothek mit erweiterten Sammlungen: https://pypi.python.org/pypi/collections-extended/0.6.0

Die Verwendung der Bijektionsklasse ist so einfach wie:

RESPONSE_TYPES = bijection({
    0x03 : 'module_info',
    0x09 : 'network_status_response',
    0x10 : 'trust_center_device_update'
})
>>> RESPONSE_TYPES[0x03]
'module_info'
>>> RESPONSE_TYPES.inverse['network_status_response']
0x09

Ich mag den Vorschlag von Bidict in einem der Kommentare.

pip install bidict

Verwendung:

# This normalization method should save hugely as aDaD ~ yXyX have the same form of smallest grammar.
# To get back to your grammar's alphabet use trans

def normalize_string(s, nv=None):
    if nv is None:
        nv = ord('a')
    trans = bidict()
    r = ''
    for c in s:
        if c not in trans.inverse:
            a = chr(nv)
            nv += 1
            trans[a] = c
        else:
            a = trans.inverse[c]
        r += a
    return r, trans


def translate_string(s, trans):
    res = ''
    for c in s:
        res += trans[c]
    return res


if __name__ == "__main__":
    s = "bnhnbiodfjos"

    n, tr = normalize_string(s)
    print(n)
    print(tr)
    print(translate_string(n, tr))    

Da gibt es nicht viele Dokumente darüber. Aber ich habe alle Funktionen, die ich brauche, damit es richtig funktioniert.

Drucke:

abcbadefghei
bidict({'a': 'b', 'b': 'n', 'c': 'h', 'd': 'i', 'e': 'o', 'f': 'd', 'g': 'f', 'h': 'j', 'i': 's'})
bnhnbiodfjos

Das kjbuckets C-Erweiterungsmodul bietet eine "Graph" -Datenstruktur, von der ich glaube, dass sie Ihnen das bietet, was Sie wollen.

Hier ist eine weitere Zwei-Wege-Wörterbuchimplementierung durch Erweitern der Python- dictKlasse, falls Ihnen eine dieser anderen nicht gefallen hat:

class DoubleD(dict):
    """ Access and delete dictionary elements by key or value. """ 

    def __getitem__(self, key):
        if key not in self:
            inv_dict = {v:k for k,v in self.items()}
            return inv_dict[key]
        return dict.__getitem__(self, key)

    def __delitem__(self, key):
        if key not in self:
            inv_dict = {v:k for k,v in self.items()}
            dict.__delitem__(self, inv_dict[key])
        else:
            dict.__delitem__(self, key)

Verwenden Sie es als normales Python-Wörterbuch, außer in der Konstruktion:

dd = DoubleD()
dd['foo'] = 'bar'

Eine Art und Weise, wie ich so etwas mache, ist so etwas wie:

{my_dict[key]: key for key in my_dict.keys()}