Jak zaimplementowano set ()?

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

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.

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

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

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

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