Päivitä Python-taitosi: Sanakirjan tutkiminen

hash-taulukko (hash-kartta) on tietorakenne, joka toteuttaa assosiatiivisen taulukon abstraktin tietotyypin, rakenteen, joka voi yhdistää avaimet arvoihin.

Jos se haisee kuin Python dict, tuntuu kuin dictja näyttää siltä ... hyvin, sen on oltava dict. Ehdottomasti! Voi, ja setmyös ...

Huh?

Sanakirjat ja joukot Pythonissa toteutetaan hash-taulukon avulla. Aluksi se saattaa kuulostaa pelottavalta, mutta tutkittaessa asiaa kaiken pitäisi olla selvää.

Tavoite

Tässä artikkelissa selvitetään, kuinka a dicton toteutettu Pythonissa, ja rakennamme oman (yksinkertaisen) toteutuksen. Artikkeli on jaettu kolmeen osaan, ja mukautetun sanakirjan rakentaminen tapahtuu kahdessa ensimmäisessä:

  1. Ymmärtäminen, mitä hash-taulukot ovat ja miten niitä käytetään
  2. Sukellus Pythonin lähdekoodiin ymmärtääkseen paremmin sanakirjojen toteutusta
  3. Sanakirjan ja muiden tietorakenteiden, kuten luetteloiden ja sarjojen, erojen tutkiminen

Mikä on hash-taulukko?

Hajautustaulukko on rakenne, joka on suunniteltu tallentamaan luettelo avainarvopareista vaarantamatta rakenteen manipuloinnin ja haun nopeutta ja tehokkuutta.

Hajautustaulukon tehokkuus johtuu hajautusfunktiosta - funktiosta, joka laskee avain-arvo-parin indeksin. Tämä tarkoittaa, että voimme nopeasti lisätä, etsiä ja poistaa elementtejä, koska tiedämme niiden hakemiston muistiryhmässä.

Monimutkaisuus alkaa, kun kahdessa avaimessamme on sama arvo. Tätä skenaariota kutsutaan hash-törmäykseksi . On olemassa monia erilaisia ​​tapoja käsitellä törmäystä, mutta käsittelemme vain Pythonin tapaa. Emme mene liian syvälle hash-taulukko-selityksellämme, jotta tämä artikkeli olisi aloittelijaystävällinen ja Python-keskittynyt.

Varmista, että kiedoimme pään hash-pöytien käsitteen ympärille ennen kuin jatkaamme. Aloitamme luomalla luurankoja hyvin (hyvin) yksinkertaiselle dictmukautuksellemme, joka koostuu vain lisäys- ja hakumenetelmistä, käyttämällä joitain Pythonin dunder-menetelmiä. Meidän on alustettava hash-taulukko tietyn koon luettelolla ja sallittava tilaus ([] -merkki) sille:

Nyt hash-taulukon luettelossa on oltava tietyt rakenteet, joista jokainen sisältää avaimen, arvon ja hash:

Perusesimerkki

Pieni yritys, jolla on 10 työntekijää, haluaa pitää kirjaa työntekijöidensä jäljellä olevista sairauspäivistä. Voimme käyttää seuraavaa hash-toimintoa, joten kaikki mahtuu muistiryhmään:

length of the employee's name % TABLE_SIZE

Määritetään hash-funktiomme Entry-luokassa:

Nyt voimme alustaa 10 elementin taulukon taulukossamme:

Odota! Ajatelkaamme sitä uudestaan. Todennäköisesti käsittelemme joitain hash-törmäyksiä. Jos meillä on vain 10 elementtiä, on paljon vaikeampaa löytää avoin tila törmäyksen jälkeen. Päätetään, että pöydässämme on kaksinkertainen koko - 20 elementtiä! Se on kätevä tulevaisuudessa, lupaan.

Jokainen työntekijä lisätään nopeasti seuraamalla logiikkaa:

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

Joten lisäystapa näyttää seuraavalta (ei vielä hash-törmäysten käsittelyä):

Etsinnässä teemme periaatteessa saman:

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

Emme ole vielä valmiita!

