Judy Array - Judy array
Inden for datalogi er en Judy -array en datastruktur, der implementerer en type associativ array med høj ydeevne og lavt hukommelsesforbrug. I modsætning til de fleste andre nøgleværdibutikker bruger Judy-arrays ingen hash, udnytter komprimering på deres nøgler (som kan være heltal eller strenge) og kan effektivt repræsentere sparsomme data; det vil sige, at de kan have et stort udvalg af ikke -tildelte indekser uden at øge hukommelsesforbruget eller behandlingstiden kraftigt. De er designet til at forblive effektive, selv på strukturer med størrelser i peta-element-området, med ydelsesskalering i størrelsesordenen O (log n ). Groft sagt er Judy-arrays stærkt optimerede 256-radige radix-træer .
Judy-træer er normalt hurtigere end AVL-træer , B-træer , hashtabeller og springlister, fordi de er meget optimerede til at maksimere brugen af CPU-cachen . Derudover kræver de ingen træbalancering, og der bruges ingen hash -algoritme.
Judy -arrayet blev opfundet af Douglas Baskins og opkaldt efter hans søster.
Fordele
Hukommelsestildeling
Judy -arrays er dynamiske og kan vokse eller krympe, når elementer tilføjes til eller fjernes fra arrayet. Hukommelsen, der bruges af Judy -arrays, er næsten proportional med antallet af elementer i Judy -arrayet.
Fart
Judy-arrays er designet til at minimere antallet af dyre cache-line- fyld fra RAM , og derfor indeholder algoritmen meget kompleks logik for at undgå cache-misser så ofte som muligt. På grund af disse cache -optimeringer er Judy -arrays hurtige, især for meget store datasæt. På datasæt, der er sekventielle eller næsten sekventielle, kan Judy -arrays endda overgå hashtabeller, da den interne træstruktur i Judy -arrays i modsætning til hash -tabeller opretholder rækkefølgen af nøglerne.
Ulemper
Judy -arrays er ekstremt komplicerede. De mindste implementeringer er tusinder af linjer med kode. Derudover er Judy -arrays optimeret til maskiner med 64 byte -cachelinjer, hvilket gør dem i det væsentlige ikke -bærbare uden en væsentlig omskrivning. I de fleste applikationer er den mulige ydelsesfordel for lille til at retfærdiggøre datakonstruktionens høje kompleksitet.
