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

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?

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.

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.

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

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.

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?

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.

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

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.

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.

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

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