Kuidas rakendada JavaScripti lihtsat räsitabelit

Kui ilus on {}?

See võimaldab teil väärtusi võtmete kaupa salvestada ja neid väga kulutõhusalt kätte saada ( O(1)lisateavet selle kohta hiljem).

Selles postituses tahan rakendada väga elementaarset räsitabelit ja heita pilgu selle sisemisele tööle, et selgitada üht kõige geniaalsemat ideed arvutiteaduses.

Probleem

Kujutage ette, et ehitate uut programmeerimiskeelt: kõigepealt on teil üsna lihtsad tüübid (stringid, täisarvud, ujukid jne) ja seejärel jätkake väga elementaarsete andmestruktuuride juurutamist. Kõigepealt []mõtlete välja massiivi ( ), seejärel tuleb räsitabel (teisiti tuntud kui sõnastik, assotsiatiivne massiiv, hashmap, kaart ja ... loend jätkub).

Kas olete mõelnud, kuidas need toimivad? Kuidas nad nii kuradima kiiresti on?

Oletame, et JavaScripti ei olnud {}või new Map(), ja rakendagem omaenda DumbMap!

Kommentaar keerukuse kohta

Enne palli veeretamist peame mõistma funktsiooni keerukuse toimimist: Vikipeedias on arvutusliku keerukuse osas hea värskendus, kuid laiskadele lisan lühikese selgituse.

Komplekssus mõõdab, kui palju samme meie funktsioon nõuab - mida vähem samme, seda kiirem on täitmine (tuntud ka kui „tööaeg“).

Vaatame järgmist fragmenti:

function fn(n, m) { return n * m}

Arvutuslik keerukus (edaspidi lihtsalt "keerukus") fnon O(1), see tähendab, et see on konstantne (võite lugeda O(1)kui " kulu on üks "): hoolimata sellest, milliseid argumente edastate, peab seda koodi käitav platvorm tegema ainult ühte toimingut (mitmekordselt nviiakse m). Jällegi, kuna see on üks operatsioon, viidatakse maksumusele O(1).

Keerukust mõõdetakse eeldades, et teie funktsiooni argumentidel võivad olla väga suured väärtused. Vaatame seda näidet:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Võib arvata, et selle keerukus on O(3)õige?

Jällegi, kuna keerukust mõõdetakse väga mahukate argumentide kontekstis, kipume konstandid „maha viskama“ ja arvestama O(3)samaga O(1). Nii et isegi sel juhul ütleksime, et selle keerukus fnon O(1). Pole tähtis, mis väärtus nja väärtus mon, lõpuks jõuate alati kolme toiminguni - mis on jällegi pidev kulu (seetõttu O(1)).

Nüüd on see näide veidi erinev:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Nagu näete, loopime nii mitu korda kui väärtus n, mis võib olla miljonites. Sel juhul määratleme selle funktsiooni keerukuse järgmiselt O(n): kuna peate tegema nii palju toiminguid kui ühe oma argumendi väärtus.

Teised näited?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Need näited viivad 2 * nkorda, st keerukus peaks olema O(2n). Kuna mainisime, et funktsiooni keerukuse arvutamisel „ignoreeritakse” konstante, klassifitseeritakse ka see näide O(n).

Üks veel?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Siin me silitame üle nja silmusime uuesti põhisilmu sees, see tähendab, et keerukus on "ruudus" ( n * n): kui non 2, siis jookseme s.push(m)4 korda, kui 3 siis 9 korda jne.

Sel juhul viidatakse funktsiooni keerukusele O(n²).

Viimane näide?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

Sel juhul ei ole meil pesastatud tsükleid, kuid me teeme kaks korda kaks erinevat argumenti: keerukus on määratletud järgmiselt O(n+m). Kristallselge.

Nüüd, kui olete just saanud keerukuse lühitutvustuse (või värskenduse), on väga lihtne mõista, et keerukate funktsioonide funktsioon O(1)toimib palju paremini kui sellega O(n).

Hash-tabelid on O(1)keerukad: võhiku mõistes on need ülikiired . Liigume edasi.

(Ma lamasin räsilaudadel, mis on alati O(1)keerukas, aga loe lihtsalt edasi;))

Ehitame (tumma) räsitabeli

Meie räsitabelis on 2 lihtsat meetodit - set(x, y)ja get(x). Alustame koodi kirjutamist:

