Џуди низ

У рачунарству и софтверском инжењерингу, Џуди низ је структура података која има високе перформансе, ниску потрошњу меморије и имплементира асоцијативни низ. За разлику од нормалних низова, Џуди низови могу бити оскудни, односно, они могу да имају велике опсеге нераспоређених индекса. Могу се користити за складиштење и гледање вредности преко целог броја или стринга. Кључне предности коришћења Џуди низа је његова проширивост, високе перформансе, меморија, ефикасност и једноставност употребе.

Џуди низови су и брзински и меморијски-ефикасни, без потребе подешавања и конфигурације, те они могу заменити уобичајене структуре података (повезане листе, бинарне, тројне, Б-стабла, хешинг) и боље раде са веома великим скуповима података.

Да би била мала потрошња меморије, Џуди низови користе више од 20 различитих техника компресије за компримовање чворова.

Џуди Низ је измислио Даглас Баскинс (енгл. Douglas Baskins) и назван је по његовој сестри.

Терминологија

Проширивање, популација и густина становништва се најчешће користе када су у питању Џуди низови. Пошто се обично не користи у литератури стабла претраге, важно је да се дефинишу:

1. Простор је опсег могућих кључева, нпр 200, 300, итд
2. Популација је број кључева садржане у простору, на пример, становништво од 5 могу бити кључеви 200, 360, 400, 512 и 720
3. Густина се користи да се опише оскудност просторних кључева: Густина = Популација / Простор

Предности

Алокација меморије

Џуди низови су дизајнирани да буду безгранични низови и самим тим њихова величина није унапред додељена. Они могу динамички да бирају да повећавају или смањују меморију према популацији низа и може да скалира на великом броју елемената. Пошто динамички алоцира меморију како расте, он је само ограничен машинском меморијом. Меморија коју користе Џуди низови је скоро пропорционална броју елемената у низу.

Брзина

Џуди низови су дизајнирани да задржи број процесорских пуњења кеш линија што је могуће ниже, а алгоритам је сложен у покушају да задовољи овај циљ, што је чешће могуће. Због ових кеш оптимизација, Џуди низови су брзи, понекад чак и бржи од хеш табела, посебно за веома велике скупове података. Они троше много мање меморије него хеш табеле. Такође, могуће је урадити наручени секвенцијални пролаз кључева, што није могуће у хеш табелама.