Dlaczego nie mogę użyć listy jako klucza dyktowania w Pythonie?


103

Jestem trochę zdezorientowany, co może, a czego nie może być używane jako klucz do dyktu w Pythonie.

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

Tak więc krotka jest niezmiennym typem, ale jeśli ukryję w niej listę, to nie może to być klucz… czy nie mógłbym równie łatwo ukryć listy w module?

Miałem niejasne pojęcie, że klucz musi być „haszowany”, ale zamierzam tylko przyznać, że nie znam szczegółów technicznych; Nie wiem, co się tu naprawdę dzieje. Co by się stało, gdybyś spróbował użyć list jako kluczy, z hashem jako, powiedzmy, lokalizacją w pamięci?



50
Zaśmiał się z twojej nazwy zmiennej.
kindall

Odpowiedzi:


35

Na wiki Pythona znajduje się dobry artykuł na ten temat: Why Lists Can't Be Dictionary Keys . Jak tam wyjaśniono:

Co by się nie stało, gdybyś próbował użyć list jako kluczy, z hashem jako, powiedzmy, lokalizacją w pamięci?

Można to zrobić bez łamania któregokolwiek z wymagań, ale prowadzi to do nieoczekiwanego zachowania. Listy są generalnie traktowane tak, jakby ich wartość pochodziła z wartości zawartości, na przykład podczas sprawdzania (nie) równości. Wielu spodziewałoby się - co zrozumiałe - że możesz użyć dowolnej listy[1, 2] aby uzyskać ten sam klucz, w którym musiałbyś trzymać się dokładnie tego samego obiektu listy. Ale wyszukiwanie według wartości jest przerywane, gdy tylko lista używana jako klucz zostanie zmodyfikowana, a wyszukiwanie według tożsamości wymaga, abyś trzymał dokładnie tę samą listę - co nie wymaga żadnej innej powszechnej operacji na liście (przynajmniej nie przychodzi mi do głowy ).

Inne obiekty, takie jak moduły, i tak objectrobią znacznie większą sprawę z ich tożsamości obiektów (kiedy ostatnio miałeś wywołać dwa odrębne obiekty modułów sys?) I mimo to są przez to porównywane. Dlatego mniej zaskakujące - a nawet oczekiwane - jest to, że używane jako klucze dyktowania również w tym przypadku porównują według tożsamości.


32

Dlaczego nie mogę użyć listy jako klucza dyktowania w Pythonie?

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

(dla każdego, kto natknie się na to pytanie, szukając rozwiązania)

jak wyjaśnili inni tutaj, rzeczywiście nie możesz. Możesz jednak użyć jej reprezentacji łańcuchowej, jeśli naprawdę chcesz użyć swojej listy.


6
Przepraszam, naprawdę nie rozumiem twojego punktu widzenia. Nie różni się to od używania literałów łańcuchowych jako kluczy.
wim

12
Prawdziwe; Właśnie zobaczyłem tak wiele odpowiedzi wyjaśniających, dlaczego nie można używać list w kategoriach `` klucz musi być hashowany '', co jest tak prawdziwe, że chciałem zasugerować sposób obejścia tego, na wypadek gdyby ktoś (nowy) go szukał ...
Remi

5
Dlaczego po prostu nie przekonwertować listy na krotkę? Po co konwertować to na ciąg? Jeśli używasz krotki, będzie działać poprawnie z klasami, które mają niestandardową metodę porównania __eq__. Ale jeśli przekonwertujesz je na łańcuchy, wszystko zostanie porównane według reprezentacji ciągu.
Aran-Fey

dobra uwaga @ Aran-Fey. Po prostu upewnij się, że każdy element w krotce sam może być hashowany. np. krotka ([[1,2], [2,3]]) jako klucz nie będzie działać, ponieważ elementy krotki są nadal listami.
Remi

19

Właśnie odkryłem, że możesz zmienić Listę na krotkę, a następnie użyć jej jako kluczy.

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

działało jak urok!
Tabz

16

Problem polega na tym, że krotki są niezmienne, a listy nie. Rozważ następujące

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

Co powinno d[li]wrócić? Czy to ta sama lista? A co powiesz d[[1,2,3]]? Ma te same wartości, ale czy jest to inna lista?

Ostatecznie nie ma satysfakcjonującej odpowiedzi. Na przykład, jeśli jedynym działającym kluczem jest klucz oryginalny, to jeśli nie masz odniesienia do tego klucza, nigdy więcej nie możesz uzyskać dostępu do wartości. Z każdym innym dozwolonym kluczem możesz skonstruować klucz bez odniesienia do oryginału.

Jeśli obie moje sugestie działają, masz bardzo różne klucze, które zwracają tę samą wartość, co jest więcej niż trochę zaskakujące. Jeśli działa tylko oryginalna zawartość, klucz szybko się zepsuje, ponieważ listy są modyfikowane.


