dictionary

[dk1ri]

Eine einfache Frage:

Gibt es eine einfache Möglichkeit, bei dictionaries vom value auf den (die) keys zuzugreifen? so wie bei Perl zB
in den tutorials habe ich nichts gefunden...
tnx
guenter

[Schorlem]

Soweit ich weiß, ist das nicht direkt möglich. Allerdings könntest du in einer Schleife durch alle Keys durchlaufen und ihren Wert überprüfen.

[dk1ri]

tnx, klar, so geht es. Soweit ich weiss, benutzt Perl eine hashfunktion und ist damit bei langen Listen sehr schnell.

[BlackJack]

@dk1ri: Wie geht das denn bei Perl? AFAIK macht man da nichts anderes als bei Python, nur die Syntax ist halt ein bisschen anders. Schlüssel nach Wert ist bei beiden O(1) wegen der Implementierung als Hashtabelle, und wenn man von Wert nach Schlüssel(n) will wird es in beiden Sprachen ineffizient, weil man eben linear durch die Schlüssel/Wert-Paare gehen muss um das gewünschte zu finden.

[jerch]

@dk1ri:
Du kannst Dir ein reverse lookup Wörterbuch erstellen, falls die Zugriffszeiten problematisch sind. Als Schlüssel müssen Deine Werte hashable sein, Mehrfachbelegungen musst Du entweder verbieten oder als Wert einen Containertypen verwenden. Perl hat für sowas einen automagischen Typen?

[snafu]

@dk1ri: Wörterbücher (oder wie auch immer sie in der jeweiligen Sprache benannt sind) haben grundsätzlich die Eigenschaft, dass jeder Schlüssel nur genau einmal existieren darf. Es kann jedoch der selbe Wert an mehrere Schlüssel gebunden sein. Das ist durchaus praktikabel, wenn z.B. die Werte aus Zahlen bestehen oder wenn sie lediglich Wahrheitswerte sind. Man kann daher nur aufgrund des Wertes nicht eindeutig herausfinden, welchem Schlüssel der Wert zugeordnet wurde.

Wenn du sicher bist, dass auch die Werte einmalig sind, dann könntest du z.B. eine eigene Klasse von ``dict`` ableiten, die intern ein weiteres Wörterbuch führt, in dem die Umkehrung verwaltet wird. Da müsste man halt jede für ``dict``s definierte Operation zusätzlich auf dem zweiten Wörterbuch anwenden. Alternativ kann man ein "normales" Wörterbuch auch einfach in ein "umgekehrtes" Wörterbuch umwandeln. Letzteres könnte man so umsetzen (Ausgabe aus der IPython-Shell):

Code: Alles auswählen

In [1]: def get_switched_dict(d):
   ...:     return dict(zip(d.values(), d.keys()))
   ...: 

In [2]: d = {'a': 1, 'b': 2, 'c': 3}

In [3]: get_switched_dict(d)
Out[3]: {1: 'a', 2: 'b', 3: 'c'}

Unter Umständen möchte man, falls Python 2.x verwendet wird, an einigen Stellen Iteratoren einsetzen. Das habe ich jetzt mal ausgespart.

[dk1ri]

hoffentlich ist das nicht doppelt:

Bei Perl heist das assoziative arrays ( %xyz ) mit den keywords keys und values, die man darauf anwenden kann.

sh zB http://www.tutorialspoint.com/perl/perl_hashes.htm

die Lösung mit den reverse directories ist wohl das einfachste, Speicherplatz ist billig

tnx
Guenter

[kbr]

Gibt es eine einfache Möglichkeit, bei dictionaries vom value auf den (die) keys zuzugreifen?

Du könnstest Dir ein "double dict" schreiben. Das sieht rudimentär etwa so aus:

Code: Alles auswählen

>>> class DDict(dict):
...     def __init__(self):
...         super(DDict, self).__init__()
...         self.key = {}        
...     def __setitem__(self, key, value):
...         super(DDict, self).__setitem__(key, value)
...         self.key[value] = key
... 
>>> dd = DDict()
>>> dd['a'] = 'b'
>>> dd['a']
'b'
>>> dd.key['b']
'a'
>>> 

Die values müssen, wie schon erwähnt, "hashable" sein. Falls ein value mehrfach vorkommt sind die keys auch nicht mehr eindeutig.

[jerch]

Hier mal mit Werte-Dopplungen und Entfernen von Items:

Code: Alles auswählen

from collections import defaultdict

class DoubleDict(dict):
    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self.key = defaultdict(set)
        for k, v in self.iteritems():
            self.key[v].add(k)

    def __setitem__(self, key, value):
        dict.__setitem__(self, key, value)
        self.key[value].add(key)

    def __delitem__(self, key):
        value = self.pop(key)
        reverse = self.key[value]
        if reverse:
            reverse.remove(key)
        if not reverse:
            del self.key[value]

Das `defaultdict(set)` bietet sich hier an, da Key-Dopplungen im Container unmöglich sind und die Reihenfolge egal ist. Für vollständige Behandlung müsstest Du die anderen Dict-Methoden ebenfalls ableiten.

[BlackJack]

