Джуди массиві: Жоғары өнімділік және жадты үнемдеуші ассоциативтік массив құрылымы
Judy array
Жуди массиві – аса жоғары өнімділік пен жадты үнемді пайдаланатын ассоциативтік массив құрылымы. Хештелмейтін, сығылған кілттері бар, үлкен деректерге арналған.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Ассоциативтік массивтің түрі
Type of associative array
Компьютерлік ғылымда Джуди массиві – жоғары өнімділікке және жадты аз пайдалануға ие ассоциативтік массивтің түрін іске асыратын дерек құрылымы. Көптеген басқа кілт-мәнді сақтау орындарынан өзгеше, Джуди массиві хештеуді қолданбайды, кілттерін (бүтін сан немесе жол болуы мүмкін) қысып пайдаланады және сирек деректерді тиімді ұсынуға мүмкіндік береді; яғни, жадты пайдалануды немесе өңдеу уақытын күрт арттырмай, үлкен көлемде тағайындалмаған индекстерге ие болуы мүмкін. Олар пета элементтерінің диапазонындағы өлшемдерде де тиімді жұмыс істеу үшін жасалған, өнімділік O(log n) ретінде өседі. Шамамен айтқанда, Джуди массиві – 256-дық радикс ағаштарының жоғары сапалы оңтайландырылған түрі. Джуди ағаштары әдетте AVL ағаштарынан, B ағаштарынан, хеш-кестелерден және секіріп өтетін тізімдерден жылдам, себебі олар процессордың кэшін тиімді пайдалану үшін жоғары деңгейде оңтайландырылған. Бұған қоса, оларға ағаш теңгерімі қажет емес және хештеу алгоритмі қолданылмайды.
In computer science, a Judy array is a data structure implementing a type of associative array with high performance and low memory usage. Unlike most other key value stores, Judy arrays use no hashing, leverage compression on their keys (which may be integers or strings), and can efficiently represent sparse data; that is, they may have large ranges of unassigned indices without greatly increasing memory usage or processing time. They are designed to remain efficient even on structures with sizes in the peta element range, with performance scaling on the order of O(log n). Roughly speaking, Judy arrays are highly optimized 256 ary radix trees. Judy trees are usually faster than AVL trees, B trees, hash tables and skip lists because they are highly optimized to maximize usage of the CPU cache. In addition, they require no tree balancing and no hashing algorithm is used.
Тарих
Джуди массивін Дуглас Баскинс ойлап тапты және оны әпкесінің құрметіне атады.
The Judy array was invented by Douglas Baskins and named after his sister.
Жадыны бөлу
Джуди массиві динамикалық және элементтер қосылғанда немесе алынып тасталғанда кеңейе немесе тарылуы мүмкін. Джуди массиві пайдаланатын жад, массивідегі элементтер санына пропорционал болады.
Judy arrays are dynamic and can grow or shrink as elements are added to, or removed from, the array. The memory used by Judy arrays is nearly proportional to the number of elements in the Judy array.
Жылдамдық
Джуди массиві RAM-нан қымбат кэш жолдарының толтырылуын азайту үшін жасалған, сондықтан алгоритмде кэштен қателерді мүмкіндігінше болдырмауға бағытталған күрделі логика бар. Осы кэштік оптимизациялардың арқасында Джуди массиві жылдам, әсіресе өте үлкен деректер жиынтықтары үшін. Ретті немесе дерлік ретті деректер жиынтықтарында Джуди массиві тіпті хэш-кестелерден де озып кетеді, себебі хэш-кестелерден өзгеше, Джуди массивінің ішкі ағаш құрылымы кілттердің ретін сақтайды.
Judy arrays are designed to minimize the number of expensive cache line fills from RAM, and so the algorithm contains much complex logic to avoid cache misses as often as possible. Due to these cache optimizations, Judy arrays are fast, especially for very large datasets. On data sets that are sequential or nearly sequential, Judy arrays can even outperform hash tables, since, unlike hash tables, the internal tree structure of Judy arrays maintains the ordering of the keys.
Кемшіліктері
Джуди массиві өте күрделі. Ең кішкентай реализациялары мыңдаған код жолдарынан тұрады. Сонымен қатар, Джуди массиві 64 байттық кэш желілері бар машиналар үшін оңтайландырылған, оларды маңызды өзгерістерсіз басқа платформаға көшіру мүмкін емес.
Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code. In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.