webentwicklung-frage-antwort-db.com.de

Warum kann ich in Python keine Liste als Diktierschlüssel verwenden?

Ich bin ein bisschen verwirrt darüber, was als Schlüssel für ein python dict verwendet werden kann/nicht.

dicked = {}
dicked[None] = 'foo'     # None ok
dicked[(1,3)] = 'baz'    # Tuple ok
import sys
dicked[sys] = 'bar'      # wow, even a module is ok !
dicked[(1,[3])] = 'qux'  # oops, not allowed

Ein Tupel ist also ein unveränderlicher Typ, aber wenn ich eine Liste darin verstecke, kann es kein Schlüssel sein. Kann ich eine Liste nicht genauso einfach in einem Modul verstecken?

Ich hatte eine vage Vorstellung davon, dass der Schlüssel "hashbar" sein muss, aber ich gebe nur meine eigene Unkenntnis über die technischen Details zu. Ich weiß nicht, was hier wirklich los ist. Was würde schief gehen, wenn Sie versuchen würden, Listen als Schlüssel zu verwenden, wobei der Hash beispielsweise deren Speicherort ist?

80
wim

Es gibt einen guten Artikel zu diesem Thema im Python wiki: Warum Listen keine Dictionary-Schlüssel sein können . Wie dort erklärt:

Was würde schief gehen, wenn Sie versuchen würden, Listen als Schlüssel zu verwenden, wobei der Hash beispielsweise deren Speicherort ist?

Dies kann durchgeführt werden, ohne die Anforderungen zu verletzen, führt jedoch zu unerwartetem Verhalten. Listen werden im Allgemeinen so behandelt, als ob ihr Wert von den Werten ihres Inhalts abgeleitet worden wäre, beispielsweise bei der Überprüfung der (Un-) Gleichheit. Viele würden - verständlicherweise - erwarten, dass Sie jede Liste verwenden können [1, 2], um denselben Schlüssel zu erhalten, wobei Sie genau dasselbe Listenobjekt behalten müssten. Die Suche nach Werten bricht jedoch ab, sobald eine Liste, die als Schlüssel verwendet wird, geändert wird, und die Suche nach Identität erfordert, dass Sie ungefähr dieselbe Liste führen - was für keine andere allgemeine Listenoperation erforderlich ist (zumindest keine, die mir einfällt) ).

Andere Objekte wie Module und object machen ohnehin viel mehr aus ihrer Objektidentität (wann hatten Sie das letzte Mal zwei unterschiedliche Modulobjekte mit dem Namen sys?) Und werden damit verglichen sowieso. Daher ist es weniger überraschend - oder sogar zu erwarten -, dass sie, wenn sie als Diktierschlüssel verwendet werden, auch in diesem Fall nach Identität verglichen werden.

21
user395760

Warum kann ich in Python keine Liste als Diktierschlüssel verwenden?

>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}

(für alle, die über diese Frage stolpern und nach einem Weg suchen, sie zu umgehen)

wie von anderen hier erklärt, kannst du es tatsächlich nicht. Sie können jedoch stattdessen die Zeichenfolgendarstellung verwenden, wenn Sie Ihre Liste wirklich verwenden möchten.

25
Remi

Das Problem ist, dass Tupel unveränderlich sind und Listen nicht. Folgendes berücksichtigen

d = {}
li = [1,2,3]
d[li] = 5
li.append(4)

Was sollte d[li] Rückkehr? Ist es die gleiche Liste? Wie wäre es mit d[[1,2,3]]? Es hat die gleichen Werte, ist aber eine andere Liste?

Letztendlich gibt es keine zufriedenstellende Antwort. Wenn der einzige Schlüssel, der funktioniert, beispielsweise der Originalschlüssel ist, können Sie nie wieder auf den Wert zugreifen, wenn Sie keinen Verweis auf diesen Schlüssel haben. Mit jedem anderen erlaubten Schlüssel können Sie einen Schlüssel ohne Bezug zum Original erstellen.

Wenn meine beiden Vorschläge funktionieren, haben Sie sehr unterschiedliche Schlüssel, die denselben Wert zurückgeben, was mehr als ein wenig überraschend ist. Wenn nur der ursprüngliche Inhalt funktioniert, wird Ihr Schlüssel schnell ungültig, da Listen so erstellt werden, dass sie geändert werden.

