Jak zaimplementowano set ()?

151

Widziałem ludzi, którzy mówili, że setobiekty w Pythonie mają sprawdzanie członkostwa O (1). Jak są wdrażane wewnętrznie, aby to umożliwić? Jakiego rodzaju struktury danych używa? Jakie inne konsekwencje ma to wdrożenie?

Każda odpowiedź była naprawdę pouczająca, ale mogę zaakceptować tylko jedną, więc podam najbliższą odpowiedź na moje pierwotne pytanie. Dzięki wszystkim za informację!

Daenyth
źródło

Odpowiedzi:

139

Według tego wątku :

Rzeczywiście, zestawy CPythona są implementowane jako coś w rodzaju słowników z wartościami fikcyjnymi (klucze są elementami zestawu), z pewnymi optymalizacjami, które wykorzystują ten brak wartości

Zasadniczo więc setużywa tablicy hashy jako podstawowej struktury danych. Wyjaśnia to sprawdzanie członkostwa O (1), ponieważ wyszukanie elementu w tablicy hashy jest średnio operacją O (1).

Jeśli masz takie skłonności, możesz nawet przeglądać kod źródłowy CPythona w poszukiwaniu zestawu, który według Achima Domma jest głównie wycinaniem i wklejaniem z dictimplementacji.

Justin Ethier
źródło
18
IIRC, oryginalna setimplementacja faktycznie miała dict wartości fikcyjne i została później zoptymalizowana.
dan04
1
Czy wielki O nie jest najgorszym scenariuszem? Jeśli możesz znaleźć instancję, w której czas jest O (n), to jest O (n) .. Nie rozumiem teraz niczego ze wszystkich tych samouczków.
Claudiu Creanga
4
Nie, średni przypadek to O (1), ale najgorszy przypadek to O (N) przy przeszukiwaniu tablicy skrótów.
Justin Ethier,
4
@ClaudiuCreanga to stary komentarz, ale tylko po to, by wyjaśnić: notacja duże-O wskazuje górne granice tempa wzrostu rzeczy, ale możesz górne ograniczenie wzrostu średniej wydajności przypadku i możesz osobno ograniczyć wzrost najgorszego przypadku występ.
Kirk Boyer,
79

Kiedy ludzie mówią, że zestawy mają sprawdzanie członkostwa O (1), mówią o przeciętnym przypadku. W najgorszym przypadku (kiedy wszystkie zaszyfrowane wartości kolidują) sprawdzanie członkostwa to O (n). Zobacz wiki Pythona na temat złożoności czasowej .

Artykuł w Wikipedii mówi, że najlepsza złożoność czasowa przypadku dla tabeli skrótów, która nie zmienia rozmiaru, to O(1 + k/n). Ten wynik nie ma bezpośredniego zastosowania do zestawów Pythona, ponieważ zestawy Pythona używają tablicy skrótów, która zmienia rozmiar.

Nieco dalej w artykule na Wikipedii napisano, że dla przeciętnego przypadku, przy założeniu prostej, jednolitej funkcji mieszającej, złożoność czasowa jest taka O(1/(1-k/n)), w której k/nmożna ją ograniczyć przez stałą c<1.

Big-O odnosi się tylko do asymptotycznego zachowania jako n → ∞. Ponieważ k / n może być ograniczone stałą, c <1, niezależną od n ,

O(1/(1-k/n))jest nie większa niż O(1/(1-c))która jest równoważna O(constant)= O(1).

Zatem zakładając jednolite proste haszowanie, sprawdzanie członkostwa w zestawach Pythona wynosi średnioO(1) .

unutbu
źródło
14

Myślę, że to częsty błąd, setwyszukiwanie (lub haszowanie w tym przypadku) nie jest O (1).
z Wikipedii

