Nadogradite svoje Python vještine: ispitivanje rječnika

Programiranje
hash tablica (hash map) je struktura podataka koja implementira asocijativni niz apstraktnih vrsta podataka, strukturu koja može preslikati ključeve u vrijednosti.

Ako miriše na Python dict, osjeća se poput dicti izgleda poput njega ... pa, to mora biti dict. Apsolutno! Oh, i settakođer ...

A?

Rječnici i skupovi u Pythonu implementirani su pomoću hash tablice. U početku može zvučati zastrašujuće, ali kako dalje istražujemo, sve bi trebalo biti jasno.

Cilj

Kroz ovaj ćemo članak otkriti kako se a dictimplementira u Pythonu i izgradit ćemo vlastitu implementaciju (jednostavne). Članak je podijeljen u tri dijela, a izrada našeg prilagođenog rječnika odvija se u prva dva:

  1. Razumijevanje što su hash tablice i kako ih koristiti
  2. Uronite u izvorni kod Pythona kako biste bolje razumjeli kako se rječnici primjenjuju
  3. Istraživanje razlika između rječnika i drugih struktura podataka poput popisa i skupova

Što je hash tablica?

Hash tablica je struktura koja je dizajnirana za spremanje popisa parova ključ / vrijednost, bez ugrožavanja brzine i učinkovitosti manipulacije i pretraživanja strukture.

Učinkovitost hash tablice izvedena je iz hash funkcije - funkcije koja izračunava indeks para ključ / vrijednost - što znači da možemo brzo umetnuti, pretraživati ​​i uklanjati elemente budući da znamo njihov indeks u memorijskom polju.

Složenost započinje kada dva naša ključa imaju vrijednost iste vrijednosti. Ovaj se scenarij naziva hash kolizija . Postoji mnogo različitih načina rješavanja sudara, ali mi ćemo pokriti samo Pythonov put. Nećemo ulaziti preduboko u naše objašnjenje hash tablice radi održavanja ovog članka početnim i usredotočenim na Python.

Obavezno smo se omotali oko koncepta hash tablica prije nego što krenemo dalje. Počet ćemo s izradom kostura za naš vrlo (vrlo) jednostavan običaj koji se dictsastoji samo od metoda umetanja i pretraživanja, koristeći neke od Pythonovih metoda dundera. Trebat ćemo inicijalizirati hash tablicu popisom određene veličine i omogućiti pretplatu (znak []) za nju:

Sada naš popis hash tablica mora sadržavati određene strukture, od kojih svaka sadrži ključ, vrijednost i hash:

Osnovni primjer

Mala tvrtka s 10 zaposlenika želi voditi evidenciju koja sadrži njihove zaposlenike koji ostaju na bolovanju. Možemo koristiti sljedeću hash funkciju, tako da sve može stati u memorijski niz:

length of the employee's name % TABLE_SIZE

Definirajmo našu hash funkciju u klasi Entry:

Sada možemo inicijalizirati niz od 10 elemenata u našoj tablici:

Čekati! Razmislimo. Najvjerojatnije ćemo riješiti neke hash sudare. Ako imamo samo 10 elemenata, bit će nam teže pronaći otvoren prostor nakon sudara. Odlučimo da će naša tablica imati dvostruku veličinu - 20 elemenata! Obećavam, dobro će doći u budućnosti.

Da bismo brzo ubacili svakog zaposlenika, slijedit ćemo logiku:

array[length of the employee's name % 20] = employee_remaining_sick_days

Tako će naša metoda umetanja izgledati ovako (još nema obrade hash sudara):

Za pretraživanje u osnovi radimo isto:

array[length of the employee's first name % 20]

Još nismo gotovi!

Upravljanje sudarom Pythona

Python za obradu sudara koristi metodu koja se naziva Otvoreno adresiranje. Također mijenja veličinu hash tablica kad dosegne određenu veličinu, ali nećemo raspravljati o tom aspektu. Otvorite definiciju adresiranja s Wikipedije:

U drugoj strategiji, koja se naziva otvoreno adresiranje, svi se unosi pohranjuju u sam niz polja. Kada treba ubaciti novi unos, ispituju se segmenti, počevši od utora za raspršivanje i nastavljajući u nekom slijedu sonde , sve dok se ne pronađe neuzet utor. Kada se traži unos, segmenti se skeniraju u istom slijedu, sve dok se ne pronađe ciljni zapis ili ne pronađe neiskorišteni utor polja, što ukazuje da u tablici nema takvog ključa.

Ispitajmo postupak dohvaćanja vrijednosti keypregledavanjem izvornog koda Pythona (napisanog na C):

  1. Izračunaj hash od key
  2. Izračunajte indexstavku prema tome hash & maskgdje mask = HASH_TABLE_SIZE-1(jednostavnim riječima - uzmite N zadnjih bitova iz hash bitova):
i = (size_t)hash & mask;

3. Ako je prazno, vratite DKIX_EMPTYšto se na kraju prevodi u KeyError:

if (ix == DKIX_EMPTY) { *value_addr = NULL; return ix;}

4. Ako nisu prazni, usporedite ključeve i hashove i postavite value_addradresu na stvarnu adresu vrijednosti ako je jednaka:

if (ep->me_key == key) { *value_addr = ep->me_value; return ix;}

i:

if (dk == mp->ma_keys && ep->me_key == startkey) { if (cmp > 0) { *value_addr = ep->me_value; return ix; }}

5. Ako nije jednako, upotrijebite različite bitove hasha (algoritam ovdje objašnjen) i prijeđite na korak 3 opet:

perturb >>= PERTURB_SHIFT;i = (i*5 + perturb + 1) & mask;

Evo dijagrama koji ilustrira cijeli postupak:

Proces umetanja prilično je sličan - ako je pronađeni utor prazan, unos se ubacuje, ako nije prazan, uspoređujemo ključ i hash - ako je jednak, zamjenjujemo vrijednost, a ako ne nastavljamo našu potragu za pronalaženjem novo mjesto s perturbalgoritmom.

Posuđivanje ideja od Pythona

Možemo posuditi Pythonovu ideju uspoređivanja oba ključa i heša svakog unosa s našim objektom unosa (zamjenjujući prethodnu metodu):

Naša hash tablica još uvijek nema nikakvih postupaka za sudare - implementirajmo jedan! Kao što smo ranije vidjeli, Python to čini usporedbom unosa, a zatim promjenom maske bitova, ali to ćemo učiniti metodom koja se naziva linearno ispitivanje (koja je oblik otvorenog adresiranja, gore objašnjeno):

Kada hash funkcija uzrokuje sudar preslikavanjem novog ključa na ćeliju hash tablice koja je već zauzeta drugim ključem, linearno sondiranje pretražuje u tablici najbliže slijedeće slobodno mjesto i tamo ubacuje novi ključ.

So what we’re going to do is to move forward until we find an open space. If you recall, we implemented our table with double the size (20 elements and not 10) — This is where it comes handy. When we move forward, our search of an open space will be much quicker because there’s more room!

But we have a problem. What if someone evil tries to insert the 11th element? We need to raise an error (we won’t be dealing with table resizing in this article). We can keep a counter of filled entries in our table:

Now let’s implement the same in our searching method:

The full code can be found here.

Now the company can safely store sick days for each employee:

Python Set

Going back to the beginning of the article, set and dict in Python are implemented very similarly, with set using only key and hash inside each record, as can be seen in the source code:

typedef struct { PyObject *key; Py_hash_t hash; /* Cached hash code of the key */} setentry;

As opposed to dict, that holds a value:

typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */} PyDictKeyEntry;

Performance and Order

Time comparison

I think it’s now clear that a dict is much much faster than a list (and takes way more memory space), in terms of searching, inserting (at a specific place) and deleting. Let's validate that assumption with some code (I am running the code on a 2017 MacBook Pro):

And the following is the test code (once for the dict and once for the list, replacing d):

The results are, well, pretty much what we expected..

dict: 0.015382766723632812 seconds

list:55.5544171333313 seconds

Order depends on insertion order

The order of the dict depends on the history of insertion. If we insert an entry with a specific hash, and afterwards an entry with the same hash, the second entry is going to end up in a different place then if we were to insert it first.

Before you go…

Thanks for reading! You can follow me on Medium for more of these articles, or on GitHub for discovering some cool repos :)

If you enjoyed this article, please hold down the clap button ? to help others find it. The longer you hold it, the more claps you give!

And do not hesitate to share your thoughts in the comments below, or correct me if I got something wrong.

Additional resources

  1. Hash Crash: The Basics of Hash Tables
  2. The Mighty Dictionary
  3. Introduction to Algorithms