Python-törmäysten käsittely

Python käyttää avoimen osoitteen menetelmää törmäysten käsittelemiseksi. Se muuttaa myös hash-taulukoiden kokoa, kun se saavuttaa tietyn koon, mutta emme keskustele siitä. Avaa osoitteen määrittely Wikipediasta:

Toisessa strategiassa, jota kutsutaan avoimeksi osoitteeksi, kaikki merkinnät tallennetaan itse ryhmään. Kun uusi merkintä on lisättävä, kauhat tutkitaan, alkaen hash-to-urasta ja jatkamalla jossain koetinjärjestyksessä , kunnes vapaa paikka löytyy. Kun etsit merkintää, ämpärit skannataan samassa järjestyksessä, kunnes joko kohdetietue tai käyttämätön matriisipaikka löytyy, mikä osoittaa, että taulukossa ei ole tällaista avainta.

Tarkastellaan arvon noutoprosessia keytarkastelemalla Python-lähdekoodia (kirjoitettu C-muodossa):

  1. Laske hash key
  2. Laske indexkohteen arvo hash & maskmistä mask = HASH_TABLE_SIZE-1(yksinkertaisesti sanottuna - ota N viimeistä bittiä hasisbitistä):
i = (size_t)hash & mask;

3. Jos tyhjä, palaa, DKIX_EMPTYmikä lopulta tarkoittaa KeyError:

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

4. Jos se ei ole tyhjä, vertaa avaimet ja tiivisteet ja aseta value_addrosoite todelliseen arvo-osoitteeseen, jos se on sama:

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

ja:

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

5. Jos se ei ole yhtä suuri, käytä hashin eri bittejä (tässä selitetty algoritmi) ja siirry vaiheeseen 3 uudelleen:

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

Tässä on kaavio koko prosessin havainnollistamiseksi:

Lisäysprosessi on melko samanlainen - jos löydetty paikka on tyhjä, merkintää lisätään, jos se ei ole tyhjä, verrataan avainta ja hashia - jos sama, korvaamme arvon ja jos ei, jatkaamme etsintää uusi paikka perturbalgoritmilla.

Lainaa ideoita Pythonilta

Voimme lainata Pythonin ajatusta verrata kunkin merkinnän molempia avaimia ja tiivistelmiä syöttöobjektiimme (korvaa edellinen menetelmä):

Hash-taulukossamme ei vieläkään ole törmäyksen käsittelyä - toteutetaan yksi! Kuten aiemmin näimme, Python tekee sen vertaamalla merkintöjä ja vaihtamalla sitten bittien peitteen, mutta teemme sen käyttämällä menetelmää, jota kutsutaan lineaariseksi koetukseksi (joka on avoimen osoitteen muoto, selitetty yllä):

Kun hash-toiminto aiheuttaa törmäyksen kartoittamalla uuden avaimen hash-taulukon soluun, joka on jo toisen avaimen käytössä, lineaarinen koetus etsii taulukosta lähintä seuraavaa vapaata sijaintia ja lisää uuden avaimen sinne.

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

Tilaus riippuu lisäysjärjestyksestä

Sanelun järjestys riippuu lisäyksen historiasta. Jos syötämme merkinnän tietyllä hashilla ja sen jälkeen merkinnän, jolla on sama hash, toinen merkintä päätyy eri paikkaan, jos haluaisimme lisätä sen ensin.

Ennen kuin menet…

Kiitos lukemisesta! Voit seurata minua Mediumissa saadaksesi lisää näistä artikkeleista tai GitHubista löytääksesi hienoja repoja :)

Jos pidit tästä artikkelista, pidä taputuspainiketta painettuna? auttaa muita löytämään sen. Mitä kauemmin pidät sitä, sitä enemmän taputat!

Ja älä epäröi jakaa ajatuksiasi alla olevissa kommenteissa tai korjata minua, jos minulla on jotain vikaa.

Lisäresurssit

  1. Hash Crash: Hash-taulukoiden perusteet
  2. Mighty Dictionary
  3. Johdanto algoritmeihin