W najprostszym modelu funkcja skrótu jest całkowicie nieokreślona, ​​a tabela nie zmienia rozmiaru. Aby uzyskać najlepszy możliwy wybór funkcji skrótu, tabela o rozmiarze n z otwartym adresowaniem nie ma kolizji i zawiera do n elementów, z pojedynczym porównaniem dla pomyślnego wyszukiwania, a tabela o rozmiarze n z łączeniem i k kluczy ma minimalne maks. (0, kn) kolizje i O (1 + k / n) porównań dla wyszukiwania. W przypadku najgorszego wyboru funkcji skrótu każde wstawienie powoduje kolizję, a tablice skrótów zdegenerowane są do wyszukiwania liniowego, z porównaniami amortyzowanymi Ω (k) na wstawienie i do k porównań w celu pomyślnego wyszukiwania.

Powiązane: Czy hashmap Java to naprawdę O (1)?

Shay Erlichmen
źródło
4
Ale szukanie elementów zajmuje im stały czas: python -m timeit -s "s = set (range (10))" "5 in s" 10000000 pętli, najlepiej 3: 0,0642 usek na pętlę <--> python - m timeit -s "s = set (range (10000000))" "5 in s" 10000000 pętli, najlepsze z 3: 0,0634 usek na pętlę ... i to jest największy zestaw, który nie generuje błędów MemoryErrors
Jochen Ritzel
2
@ THC4k Udowodniłeś tylko, że wyszukiwanie X odbywa się w stałym czasie, ale nie oznacza to, że czas na wyszukiwanie X + Y zajmie tyle samo czasu, o co chodzi w O (1).
Shay Erlichmen
3
@intuited: Tak, ale powyższy test nie dowodzi, że możesz wyszukać „5” w tym samym czasie, co „485398” lub inną liczbę, która może znajdować się w okropnej przestrzeni kolizyjnej. Nie chodzi o wyszukanie tego samego elementu w hashu o różnej wielkości w tym samym czasie (w rzeczywistości nie jest to wcale wymagane), ale raczej chodzi o to, czy możesz uzyskać dostęp do każdego wpisu w tym samym czasie w bieżącej tabeli - coś, co jest w zasadzie niemożliwe do osiągnięcia przez tablice skrótów, ponieważ generalnie zawsze będą kolizje.
Nick Bastin,
3
Innymi słowy, czas potrzebny na wyszukiwanie zależy od liczby przechowywanych wartości, ponieważ zwiększa to prawdopodobieństwo kolizji.
intuicyjnie z
3
@intuited: nie, to nieprawda. Gdy liczba przechowywanych wartości wzrośnie, Python automatycznie zwiększy rozmiar tablicy hashy, a szybkość kolizji pozostanie mniej więcej stała. Zakładając, że algorytm skrótu O (1) jest równomiernie rozłożony, wyszukiwanie tablic haszujących jest amortyzowane O (1). Możesz obejrzeć prezentację wideo „The Mighty Dictionary” python.mirocommunity.org/video/1591/…
Lie Ryan
13

Wszyscy mamy łatwy dostęp do źródła , w którym powyższy komentarz set_lookkey()mówi:

/* set object implementation
 Written and maintained by Raymond D. Hettinger <[email protected]>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...
gimel
źródło
2
Ta odpowiedź będzie korzystać z C podświetlanie składni . Podświetlanie komentarza w składni Pythona wygląda naprawdę źle.
user202729
Odnośnie komentarza „To daje nam hybrydę liniowego sondowania i otwartego adresowania”, czy liniowe sondowanie nie jest rodzajem rozwiązywania kolizji w otwartym adresowaniu, jak opisano w en.wikipedia.org/wiki/Open_addressing ? Dlatego sondowanie liniowe jest podtypem adresowania otwartego, a komentarz nie ma sensu.
Alan Evangelista
2

Aby nieco bardziej podkreślić różnicę między set'si dict's, oto fragment setobject.csekcji komentarzy, który wyjaśnia główną różnicę między zestawami a dyktami.

Przypadki użycia dla zestawów różnią się znacznie od słowników, w których istnieje większe prawdopodobieństwo obecności wyszukanych kluczy. Natomiast zestawy dotyczą przede wszystkim testowania członkostwa, w przypadku których obecność elementu nie jest z góry znana. W związku z tym implementacja zestawu musi zostać zoptymalizowana zarówno dla przypadku znalezionego, jak i nie znalezionego.

źródło na github

user1767754
źródło