10
Eric Wilson

Gerade gefunden, können Sie Liste in Tupel ändern und es dann als Schlüssel verwenden.

d = {Tuple([1,2,3]): 'value'}
7
Ningrong Ye

Hier ist eine Antwort http://wiki.python.org/moin/DictionaryKeys

Was würde schief gehen, wenn Sie versuchen würden, Listen als Schlüssel zu verwenden, wobei der Hash beispielsweise deren Speicherort ist?

Das Nachschlagen verschiedener Listen mit demselben Inhalt würde zu unterschiedlichen Ergebnissen führen, obwohl das Vergleichen von Listen mit demselben Inhalt dies als gleichwertig anzeigt.

Was ist mit der Verwendung eines Listenliteral in einer Wörterbuchsuche?

7
bpgergo

Ihre Markise finden Sie hier:

Warum Listen keine Wörterbuchschlüssel sein können

Neulinge in Python) fragen sich oft, warum Tupel als Wörterbuchschlüssel verwendet werden können, obwohl die Sprache sowohl einen Tupel- als auch einen Listentyp enthält, während dies bei Listen nicht der Fall ist Erklären Sie dies am besten, indem Sie zunächst verstehen, wie Python Wörterbücher funktionieren.

Quelle und weitere Informationen: http://wiki.python.org/moin/DictionaryKeys

2
AKjsd89

Die einfache Antwort auf Ihre Frage lautet, dass die Klassenliste nicht die Methode Hash implementiert, die für ein Objekt erforderlich ist, das als Schlüssel in einem Wörterbuch verwendet werden soll. Der Grund, warum Hash nicht wie in der Tuple-Klasse (basierend auf dem Inhalt des Containers) implementiert ist, liegt darin, dass eine Liste veränderbar ist, sodass die Liste bearbeitet werden kann erfordern, dass der Hash neu berechnet wird, was bedeuten kann, dass sich die Liste jetzt im falschen Bucket in der untergeordneten Hash-Tabelle befindet. Beachten Sie, dass dieses Problem nicht auftritt, da Sie ein Tupel (unveränderlich) nicht ändern können.

Als Randnotiz basiert die tatsächliche Implementierung der Dictobjects-Suche auf dem Algorithmus D von Knuth Vol. 4, No. 3, Sec. 6.4. Wenn Sie dieses Buch zur Verfügung haben, könnte es sich lohnen, es zu lesen. Wenn Sie wirklich sehr, sehr interessiert sind, können Sie einen Blick auf die Kommentare der Entwickler zur tatsächlichen Implementierung von dictobject hier. Werfen = Es wird sehr detailliert darauf eingegangen, wie es genau funktioniert. Es gibt auch einen Python-Vortrag über die Implementierung von Wörterbüchern, die Sie interessieren könnten. Sie gehen die Definition eines Schlüssels durch und was ein Hash in den ersten Minuten ist.

1
Ben Wright

Da Listen veränderlich sind, müssen dict Schlüssel (und set Mitglieder) hashbar sein, und es ist eine schlechte Idee, veränderliche Objekte zu hashen, da Hash-Werte sollte berechnet werden auf der Basis von Instanzattributen.

In dieser Antwort werde ich einige konkrete Beispiele geben, die hoffentlich zusätzlich zu den vorhandenen Antworten einen Mehrwert bieten. Jede Einsicht gilt auch für die Elemente der Datenstruktur set.

Beispiel 1: Hashing eines veränderlichen Objekts, wobei der Hash-Wert auf einer veränderlichen Eigenschaft des Objekts basiert.

>>> class stupidlist(list):
...     def __hash__(self):
...         return len(self)
... 
>>> stupid = stupidlist([1, 2, 3])
>>> d = {stupid: 0}
>>> stupid.append(4)
>>> stupid
[1, 2, 3, 4]
>>> d
{[1, 2, 3, 4]: 0}
>>> stupid in d
False
>>> stupid in d.keys()
False
>>> stupid in list(d.keys())
True