Rakendame väga lihtsat ja ebaefektiivset viisi nende võtmeväärtuste paaride salvestamiseks ja hiljem hankimiseks. Kõigepealt alustame nende salvestamisest sisemisse massiivi (pidage meeles, et me ei saa seda kasutada, {}kuna rakendame {}- mõistus puhutud!):

Siis on lihtsalt loendist õige element kätte saada:

Meie täielik näide:

Meie DumbMap on hämmastav! See töötab kohe karbist, kuid kuidas see toimib, kui lisame suure hulga võtme-väärtuse paare?

Proovime lihtsat võrdlusalust. Kõigepealt proovime leida väga väheste elementidega räsitabelist olematu elemendi ja seejärel proovime seda sama suure hulga elementidega:

Tulemused? Mitte nii julgustav:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

Rakendamisel peame kõik sees this.listolevad elemendid läbi otsima, et leida sobivuse võtmega element . Maksumus on O(n)ja see on üsna kohutav.

Tehke see kiiresti (er)

Peame leidma viisi, kuidas vältida oma loendi uurimist : aeg lisada räsi räsitabelisse .

Kas olete kunagi mõelnud, miks nimetatakse seda andmestruktuuri räsitabeliks? Seda seetõttu, et teie seatud ja hangitud klahvidel kasutatakse räsimisfunktsiooni. Selle funktsiooni abil muudame võtme täisarvuks ija salvestame väärtuse isisemise loendi indeksisse . Kuna loendist elementi pääsemisel selle indeksi järgi on püsivad kulud ( O(1)), on räsitabeli maksumus ka O(1).

Proovime seda:

Siin kasutame string-hash moodulit, mis teisendab stringi lihtsalt numbriliseks räsi. Kasutame seda elementide salvestamiseks ja toomiseks hash(key)meie loendi indeksis . Tulemused?

with lots of records in the map: 0.013ms

W - O - W. Sellest ma räägin!

Me ei pea loendis kõiki elemente silmitsema ja elementide hankimine DumbMapon ülikiire!

Las ma panen selle võimalikult sirgjooneliselt: räsimine muudab räsitabelid ülimalt tõhusaks . Maagiat pole. Mitte midagi rohkemat. Nada. Lihtsalt lihtne, nutikas ja leidlik idee.

Õige räsimisfunktsiooni valimise kulud

Muidugi on kiire räsimisfunktsiooni valimine väga oluline. Kui meie töö hash(key)kestab mõne sekundi jooksul, on meie funktsioon selle keerukusest hoolimata üsna aeglane.

Samal ajal on väga oluline veenduda, et meie räsimisfunktsioon ei tekitaks palju kokkupõrkeid , kuna need kahjustaksid meie räsitabeli keerukust.

Segaduses? Vaatame kokkupõrkeid lähemalt.

Kokkupõrked

Võite mõelda: „ Ah, hea räsimisfunktsioon ei tekita kunagi kokkupõrkeid! ”: Noh, tule tagasi reaalsesse maailma ja mõtle uuesti. Google suutis SHA-1 räsialgoritmi jaoks kokku põrgata ja see on vaid aja või arvutusvõime küsimus, enne kui räsimisfunktsioon praguneb ja tagastab sama räsi kahe erineva sisendi jaoks. Eeldage alati, et teie räsimisfunktsioon tekitab kokkupõrkeid, ja rakendage selliste juhtumite vastu õiget kaitset.

Proovime juhul kasutada hash()funktsiooni, mis tekitab palju kokkupõrkeid:

See funktsioon kasutab väärtuste salvestamiseks 10 elemendi massiivi, mis tähendab, et elemendid tõenäoliselt asendatakse - vastik viga meie DumbMap:

Probleemi lahendamiseks saame ühte indeksisse lihtsalt salvestada mitu võtme-väärtuse paari. Nii et muutkem meie räsitabelit:

Nagu võite märgata, pöördume siin tagasi oma algse rakenduse juurde: salvestage loend võtmeväärtuste paaridest ja uurige neid kõiki. See saab olema üsna aeglane, kui loendi konkreetse indeksi jaoks on palju kokkupõrkeid.

Võrdleme seda oma hash()funktsiooni abil, mis genereerib indeksid vahemikus 1 kuni 10:

with lots of records in the map: 11.919ms

ja kasutades hash-funktsiooni from string-hash, mis genereerib juhuslikud indeksid:

with lots of records in the map: 0.014ms

