Paaugstiniet savas Python prasmes: pārbaudiet vārdnīcu

jaukšanas tabula (jaukšanas karte) ir datu struktūra, kas ievieš asociatīvā masīva abstrakto datu tipu, struktūra, kas var attēlot atslēgas vērtībām.

Ja tas smaržo pēc Python dict, jūtas kā dictun izskatās ... labi, tam jābūt dict. Pilnīgi! Ak, un setarī ...

Huh?

Vārdnīcas un kopas Python tiek ieviestas, izmantojot jaukšanas tabulu. Sākumā tas var likties biedējoši, taču, turpinot izmeklēšanu, visam jābūt skaidram.

Mērķis

Šajā rakstā mēs atklāsim, kā a dicttiek ieviests Python, un mēs izveidosim savu (vienkāršu) ieviešanu. Raksts ir sadalīts trīs daļās, un mūsu pielāgotās vārdnīcas veidošana notiek pirmajās divās:

  1. Izpratne par to, kas ir hash tabulas un kā tās izmantot
  2. Ieniršana Python avota kodā, lai labāk izprastu, kā tiek ieviestas vārdnīcas
  3. Izpētiet atšķirības starp vārdnīcu un citām datu struktūrām, piemēram, sarakstiem un kopām

Kas ir hash tabula?

Hash tabula ir struktūra, kas paredzēta galveno vērtību pāru saraksta glabāšanai, neapdraudot struktūras manipulācijas un meklēšanas ātrumu un efektivitāti.

Jaukšanas tabulas efektivitāte tiek iegūta no hash funkcijas - funkcijas, kas aprēķina atslēgas un vērtības pāra indeksu. Tas nozīmē, ka mēs varam ātri ievietot, meklēt un noņemt elementus, jo mēs zinām to indeksu atmiņas masīvā.

Sarežģītība sākas, kad diviem mūsu taustiņiem ir vienāda vērtība. Šo scenāriju sauc par hash sadursmi . Ir daudz dažādu veidu, kā rīkoties sadursmes gadījumā, taču mēs apskatīsim tikai Python ceļu. Mēs nepievērsīsimies pārāk daudz mūsu hash tabulas skaidrojuma, lai šis raksts būtu draudzīgs iesācējiem un orientēts uz Python.

Pārliecināsimies, ka pirms došanās tālāk mēs aptinām galvu ap hash tabulu jēdzienu. Mēs sāksim ar to, ka izveidosim skeletus mūsu ļoti (ļoti) vienkāršajai paražai, kas dictsastāv tikai no ievietošanas un meklēšanas metodēm, izmantojot dažas no Python's dunder metodēm. Mums būs jāinicializē jaukšanas tabula ar noteikta lieluma sarakstu un jāiespējo abonēšana ([] zīme):

Tagad mūsu hash tabulu sarakstā ir jābūt īpašām struktūrām, katrā no tām ir atslēga, vērtība un hash:

Pamata piemērs

Neliels uzņēmums, kurā strādā 10 darbinieki, vēlas veikt uzskaiti par to, kā viņu darbiniekiem ir atlikušās slimības dienas. Mēs varam izmantot šādu hash funkciju, tāpēc viss var ietilpt atmiņas masīvā:

length of the employee's name % TABLE_SIZE

Definēsim savu hash funkciju klasē Entry:

Tagad mūsu tabulā varam inicializēt 10 elementu masīvu:

Pagaidi! Padomāsim to pārdomāt. Mēs, visticamāk, novērsīsim dažas hash sadursmes. Ja mums ir tikai 10 elementi, mums pēc sadursmes būs daudz grūtāk atrast atvērtu telpu. Izlemsim, ka mūsu galdam būs divkāršs izmērs - 20 elementi! Nākotnē tas noderēs, es apsolu.

Lai ātri ievietotu katru darbinieku, mēs ievērosim loģiku:

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

Tātad mūsu ievietošanas metode izskatīsies šādi (vēl nav hash sadursmju apstrādes):

Meklēšanai mēs pamatā darām to pašu:

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

Mēs vēl neesam pabeiguši!

Python sadursmes apstrāde

Python sadursmju apstrādei izmanto metodi ar nosaukumu Open Addressing. Tas arī maina jaucējgaldu izmērus, kad tie sasniedz noteiktu lielumu, taču mēs šo aspektu neapspriedīsim. Atvērt adresēšanas definīciju no Wikipedia:

Citā stratēģijā, ko sauc par atvērto adresēšanu, visi ierakstu ieraksti tiek glabāti pašā segmenta masīvā. Kad ir jāievieto jauns ieraksts, tiek pārbaudīti segmenti, sākot ar jaukto slotu un turpinot kādu zondes secību , līdz tiek atrasts neizmantots slots. Meklējot ierakstu, segmenti tiek skenēti vienā secībā, līdz tiek atrasts vai nu mērķa ieraksts, vai arī tiek atrasts neizmantots masīva slots, kas norāda, ka tabulā šādas atslēgas nav.