Nach der Mutation von stupid kann es nicht mehr im Diktat gefunden werden, da sich der Hash geändert hat. Nur ein linearer Scan über die Liste der Diktattasten findet stupid.

Beispiel 2: ... aber warum nicht einfach einen konstanten Hashwert?

>>> class stupidlist2(list):
...     def __hash__(self):
...         return id(self)
... 
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>> 
>>> stupidA == stupidB
True
>>> stupidA in {stupidB: 0}
False

Das ist auch keine gute Idee, da gleiche Objekte identisch hashen sollten, sodass Sie sie in einem dict oder set finden können.

Beispiel: ... ok, was ist mit konstanten Hashes über alle Instanzen hinweg ?!

>>> class stupidlist3(list):
...     def __hash__(self):
...         return 1
... 
>>> stupidC = stupidlist3([1, 2, 3])
>>> stupidD = stupidlist3([1, 2, 3])
>>> stupidE = stupidlist3([1, 2, 3, 4])
>>> 
>>> stupidC in {stupidD: 0}
True
>>> stupidC in {stupidE: 0}
False
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d
True

Die Dinge scheinen wie erwartet zu funktionieren, aber denken Sie darüber nach, was passiert: Wenn alle Instanzen Ihrer Klasse denselben Hash-Wert erzeugen, kommt es zu einer Hash-Kollision, wenn mehr als zwei Instanzen als Schlüssel in einem dict oder vorhanden sind in einem set.

Um die richtige Instanz mit my_dict[key] Oder key in my_dict (Oder item in my_set) Zu finden, müssen so viele Gleichheitsprüfungen durchgeführt werden, wie Instanzen von stupidlist3 In den Diktatschlüsseln vorhanden sind ( im schlimmsten Fall). Zu diesem Zeitpunkt ist der Zweck des Wörterbuchs - O(1) lookup - vollständig beseitigt. Dies wird in den folgenden Timings (mit IPython) demonstriert.

Einige Zeitpunkte für Beispiel

>>> lists_list = [[i]  for i in range(1000)]
>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}
>>> tuples_set = {(i,) for i in range(1000)}
>>> l = [999]
>>> s = stupidlist3([999])
>>> t = (999,)
>>> 
>>> %timeit l in lists_list
25.5 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit s in stupidlists_set
38.5 µs ± 61.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit t in tuples_set
77.6 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

Wie Sie sehen, ist der Mitgliedschaftstest in unserem stupidlists_set Sogar langsamer als ein linearer Scan über den gesamten lists_list, Während Sie die erwartete superschnelle Suchzeit (Faktor 500) in einem Satz ohne haben viele Hash-Kollisionen.


TL; DR: Sie können Tuple(yourlist) als dict -Tasten verwenden, da Tupel unveränderlich und hashbar sind.

1
timgeb

Laut der Python 2.7.2 Dokumentation:

Ein Objekt ist hashbar, wenn es einen Hashwert hat, der sich während seiner Lebensdauer nicht ändert (es benötigt eine hash () Methode) und mit anderen Objekten verglichen werden kann (es benötigt eine eq () oder cmp () Methode). Hashbare Objekte, die gleich vergleichen, müssen den gleichen Hashwert haben.

Hashability macht ein Objekt als Dictionary-Schlüssel und Set-Member verwendbar, da diese Datenstrukturen den Hash-Wert intern verwenden.

Alle unveränderlichen integrierten Objekte von Python sind hashfähig, während es keine veränderlichen Container (wie Listen oder Wörterbücher) sind. Objekte, die Instanzen von benutzerdefinierten Klassen sind, können standardmäßig gehasht werden. Sie vergleichen alle ungleich, und ihr Hash-Wert ist ihre id ().

Ein Tupel ist in dem Sinne unveränderlich, dass Sie seine Elemente nicht hinzufügen, entfernen oder ersetzen können, aber die Elemente selbst können veränderlich sein. Der Hash-Wert von List hängt von den Hash-Werten seiner Elemente ab und ändert sich daher, wenn Sie die Elemente ändern.

Die Verwendung von IDs für Listen-Hashes würde bedeuten, dass alle Listen unterschiedlich verglichen werden, was überraschend und unpraktisch wäre.

0
Nicola Musatti