В информатике , А массив Judy является структура данных , реализует тип ассоциативного массива с высокой производительностью и низким уровнем использования памяти. [1] В отличие от большинства других хранилищ ключей и значений , массивы Judy не используют хеширование, усиливают сжатие своих ключей (которые могут быть целыми числами или строками) и могут эффективно представлять разреженные данные, то есть они могут иметь большие диапазоны неназначенных индексов без значительно увеличивая использование памяти или время обработки. Они разработаны, чтобы оставаться эффективными даже в структурах с размерами в диапазоне петаэлементов, с масштабированием производительности порядка O (log n ). [2]Грубо говоря, массивы Джуди - это высокооптимизированные 256-арные деревья счисления . [3]
Деревья Джуди обычно быстрее, чем деревья AVL , B-деревья , хеш-таблицы и списки пропусков, потому что они оптимизированы для максимального использования кеша ЦП . Кроме того, они не требуют балансировки дерева и алгоритма хеширования. [4]
Массив Джуди был изобретен Дугласом Баскинсом и назван в честь его сестры. [5]
Преимущества [ править ]
Распределение памяти [ править ]
Массивы Judy являются динамическими и могут увеличиваться или уменьшаться по мере добавления элементов в массив или удаления из него. Память, используемая массивами Judy, почти пропорциональна количеству элементов в массиве Judy.
Скорость [ править ]
Массивы Judy спроектированы таким образом, чтобы минимизировать количество дорогостоящих заполнений строк кэша из ОЗУ , поэтому алгоритм содержит много сложной логики, чтобы как можно чаще избегать пропусков кеша. Благодаря этой оптимизации кеша массивы Judy работают быстро, особенно для очень больших наборов данных. На наборах данных, которые являются последовательными или почти последовательными, массивы Judy могут даже превзойти хеш-таблицы, поскольку, в отличие от хеш-таблиц, внутренняя древовидная структура массивов Judy поддерживает порядок ключей. [6]
Недостатки [ править ]
Массивы Джуди чрезвычайно сложны. Самые маленькие реализации - это тысячи строк кода. [5] Кроме того, массивы Judy оптимизированы для машин с 64-байтовыми строками кэша, что делает их практически непереносимыми без значительного переписывания. [6] В большинстве приложений возможное преимущество в производительности слишком мало, чтобы оправдать высокую сложность реализации структуры данных.
См. Также [ править ]
Ссылки [ править ]
- ^ Роберт Gobeille и патент Дугласа Baskins'
- ^ http://packages.debian.org/buster/libjudy-dev
- ^ Алан Сильверстайн, " Judy IV Shop Manual ", 2002
- ^ http://judy.sourceforge.net/doc/10minutes.htm
- ^ а б http://judy.sourceforge.net/
- ^ а б http://www.nothings.org/computer/judy/
Внешние ссылки [ править ]
- Главный сайт массивов Джуди
- Как работают массивы Джуди и почему они такие быстрые
- Полное техническое описание массивов Judy
- Независимое сравнение производительности Judy с хэш-таблицами
- Компактная реализация массивов Judy в 1250 строках кода C