Tak, to ta sama lista, więc spodziewałbym d[li]się, że pozostanie 5. d[[1,2,3]]będzie odnosić się do innego obiektu listy jako klucza, więc będzie to KeyError. Naprawdę nie widzę jeszcze żadnego problemu ... poza tym, że zezwolenie na zbieranie kluczy może spowodować, że niektóre wartości dict będą niedostępne. Ale to jest problem praktyczny, a nie logiczny…
wim

@wim: d[list(li)]bycie KeyError jest częścią problemu. W prawie każdym innym przypadku użycia , libyłyby nie do odróżnienia od nowej listy z identycznej treści. To działa, ale dla wielu jest sprzeczne z intuicją. Poza tym, kiedy ostatnio naprawdę musiałeś używać listy jako klucza dyktowania? Jedynym przypadkiem użycia, jaki mogę sobie wyobrazić, jest to, że i tak haszujesz wszystko według tożsamości, aw takim przypadku powinieneś to po prostu zrobić, zamiast polegać __hash__i __eq__być opartym na tożsamości.

@delnan Czy problem polega po prostu na tym, że z powodu takich komplikacji nie byłby on zbyt przydatny? czy jest jakiś powód, dla którego może faktycznie złamać dyktando?
wim

1
@wim: Ten ostatni. Jak stwierdzono w mojej odpowiedzi, tak naprawdę nie łamie wymagań dotyczących klawiszy dyktowania, ale prawdopodobnie wprowadzi więcej problemów niż rozwiązuje.

1
@delnan - chciałeś powiedzieć „ten pierwszy”
Jason

9

Oto odpowiedź http://wiki.python.org/moin/DictionaryKeys

Co by się nie stało, gdybyś próbował użyć list jako kluczy, z hashem jako, powiedzmy, lokalizacją w pamięci?

Wyszukiwanie różnych list o tej samej zawartości dałoby różne wyniki, mimo że porównanie list o tej samej zawartości wskazywałoby, że są one równoważne.

A co z użyciem literału listy podczas wyszukiwania w słowniku?


4

Ponieważ listy są zmienne, dictklucze (i setskładowe) muszą być hashowalne, a haszowanie zmiennych obiektów jest złym pomysłem, ponieważ wartości skrótu powinny być obliczane na podstawie atrybutów instancji.

W tej odpowiedzi podam kilka konkretnych przykładów, miejmy nadzieję, że dodam wartość do istniejących odpowiedzi. Każdy wgląd dotyczy elementówset infrastruktury danych.

Przykład 1 : haszowanie zmiennego obiektu, gdzie wartość skrótu jest oparta na zmiennej charakterystyce obiektu.

>>> 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

Po mutacji stupidnie można go już znaleźć w dyktandzie, ponieważ zmienił się skrót. Tylko liniowe skanowanie listy kluczy dyktatu znajdujestupid .

Przykład 2 : ... ale dlaczego nie stałaby się wartością skrótu?

>>> 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

To również nie jest dobry pomysł, ponieważ równe obiekty powinny mieć identyczne hashowanie, aby można je było znaleźć w dictlubset .

Przykład 3 : ... ok, a co ze stałymi hashami we wszystkich instancjach ?!

>>> 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

Wydaje się, że wszystko działa zgodnie z oczekiwaniami, ale zastanów się, co się dzieje: kiedy wszystkie instancje twojej klasy generują tę samą wartość skrótu, wystąpi kolizja hashowania, ilekroć będzie więcej niż dwa wystąpienia kluczy w a dictlub w a set.

Znalezienie właściwej instancji z my_dict[key]lub key in my_dict(lub item in my_set) wymaga wykonania tylu sprawdzeń równości, ile jest instancji stupidlist3w kluczach dykta (w najgorszym przypadku). W tym momencie cel słownika - wyszukiwanie O (1) - jest całkowicie pokonany. Jest to pokazane w następujących czasach (zrobionych za pomocą IPythona).

Niektóre czasy na przykład 3

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

Jak widać, test członkostwa w naszym stupidlists_setjest nawet wolniejszy niż liniowe skanowanie całości lists_list, podczas gdy masz oczekiwany super szybki czas wyszukiwania (współczynnik 500) w zestawie bez mnóstwa kolizji hash.


TL; DR: możesz używać tuple(yourlist)jako dictkluczy, ponieważ krotki są niezmienne i haszowalne.


>>> x = (1,2,3321321321321,) >>> id (x) 139936535758888 >>> z = (1,2,3321321321321,) >>> id (z) 139936535760544 >>> id ((1, 2,3321321321321,)) 139936535810768 Te 3 mają takie same wartości krotki, ale inny identyfikator. Więc słownik z kluczem x nie będzie miał żadnej wartości dla klucza z?
Ashwani

@Ashwani, wypróbowałeś to?
timgeb

Tak, działa zgodnie z oczekiwaniami. Wątpię, że wszystkie krotki o tych samych wartościach mają różne identyfikatory. Więc na jakiej podstawie obliczany jest ten hash?
Ashwani