Pārbaudīsim vērtības iegūšanas procesu key, apskatot Python avota kodu (rakstīts C):

  1. Aprēķiniet hash no key
  2. Aprēķināt indexno posteņa hash & mask, kurā mask = HASH_TABLE_SIZE-1(vienkāršā izteiksmē - ņem N pēdējos bitus no hash biti):
i = (size_t)hash & mask;

3. Ja tukšs, atgriezieties, DKIX_EMPTYkas galu galā nozīmē KeyError:

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

4. Ja tas nav tukšs, salīdziniet atslēgas un jaucējus un iestatiet value_addradresi ar faktiskās vērtības adresi, ja tā ir vienāda:

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

un:

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

5. Ja tas nav vienāds, izmantojiet dažādus jaukuma bitus (šeit izskaidrots algoritms) un vēlreiz pārejiet pie 3. darbības:

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

Šī diagramma ilustrē visu procesu:

Ievietošanas process ir diezgan līdzīgs - ja atrastā slota ir tukša, ieraksts tiek ievietots, ja tas nav tukšs, tad mēs salīdzinām atslēgu un jaucējinstrumentu - ja vienāds, mēs aizstājam vērtību un, ja nē, mēs turpinām meklēt meklējumus jauna vieta ar perturbalgoritmu.

Ideju aizņemšanās no Python

Mēs varam aizņemties Python ideju salīdzināt katra ieraksta atslēgas un jaucējus ar mūsu ieraksta objektu (aizstājot iepriekšējo metodi):

Mūsu hash tabulā joprojām nav sadursmes - ieviesīsim to! Kā mēs redzējām iepriekš, Python to dara, salīdzinot ierakstus un pēc tam mainot bitu masku, bet mēs to darīsim, izmantojot metodi, ko sauc par lineāro zondēšanu (kas ir atvērtas adresēšanas forma, kas izskaidrota iepriekš):

Kad jaukšanas funkcija izraisa sadursmi, kartējot jaunu atslēgu hash tabulas šūnā, kuru jau aizņem cita atslēga, lineārā zondēšana tabulā meklē tuvāko sekojošo brīvo vietu un ievieto tur jauno atslēgu.

Tātad, ko mēs darīsim, ir virzīties uz priekšu, līdz atrodam atvērtu telpu. Ja atceraties, mēs esam ieviesuši mūsu galdu ar divkāršu izmēru (20 elementi, nevis 10) - šeit tas ir noderīgs . Kad mēs virzīsimies uz priekšu, mūsu meklēšana atklātā telpā būs daudz ātrāka, jo tur ir vairāk vietas!

Bet mums ir problēma. Ko darīt, ja kāds ļauns mēģina ievietot 11. elementu? Mums ir jāizvirza kļūda (šajā rakstā mēs nenodarbosimies ar tabulas lieluma maiņu). Mēs savā tabulā varam turēt aizpildītu ierakstu skaitītāju:

Tagad ieviesīsim to pašu mūsu meklēšanas metodē:

Pilns kods ir atrodams šeit.

Tagad uzņēmums var droši uzglabāt slimības dienas katram darbiniekam:

Python komplekts

Atgriežoties pie raksta sākuma, setun dictPython tiek ieviesti ļoti līdzīgi, katram ierakstam setizmantojot tikai keyun hashiekšpusē, kā redzams pirmkodā:

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

Atšķirībā no dicttā ir vērtība:

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;

Izrāde un kārtība

Laika salīdzinājums

Es domāju, ka tagad ir skaidrs, ka meklēšanas, ievietošanas (noteiktā vietā) un dzēšanas ziņā a dictir daudz ātrāks nekā list(un aizņem vairāk vietas atmiņā). Apstiprināsim šo pieņēmumu ar kādu kodu (es izmantoju kodu 2017. gada MacBook Pro):

Tālāk ir norādīts testa kods (vienu dictreizi listaizstājot un vienreiz aizstājot d):

Rezultāti ir gandrīz tādi, kādus mēs gaidījām ..

dict: 0.015382766723632812sekundes

list:55.5544171333313 sekundes

Pasūtījums ir atkarīgs no ievietošanas kārtības

Dikta secība ir atkarīga no ievietošanas vēstures. Ja mēs ievietojam ierakstu ar noteiktu hash, un pēc tam ieraksts ar to pašu hash, otrais ieraksts nonāks citā vietā, tad, ja mēs to ievietotu vispirms.

Pirms tu ej…

Paldies, ka lasījāt! Jūs varat sekot man vietnē Medium, lai uzzinātu vairāk par šiem rakstiem, vai vietnē GitHub, lai atklātu dažas foršas repo :)

Ja jums patika šis raksts, lūdzu, turiet nospiestu pogu? lai palīdzētu citiem to atrast. Jo ilgāk to turat, jo vairāk klapu dodat!

Un nevilcinieties dalīties savās domās zemāk esošajos komentāros vai labot mani, ja man kaut kas nav kārtībā.

Papildu resursi

  1. Hash Crash: Hash tabulu pamati
  2. Varenā vārdnīca
  3. Ievads algoritmos