@dk1ri: Hashes in Perl sind mir bekannt, darum habe ich die Frage ja auch nicht verstanden. Auch in Perl muss man doch über die Schlüssel/Wert-Paare iterieren um vom Wert zum Schlüssel zu kommen, also verstehen ich den Teil der Frage nicht ob das *so einfach* wie in Perl geht. Das ist in beiden Sprachen gleich kompliziert und auch gleich (in)effizient.

[dk1ri]

@Blackjack. für den Programierer ist es einfacher: die Funktionen keys und values sind eingebaut.

Soweit ich weiss, durchsucht perl mit den eingebauten Befehlen nicht die Originaltabelle sondern eine (kuerzere) Hashtabelle, was dann schneller geht.

@all
gute Hinweise, tnx

Guenter

[jerch]

In meiner Version fehlte das Update auf einen bereits gesetzten Schlüssel, damit klappts:

Code: Alles auswählen

from collections import defaultdict

class DoubleDict(dict):
    def __init__(self, *args, **kwargs):
        dict.__init__(self, *args, **kwargs)
        self.key = defaultdict(set)
        for k, v in self.iteritems():
            self.key[v].add(k)

    def _clean_reverse(self, key, value):
        reverse = self.key[value]
        if reverse:
            reverse.remove(key)
        if not reverse:
            del self.key[value]

    def __setitem__(self, key, value):
        old = self.get(key)
        if old:
            self._clean_reverse(key, old)
        dict.__setitem__(self, key, value)
        self.key[value].add(key)

    def __delitem__(self, key):
        value = self.pop(key)
        self._clean_reverse(key, value)

@dk1ri:
Schlüssel werden in Python auch gehasht, das gilt aber nicht für die Werte, das kann jedes Objekt sein (auch nicht hashable). Bei den Werten ist auch nichts weiter typisiert, was einen Hinweis für einen "Suchbaum" geben könnte. Dopplungen wären damit auch nur mit vielen Verrenkungen möglich. Ich kann mir kaum vorstellen, dass Perl hier sehr anders tickt.

Was ich mir vorstellen könnte, ist obige Setlösung interpreternah vorzuhalten, heisst mit jedem hinzugefügten Schlüssel-Wert-Paar die Rückreferenzen in einer C-Struktur mitlaufen zu lassen. Das würde aber das Standard-Wörterbuch sehr stark ausbremsen.

[BlackJack]

@dk1ri: Ähm, es ist für den Programmierer einfacher ``keys %mapping`` oder ``values %mapping`` zu schreiben als ``mapping.keys()`` oder ``mapping.values()`` weil das ”eingebaut” ist? Das ist ein Scherz oder?

Weder bei ``keys`` noch bei ``values`` nützt es das die Implementierung eine Hashtabelle ist, in beiden Fällen muss man offensichtlicherweise linear die jeweiligen Schlüssel beziehungsweise Werte durchgehen. Und wie schon gesagt machen Perl und Python da in der Implementierung das gleiche.

[dk1ri]

Eigentlich wusste ich nur nicht, dass es die Methoden keys und values gibt; das war eigentlich meine erste Frage.
Vielleicht finde ich die auch noch...

Aber offenbar bin ich nicht der einzige, der das nicht wusste und ich hoffe, dass der thread nicht nur mir etwas gebracht hat.

Guenter

[EyDu]

Eigentlich wusste ich nur nicht, dass es die Methoden keys und values gibt; das war eigentlich meine erste Frage.
Vielleicht finde ich die auch noch...

Nee, das war nicht deine Frage. Du hast gefragt, wie man von den Werten auf die Schlüssel schließen kann:

Gibt es eine einfache Möglichkeit, bei dictionaries vom value auf den (die) keys zuzugreifen?

Möglicherweise könnte dir auch noch die items-Methode helfen, damit bekommst du Schlüssel und Wert gemeinsam.

[snafu]

Wir reden schon von Anfang an davon, dass man entweder alle Schlüssel-Werte-Paare (=Items) sequentiell durchlaufen muss (womit man sich ein Wörterbuch auch gleich sparen kann) oder dass man in einer abgeleiteten Klasse intern irgendetwas hashbasiertes (=Set oder Dict) verwenden muss, wenn der Zugriff effizienter ablaufen soll. Bei letzterem hat man jedoch logischerweise den Overhead für's Verwalten von Zu- und Abgängen. Alternativ baut man sich - wie von mir vorgeschlagen - nach dem Anlegen aller Einträge im ersten Wörterbuch ein weiteres Wörterbuch, welches die Umkehrung abbildet und worauf man dann beliebig viele Abfragen machen kann, solange sich der Inhalt des ersten Wörterbuchs nicht verändert.

Dass jetzt die bloße Erwähnung von ``.keys()`` und ``.values()`` die Lösung des Problems sein soll, zeigt mir, dass der Threadersteller die wesentliche Problematik bzw die Intention der Antworten offenbar noch nicht vollständig erfasst hat, um es mal diplomatisch auszudrücken...

[dk1ri]

@snafu: Ist so realisiert...
BTW: das keys und values stammt nicht von mir.
-> Ende
tnx nochmal
Guenter

[BlackJack]

@dk1ri: *Was* ist *wie* realisiert? Und doch, mit keys und values hast *Du* angefangen.