Ohoo! Õige räsimisfunktsiooni valimisega kaasnevad kulud - piisavalt kiiresti, et see ei aeglustaks meie teostamist iseenesest, ja piisavalt hea, et see ei tekitaks palju kokkupõrkeid.

Üldiselt O (1)

Kas mäletate mu sõnu?

Hashtabelitel on O(1)keerukus

Noh, ma valetasin: räsitabeli keerukus sõltub teie valitud räsimisfunktsioonist. Mida rohkem kokkupõrkeid genereerite, seda keerukam on O(n).

Räsimisfunktsioon nagu:

function hash(key) { return 0}

tähendaks, et meie räsitabeli keerukus on O(n).

Seetõttu on arvutuslikul keerukusel kolm mõõdet: parim, keskmine ja halvimal juhul. O(1)Parimal ja keskmisel juhul on räpplaudadel keerukus, kuid O(n)halvimal juhul langevad need alla .

Pidage meeles: hea räsimisfunktsioon on tõhusa räsitabeli võti - ei rohkem ega vähem.

Lisateave kokkupõrgete kohta ...

Tehnikat, mida me DumbMapkokkupõrgete korral parandasime, nimetatakse eraldi aheldamiseks: kõik kokkupõrkeid genereerivad võtmepaarid salvestame loendisse ja silmustame neid läbi.

Teine populaarne tehnika on avatud pöördumine:

  • meie nimekirja igas indeksis salvestame ühe ja ühe ainsa võtmeväärtuste paari
  • kui proovite paari paari indeksisse xsalvestada, proovige meie uus paar salvestada aadressil , kui võtmeväärtuste paar on juba olemasx + 1
  • kui x + 1võetakse, proovige x + 2ja nii edasi ...
  • elemendi hankimisel räsige võti ja vaadake, kas sellel positsioonil ( x) olev element sobib meie võtmega
  • kui ei, proovige pääseda elemendile kohale x + 1
  • loputage ja korrake, kuni jõuate loendi lõppu või kui leiate tühja indeksi - see tähendab, et meie elementi pole räsitabelis

Nutikas, lihtne, elegantne ja tavaliselt väga tõhus!

KKK (või TL; DR)

Kas räsitabelis räsitakse meie salvestatavad väärtused?

Ei, võtmed on räsitud, nii et neist saab muuta täisarv i, ja nii klahvid kui ka väärtused salvestatakse iloendis.

Kas räsitabelite kasutatavad räsimisfunktsioonid tekitavad kokkupõrkeid?

Absoluutselt - nii et vastikute vigade vältimiseks on räsitabelid rakendatud kaitsestrateegiatega.

Kas räsitabelites kasutatakse loendit või lingitud loendit sisemiselt?

Oleneb, mõlemad saavad töötada. Näidetes kasutame JavaScripti massiivi ( []), mida saab dünaamiliselt muuta:

> a = []
> a[3] = 1
> a[ , 1 ]

Miks valisite näidete jaoks JavaScripti? JS massiivid ON räsitabelid!

Näiteks:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Ma tean, neetud JavaScript.

JavaScripti on „universaalne” ja ilmselt kõige hõlpsamini mõistetav keel, kui mõnda näidiskoodi vaadata. JS ei pruugi olla parim keel, kuid loodan, et need näited on piisavalt selged.

Kas teie näide on räsitabeli tõesti hea rakendamine? Kas see on tõesti nii lihtne?

Ei, üldse mitte.

Vaadake Matt Zeunerti "räsitabeli rakendamist JavaScripti", kuna see annab teile veidi rohkem konteksti. Õppida on palju rohkem, nii et soovitaksin teil tutvuda ka järgmisega:

  • Paul Kube räsilaudade kursus
  • Meie enda hash-tabeli juurutamine Java-s eraldi aheldamise abil
  • Algoritmid, 4. väljaanne - tabelid Hash
  • Kiire räsilaua kujundamine

Lõpuks…

Hash-tabelid on väga nutikas idee, mida me regulaarselt kasutame: ükskõik, kas loote Pythonis sõnaraamatu, PHP-s assotsiatiivse massiivi või JavaScripti Mapi. Neil kõigil on samad kontseptsioonid ja nad töötavad suurepäraselt selle nimel, et saaksime elemendi (kõige tõenäolisema) püsiva hinnaga elementi identifikaatori järgi salvestada ja hankida.

Loodetavasti teile see artikkel meeldis ja jagage julgelt oma tagasisidet minuga.

Eriline tänu kuulub Joele, kes aitas mind selle artikli läbi vaadates.

Adios!