@Ashwani Wartość skrótu xi zjest taka sama. Jeśli coś w tym jest niejasne, otwórz nowe pytanie.
timgeb

1
@Ashwani hash(x)i hash(z).
timgeb

3

Twój awnser można znaleźć tutaj:

Dlaczego listy nie mogą być kluczami słownikowymi

Nowicjusze w Pythonie często zastanawiają się, dlaczego, chociaż język zawiera zarówno typ krotki, jak i listy, krotki są używane jako klucze słownika, a listy nie. Była to celowa decyzja projektowa i najlepiej można ją wytłumaczyć, najpierw rozumiejąc, jak działają słowniki Pythona.

Źródło i więcej informacji: http://wiki.python.org/moin/DictionaryKeys


1

Prosta odpowiedź na twoje pytanie jest taka, że ​​lista klas nie implementuje skrótu metody, który jest wymagany dla każdego obiektu, który chce być używany jako klucz w słowniku. Jednak powodem, dla którego hash nie jest zaimplementowany w taki sam sposób, jak na przykład klasa krotki (na podstawie zawartości kontenera), jest to, że lista jest zmienna, więc edycja listy wymagałaby ponownego obliczenia skrótu, co może oznaczać listę w teraz znajduje się w niewłaściwym wiadrze w dolnej tabeli mieszania. Zauważ, że ponieważ nie możesz modyfikować krotki (niezmiennej), nie występuje ten problem.

Na marginesie, rzeczywista implementacja wyszukiwania dictobjects jest oparta na algorytmie D z Knuth Vol. 3, ust. 6.4. Jeśli masz tę książkę do dyspozycji, warto ją przeczytać, a jeśli jesteś naprawdę, naprawdę zainteresowany, możesz rzucić okiem na komentarze programistów dotyczące rzeczywistej implementacji dictobject tutaj. Opisuje szczegółowo, jak to działa. Jest też wykład w Pythonie na temat implementacji słowników, które mogą Cię zainteresować. W pierwszych minutach przechodzą przez definicję klucza i czym jest hash.


-1

Zgodnie z dokumentacją Pythona 2.7.2:

Obiekt jest hashable, jeśli ma wartość hash, która nigdy nie zmienia się w trakcie swojego życia (potrzebuje metody hash ()) i można go porównać z innymi obiektami (potrzebuje metody eq () lub cmp ()). Obiekty z możliwością mieszania, które porównują równe wartości, muszą mieć tę samą wartość skrótu.

Hashability sprawia, że ​​obiekt może być używany jako klucz słownika i element członkowski zestawu, ponieważ te struktury danych używają wartości skrótu wewnętrznie.

Wszystkie niezmienne obiekty wbudowane Pythona są hashowalne, podczas gdy żadne zmienne kontenery (takie jak listy lub słowniki) nie są. Obiekty, które są instancjami klas zdefiniowanych przez użytkownika, są domyślnie mieszane; wszystkie porównują nierówności, a ich wartością skrótu jest id ().

Krotka jest niezmienna w tym sensie, że nie można dodawać, usuwać ani zastępować jej elementów, ale same elementy mogą być zmienne. Wartość skrótu listy zależy od wartości skrótu jej elementów, więc zmienia się, gdy zmieniasz elementy.

Użycie id dla skrótów list oznaczałoby, że wszystkie listy są porównywane inaczej, co byłoby zaskakujące i niewygodne.


1
To nie odpowiada na pytanie, prawda? hash = idnie łamie niezmiennika na końcu pierwszego akapitu, pytanie brzmi, dlaczego nie jest to zrobione w ten sposób.

@delnan: Dodałem ostatni akapit, aby wyjaśnić.
Nicola Musatti

-1

Słownik to HashMap, który przechowuje mapę twoich kluczy, wartość przekonwertowaną na zakodowany nowy klucz i mapowanie wartości.

coś takiego (kod pseudo):

{key : val}  
hash(key) = val

Jeśli zastanawiasz się, jakie są dostępne opcje, których możesz użyć jako klucza do swojego słownika. Następnie

wszystko, co jest hashowalne (można przekonwertować na hash i przechowywać wartość statyczną, tj. niezmienne, aby utworzyć klucz hashowany, jak wspomniano powyżej) jest kwalifikowalne, ale ponieważ lista lub obiekty zestawu mogą się zmieniać w ruchu, więc hash (klucz) powinien również wymagać by się różnić tylko po to, by być zsynchronizowanym z listą lub zestawem.

Możesz spróbować :

hash(<your key here>)

Jeśli działa dobrze, można go użyć jako klucza do słownika lub przekonwertować go na coś, co można skasować.


W skrócie :

  1. Przekonwertuj tę listę na tuple(<your list>).
  2. Przekonwertuj tę listę na str(<your list>).

-1

dictklucze muszą być hashowane. Listy są modyfikowalne i nie zapewniają prawidłowej metody mieszania .

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.