Progress OpenEdge kolekcijos
OE 12.5 versijoje pristatytos (ir patobulintos 12.7 versijoje) kolekcijos suteikia naują, paprastesnį būdą saugoti duomenis – šios kolekcijos naudoja „generics“, todėl galite saugoti ir gauti objektus tiesiogiai, be poreikio juos perkonvertuoti (cast). Be to, kai kuriais atvejais jos pasiūlo geresnį veikimą nei bet kas kitas, šiuo metu egzistuojantis OpenEdge aplinkoje. Šios kolekcijos įgyvendintos natūviai (angl. natively), todėl išvengiama didelės dalies „interpretatoriaus mokesčio“ (angl. interpreter tax), būdingo tradicinėms ABL klasėms.
- List<T>: paprasta, tvarkinga (angl. ordered) kolekcija, kuri gali turėti pasikartojančius elementus. Naudokite, kai elementų eiliškumas yra svarbus.
- SortedSet<T>: unikalių elementų kolekcija, kuri išlieka surūšiuota. Puikiai tinka unikaliam ID sąrašui palaikyti.
- HashMap<K,V>: raktų-reikšmių (Key-Value) porų kolekcija (Map), paremta maišos funkcija (angl. hash function) ir pirmiausia skirta itin greitai duomenų paieškai. Netvarkinga (angl. unordered) ir nesurūšiuota.
Kas yra HashMap?
HashMap yra esminė duomenų struktūra informatikoje, žinoma savo gebėjimu saugoti ir tvarkyti rakto-reikšmės poras, akcentuojant greitą duomenų gavimą.
Progress OpenEdge programuotojai yra įpratę prie temp-tables ir FIND sakinių. Indeksuotoje lentelėje tai paprastai yra labai greita operacija. Tačiau ji vis tiek apima B-medžio (B-Tree) paiešką (O(log n) laiko sudėtingumas). Didelėje lentelėje su daug operacijų tai gali tapti pastebima. HashMap galėtų būti dar greitesnis – jo teorinis laiko sudėtingumas yra O(1), tai reiškia, kad jis neieško duomenų – jis „žino“, kur jie yra.
Kiekvienas HashMap įrašas turi dvi dalis: raktą ir reikšmę. Tai gali apibrėžti duomenų ryšį, pavyzdžiui, Darbuotojas-Vadovas, kur kiekvienas raktas (Darbuotojas) yra unikalus objektas, naudojamas reikšmei (Vadovui) rasti, kuris pats gali pasikartoti keliuose HashMap įrašuose. Raktas taip pat gali būti tiesiog unikali reikšmės objekto savybė (pvz., Darbuotojo ID), priklausanti reikšmės objektui (Darbuotojui).
Jei HashMap yra netvarkingas ir nesurūšiuotas, kaip jis žino, kur dėti ir iš kur gauti jūsų duomenis? Jis naudoja maišos funkciją (Hash function).
Kai pateikiate Map raktą, jis perleidžia tą raktą per matematinę formulę (ABL kalboje – metodą hashCode()). Ši formulė sugeneruoja skaičių, kurį HashMap tuomet naudoja kaip indeksą konkrečiam atminties segmentui (angl. bucket).
Štai kodėl tai taip greita – nesvarbu, ar turite 10 elementų, ar 1 000 000, maišos funkcijai visada reikia to paties laiko segmento adresui apskaičiuoti. Kiekvienas skirtingas raktas HashMap struktūroje idealiu atveju sugeneruoja skirtingą maišos kodą, tiesiogiai nuvedantį prie jūsų duomenų.
HashMap Progress OpenEdge aplinkoje
Kūrimas ir tipų saugumas
Nuo OpenEdge 12.5 versijos turime „generics“ – tai viena geriausių priežasčių pradėti naudoti naujas kolekcijas, nes jos suteikia tipo patikrinimą kompiliavimo metu. Jums nebereikia perkonvertuoti (cast) kiekvieno objekto, kurį ištraukiate iš kolekcijos ar temp-table. Generinio tipo parametrai gali būti ir sąsajos (interfaces), tačiau saugomi objektai visada turi būti to paties klasės tipo. Atkreipkite dėmesį, kad tiek raktai, tiek reikšmės „Progress“ HashMap struktūroje privalo būti objektai – šio dalyko poveikį paaiškinsiu kiek vėliau.
Rakto objekto paruošimas
Jei nuspręsite sukurti pasirinktinę klasę naudoti kaip raktą (mano pavyzdyje – klasė ManagerKey, turinti vardo, pavardės ir amžiaus savybes), klasė turi įgyvendinti sąsają IHashable ir perrašyti du jos metodus.
HashMap naudoja metodą Equals(), kad patvirtintų, ar du raktai yra tie patys. Tai svarbi maišos lentelių dalis, nes nors maišos funkcija kartais gali grąžinti tą pačią reikšmę skirtingiems raktams, šis metodas visada turi užtikrinti unikalumą. Pagal numatytuosius nustatymus AVM laiko du objektus lygiais tik tuomet, kai jie turi tą patį atminties adresą (t. y. tą patį egzempliorių). Šiame metode turite parašyti pasirinktinę logiką, lyginančią rakto savybes dviejuose objektuose.
Kitas esminis HashMap metodas – hashCode(). Šis metodas grąžina sveikąjį skaičių, nurodantį, kuriame atminties segmente HashMap turėtų ieškoti. Naudokite integruotą hash-code() funkciją unikalioms objekto savybėms, dažnai toms pačioms, kurios naudojamos Equals() metode, kad maišos kodai būtų unikalūs. Kai keli objektai sugeneruoja tą patį maišos kodą, tai vadinama kolizija (angl. collision) – ne būtinai lemtinga HashMap struktūrai, tačiau tuomet ji turi ieškoti per segmentą nuosekliai (linijiniu būdu), o tai lėta.
HashMap operacijos
Be greitos paieškos ir tipo patikrinimo kompiliavimo metu, dar viena priežastis naudoti HashMap (ar kitas kolekcijas) – jų operacijos yra labai paprastos, o kodas paprastai atrodo švaresnis, labiau atitinkantis kitas OOP kalbas, palyginti su tuo pačiu atveju temp-table su dviem objektais.
Skaliarinių duomenų tipų naudojimas kaip raktų
Ne kiekvienas HashMap yra ryšys tarp objektų. Iš tikrųjų, dažniau naudojame sveikuosius skaičius arba simbolių eilutes kaip raktus HashMap struktūrose. Nors to negalime atlikti tiesiogiai Progress OpenEdge aplinkoje, šiai problemai yra keletas paprastų sprendimų.
OpenEdge.Core apvalkalai (wrappers)
„Progress“ iš anksto pateikia standartinių apvalkalo (wrapper) klasių rinkinį. Tai dažniausi būdai „suvynioti“ (angl. box) jūsų primityvius duomenis:
- OpenEdge.Core.String (skirta CHARACTER)
- OpenEdge.Core.Integer (skirta INTEGER)
- OpenEdge.Core.Decimal (skirta DECIMAL)
- OpenEdge.Core.DateHolder (skirta DATE arba DATETIME)
Jei našumas jums labai svarbus, verta pažymėti, kad šios klasės gali būti ne tokios paprastos (angl. lightweight), kaip norėtumėte. Jos turi papildomą apkrovą ir logiką, kurios gali ir nereikėti, o jei saugote 10 000 reikšmių HashMap struktūroje, sukursite 10 000 apvalkalo raktų, todėl ta papildoma apkrova pradės turėti reikšmės.
Paprasti pasirinktiniai apvalkalai
Apdorojant didelį kiekį objektų, rekomenduočiau parašyti savo minimalų apvalkalą skaliariniams rakto tipams, be jokio papildomo OpenEdge.Core bibliotekos klasių balasto. Tai taip pat leidžia apibrėžti pasirinktinį hashCode() įgyvendinimą, kurio gali prireikti norint išvengti maišos kolizijų. Veikimo skirtumai mano testiniais atvejais buvo labai pastebimi – pasirinktiniai apvalkalai buvo nuo 3 iki 10 kartų greitesni kuriant objektus ir naudojo mažiau atminties.
Maišos kolizijos
Testuodamas skirtingas HashMap realizacijas, pastebėjau reikšmingus veikimo kritimus keliose iš jų. Atlikus nedidelę profilerio analizę, pamačiau, kad saugant naujus objektus buvo iškviečiama daug Equals() metodo kreipinių – tai parodė, kad tose konkrečiose HashMap struktūrose buvo daug kolizijų.
Maišos kolizija yra problema, kai du skirtingi raktai sugeneruoja tą patį maišos kodą, ir tai dažnai yra didžiausia HashMap veikimo kliūtis. Tokiu atveju dvi (ar daugiau) skirtingos reikšmės patenka į tą patį atminties segmentą, o tai reiškia, kad ieškant tų reikšmių, HashMap turi pereiti per kelis segmento objektus ir juos palyginti naudodama Equals() metodą.
ABL kalbos hash-code() funkcija grąžina 32 bitų ženklinį sveikąjį skaičių, o tai reiškia, kad yra 2³² (apie 4,3 milijardo) galimų maišos reikšmių. Tai gali skambėti kaip daug, tačiau „Birthday Paradox“ rodo, kad kolizijos įvyks žymiai anksčiau, nei tikimasi. Ir su silpnu hashCode() metodo įgyvendinimu, HashMap palaipsniui degraduoja iš labai greitos O(1) duomenų struktūros į nuoseklių, sekuencinių sąrašų seriją su O(n) paieškos laiku.
Mano pagrindinė įžvalga po testavimo – paprastiems simbolių eilutės raktams, ypač tiems, kurie seka panašiais šablonais (pvz., skaičius eilutės pavidalu), maišos kolizijos yra gana tikėtinos. Vienu itin blogu atveju duomenų įrašų riba buvo apie 10 000 objektų, kol kolizijos pradėjo atsirasti daugumai papildomų raktų. Tai gali rodyti, kad OpenEdge aplinkoje hash-code() funkcija gali būti gana silpna. Tvirtai rekomenduoju naudoti „salt“ arba „combination hashing“ skaičiuojant maišos kodą, kad būtų užtikrintas jo unikalumas. hash-code() funkcija priima iki 10 parametrų, todėl net jei naudojate apvalkalo klasę su vienu duomenų lauku, jos kombinavimas su papildomomis reikšmėmis gali žymiai padidinti HashMap struktūrų veikimą.
HashMap ir temp-table veikimo palyginimas
Jau žinome, kad indeksuotos temp-table paieškos veikimas yra O(log n), o tinkamai sukonfigūruota HashMap gali tai atlikti per O(1). Tačiau greitai supratau, kad šis HashMap greitis yra labiau teorinis nei tai, ką gauname praktikoje.
- Pradinis HashMap užpildymas daugeliu atvejų bus lėtesnis nei temp-tables, nes kiekvienam raktui reikia sukurti objektą, ypač jei raktai yra skaliarinės reikšmės, o objekto kūrimas visada bus brangesnis nei bet koks paieškos laiko prieaugis.
- 32 bitų maišos funkcija labai didelėse struktūrose greičiausiai sukels nemažai kolizijų. Tai pastato HashMap į keblią poziciją, kai paieškos greitis nėra pastebimas, palyginti su temp-table, jei duomenų rinkinys per mažas. Vis dėlto jis taip pat lėtėja, jei struktūra per didelė ir turi maišos kolizijų.
- Jei pradinis HashMap dydis nežinomas, neišvengiamai teks kelis kartus iš naujo perskaičiuoti (rehash) saugomus duomenis. Tai procesas, kai atminties segmentų skaičius didinamas, siekiant išlaikyti O(1) paieškos greitį, ir tai užtrunka laiko.
- HashMap struktūros daro žymiai didesnę apkrovą šiukšlių rinkimo (angl. garbage collection) procesui nei temp-tables, nes procesas dažnai sustoja patikrinti, ar visi HashMap objektai vis dar naudojami. Keli paprasti profiliavimo testai su 1 milijonu objektų parodė, kad šiukšlių rinkimas temp-table saugyklai vidutiniškai užtruko 8,6 s, o HashMap struktūrai – 14,3 s.
Mano nuomone, HashMap pirmiausia turėtų būti naudojamas apibrėžiant ryšį tarp dviejų realių objektų, o sveikojo skaičiaus/simbolių eilutės ir objekto ryšį geriau saugoti temp-table struktūroje. Vis dėlto norėjau patikrinti, ar izoliuotas getValue() metodas HashMap struktūroje veikia geriau nei find sakinys indeksuotoje lentelėje, ir dauguma testų rezultatų buvo nuviliantys – temp-tables pranoko HashMap struktūras. Tačiau veikimas skirsis kiekvienu atveju, priklausomai nuo saugomų duomenų ir nuo to, kaip sukonfigūruotos temp-tables ir HashMap struktūros, todėl į tai verta žiūrėti su tam tikra atsarga.
Ar verta keisti temp-tables į HashMap?
Nors HashMap ir temp-table yra iš esmės skirtingos struktūros, kai tikslas yra saugoti objektus ar žemėlapinti (map) jų ryšius, HashMap tikrai turėtų būti svarstomas kaip alternatyva, kuriant naują kodą. Tačiau mano požiūris toks: jei vienintelis jūsų rūpestis – veikimas, retai verta keisti temp-tables.
Tai specializuotas įrankis „rakto-reikšmės“ problemai spręsti, kuris kai kuriais konkrečiais atvejais gali pasiūlyti geresnį veikimą nei temp-tables, tačiau net atmetus veikimo aspektą, daugelis ABL kodo dalių galėtų tapti skaitomesnės ir lengviau prižiūrimos, įgyvendinus HashMap struktūras.
Naudokite HashMap, jei jums reikia:
- Švaraus, modernaus kodo. Kad jūsų ABL kodas atrodytų ir jaustųsi kaip Java ar C#, gerinant skaitomumą naujiems programuotojams.
- Generinio tipo saugumo. Kad klaidos būtų aptinkamos kompiliavimo, o ne vykdymo metu.
- Objekto-į-objektą žemėlapinimo. Kai jūsų duomenys jau egzistuoja kaip klasių egzemplioriai.
Daugeliu kitų atvejų? Temp-table tebėra karalius.
Sužinokite daugiau apie mūsų Progress OpenEdge paslaugas iš „Baltic Amadeus“.
Dažniausiai užduodami klausimai
Ar HashMap visada greitesnis už temp-table Progress OpenEdge aplinkoje?
Ne. Nors teorinis HashMap laiko sudėtingumas (O(1)) yra geresnis už indeksuotos temp-table (O(log n)), praktikoje objekto kūrimo, maišos kolizijų ir šiukšlių rinkimo apkrova dažnai panaikina šį pranašumą – daugumoje testinių atvejų temp-tables pranoko HashMap struktūras.
Kas yra maišos kolizija (hash collision)?
Tai atvejis, kai du skirtingi raktai sugeneruoja tą patį maišos kodą. Tuomet HashMap turi ieškoti per kelis to paties atminties segmento objektus nuosekliai, o tai sulėtina paiešką iki O(n) laiko sudėtingumo.
Kada verta naudoti HashMap vietoj temp-table?
HashMap verta rinktis, kai reikia švaraus, moderno objektiškai orientuoto kodo, generinio tipo saugumo kompiliavimo metu arba kai duomenys jau egzistuoja kaip klasių objektai ir reikia apibrėžti ryšį tarp dviejų realių objektų.
Kodėl skaliarinius tipus (sveikuosius skaičius, simbolių eilutes) sunkiau naudoti kaip HashMap raktus?
Progress OpenEdge HashMap raktai ir reikšmės privalo būti objektai, todėl skaliarinius tipus reikia „suvynioti“ (box) į apvalkalo (wrapper) klases – arba naudojant OpenEdge.Core bibliotekos klases, arba rašant pasirinktinius, lengvesnius apvalkalus geresniam veikimui.
