Массив Джуди
 | Тема этой статьи Википедии может не соответствовать общему правилу по известности . ( апрель 2022 г. ) |
В информатике массив Джуди — это структура данных, реализующая тип ассоциативного массива с высокой производительностью и низким использованием памяти. [1] В отличие от большинства других хранилищ «ключ-значение» , массивы Judy не используют хеширование, используют сжатие своих ключей (которые могут быть целыми числами или строками) и могут эффективно представлять разреженные данные; то есть они могут иметь большие диапазоны неназначенных индексов без значительного увеличения использования памяти или времени обработки. Они спроектированы так, чтобы оставаться эффективными даже в структурах с размерами в диапазоне пета-элементов, с масштабированием производительности порядка O(log n ). [2] Грубо говоря, массивы Джуди — это высокооптимизированные 256-арные базисные деревья . [3]
Деревья Джуди обычно работают быстрее, чем деревья AVL , B-деревья , хеш-таблицы и списки пропуска , поскольку они высоко оптимизированы для максимального использования кэша ЦП . Кроме того, они не требуют балансировки дерева и не используют алгоритм хеширования. [4]
История
[ редактировать ]Массив Джуди был изобретен Дугласом Баскинсом и назван в честь его сестры. [5]
Преимущества
[ редактировать ]Распределение памяти
[ редактировать ]Массивы Джуди являются динамическими и могут увеличиваться или уменьшаться по мере добавления или удаления элементов из массива. Память, используемая массивами Джуди, почти пропорциональна количеству элементов в массиве Джуди.
Скорость
[ редактировать ]Массивы Джуди предназначены для минимизации количества дорогостоящих заполнений строк кэша из ОЗУ , поэтому алгоритм содержит много сложной логики, позволяющей как можно чаще избегать промахов кэша. Благодаря оптимизации кэша массивы Джуди работают быстро, особенно для очень больших наборов данных. В наборах данных, которые являются последовательными или почти последовательными, массивы Джуди могут даже превосходить по производительности хеш-таблицы, поскольку, в отличие от хеш-таблиц, внутренняя древовидная структура массивов Джуди поддерживает порядок ключей. [6]
Недостатки
[ редактировать ]Массивы Джуди чрезвычайно сложны. Самые маленькие реализации — это тысячи строк кода. [5] Кроме того, массивы Judy оптимизированы для машин с 64-байтовыми строками кэша, что делает их практически непереносимыми без существенной перезаписи. [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Патент Роберта Гобеля и Дугласа Баскинса
- ^ «Debian — Подробная информация о пакете libjudy-dev в buster» .
- ^ Алан Сильверстайн, « Руководство по эксплуатации Джуди IV », 2002 г.
- ^ «10-минутное описание того, как работают массивы Джуди и почему они такие быстрые» .
- ^ Jump up to: а б "Дом" . Джуди.sourceforge.net .
- ^ Jump up to: а б «Сравнение производительности Джуди с хеш-таблицами» .