Лучшая структура данных для следующих ограничений?

Question

Вот некоторые ограничения для структуры данных, которая мне нужна. Кажется, что ни одна из общих структур данных (я упомяну те, о которых я думал ниже) не подходит всем этим. Кто-нибудь может предложить тот, о котором я, возможно, даже не подумал?

1. Мне нужно иметь возможность выполнять поиск по целочисленным клавишам без знака.
2. Элементы, которые должны быть сохранены, являются определяемыми пользователем структурами.
3. Эти индексы будут редкими, обычно чрезвычайно Регулярные массивы отсутствуют.
4. Частота каждого индекса будет иметь неравномерное распределение, причем маленькие индексы встречаются гораздо чаще, чем большие.
5. N обычно будет маленьким, вероятно, не больше 5 или 10, но я не хочу слишком сильно на это полагаться, потому что иногда он может быть намного больше.
6. Постоянный термин имеет большое значение. Мне нужны действительно быстрые поиски, когда N мало. Я уже пробовал общие хеш-таблицы, и, эмпирически, они слишком медленные, , даже когда N = 1, что означает отсутствие коллизий , вероятно, из-за количества косвенного обращения. Тем не менее, я буду открыт для предложений о специализированных хеш-таблицах, которые используют другие упомянутые ограничения.
7. Время вставки не важно, поскольку время поиска быстро. Даже O (N) время вставки достаточно хорошее.
8. Эффективность пространства не очень важна, хотя и достаточно важна, чтобы не использовать обычные массивы.

Answer 1

Когда N мало, простой массив или один связанный список с ключом + значением в качестве полезной нагрузки эффективен очень . Даже если он не самый лучший, когда N становится больше.

Вы получаете O (N) время поиска, что означает, что поиск занимает k * N время. Поиск O (1) занимает постоянное K время. Таким образом, вы получите лучшую производительность с O (N) для N < K/k. Здесь k очень мало, поэтому вы можете получить интересные значения N. Помните, что нотация Big O описывает только поведение для large N s, а не то, что вы ищете. Для небольших столов

void *lookup(int key_to_lookup)
{
  int n = 0;
  while (table_key[n] != key_to_lookup)
    n++;
  return table_data[n];
}

может быть трудно победить.

Оцените ваши хеш-таблицы, сбалансированное дерево и простой массив / связанный список и посмотрите, при каких значениях N они начинают лучше. Тогда ты узнаешь, что лучше для тебя.

Я почти забыл: держите часто используемые ключи в начале вашего массива. Учитывая ваше описание, это означает, что держать его отсортированным.

Answer 2

Этот совет предполагает современный процессор с:

• быстрые кэши
• намного меньшая латентность памяти по сравнению с тактовой частотой.
• разумный прогноз ветвления (действительно потрясающий в последних процессорах для настольных ПК / серверов)

Я бы предположил, что гибридные структуры вполне могут превзойти одну структуру.

Использование простых пар ключей на основе массива с доступом O (N), как уже упоминалось, но с очень низкими постоянными коэффициентами и чрезвычайно хорошим поведением кэширования. Эта исходная структура должна быть небольшой (вероятно, не больше 16 и, возможно, 8 значений), чтобы избежать выхода за пределы одной строки кэша. К сожалению, это параметр, который вам нужно настроить самостоятельно.

Как только вы выйдете за пределы этого числа, вы захотите вернуться к структуре с лучшим поведением O (N), я бы предложил начать с приличной хеш-таблицы, так как это, вероятно, будет разумно в диапазоне от 16 до нескольких тысяч и если вы склонны искать похожие значения чаще, они будут оставаться в более быстрых кешах.

Если вы также удалите , а также вставку, вы должны позаботиться о том, чтобы не перебегать назад и вперед между двумя состояниями. Требование уменьшить счет до половины отсечения для «обновления» до вторичной структуры должно предотвратить это, но помните, что любое детерминированное поведение перехода будет восприимчиво к входным данным в худшем случае.
Это может быть проблемой, если вы пытаетесь защитить себя от вредоносных входных данных. Если это так, использование случайного фактора в решении защищает от него. Вполне вероятно, что вас это не волнует, поскольку вы не упомянули об этом.

Если вы хотите, вы можете попытаться отсортировать исходный первичный массив, допуская двоичный поиск, который равен O (log (N)), но за счет более сложного поискового кода. Я бы подумал, что простой обход массива на самом деле превзойдет его, но вы захотите сравнить его с различными значениями N, это может позволить вам дольше придерживаться первичного массива, но я думаю, что это функция размера размера строки кэша больше, чем поведение O (N).

Другие опции включают в себя:

• Различная обработка всех значений ключа <256 и сохранение их в байтах <code>-> Структура пары массивов, экономящая место на ключах (и потенциально позволяющая им оставаться там при переключении на вторичную структуру), это может работать плохо из-за нужно распаковать массив на лету на родную длину слова.
• используя структуру типа trie, делающую байт во время ключа. Я сомневаюсь, что сложность этого сделает его эффективным на практике

Еще раз повторю очень хороший совет от kmkaplan. Тестируйте это полностью, избегая микробенчмарков. В таком анализе реальные числа могут удивительно отличаться от теории ...

Answer 3

Поиск в хеш-таблице выполняется настолько быстро, насколько это возможно:

Единственное, что отличает его от обычного поиска в массиве, - это вычисление хеша и (если ваша хеш-функция достаточно хороша или вы тратите достаточно времени на генерацию оптимальной хеш-функции во время вставки, которая заставит вашу вставку занять O (N)) тогда, по сути, поиск массива.

По сути, поскольку может случиться (если вы не используете оптимальную хеш-функцию), что вам придется перефразировать или следовать очень маленькому связанному списку.

Поскольку большинство хеш-функций, используемых для хеш-таблиц, имеют k * c_1% c_2, разница с поиском в массиве в довольно разреженной и / или оптимальной хеш-таблице состоит из одного косвенного преобразования, двух умножений, вычитания и деления ( эффективная реализация по модулю с использованием возможностей процессора может уменьшить это путем вычитания и умножения) и поиска в массиве.

Это просто не становится быстрее, чем это.

Answer 4

Вы могли бы рассмотреть Джуди Массив :

Джуди - это библиотека C, которая обеспечивает современная базовая технология, которая реализует разреженный динамический массив. Массивы Джуди объявляются просто с нулевой указатель. Массив Джуди потребляет память только тогда, когда она заполнена, но может расти, чтобы воспользоваться всеми доступная память при желании ... Джуди может заменить много общих данных структуры, такие как массивы, разреженные массивы, хеш-таблицы, B-деревья, двоичные файлы деревья, линейные списки, скиплисты, другое алгоритмы сортировки и поиска, и счетные функции.

Answer 5

Единственное объяснение описанной проблемы, которое я вижу, состоит в том, что хеш-функция слишком сложна. Я был бы склонен к двухэтапному подходу:

1) Для маленьких клавиш - простой массив указателей. Без хэша или чего-либо еще.

2) Для ключей, размер которых превышает размер таблицы, которую вы выделяете:

Как насчет очень простой хеш-функции, которая будет распределять кластерные ключи:

5 битов левого порядка (я предполагаю, что 32-битные целые числа. Если он 64-битный, то добавьте еще один бит.) - это количество битов, которые на самом деле содержат данные, а остальные - просто сумма (сброс несет ) оригинального ключа, разрезанного на куски, сколько битов вы используете для этой цели и которые сложены вместе.

Обратите внимание, что число значащих битов может быть частично предварительно рассчитано - создайте таблицу старших битов в 64 КБ. Если старшее слово не равно нулю, используйте его в качестве индекса таблицы и добавьте 16, в противном случае используйте младшее слово в качестве индекса. Для 64-разрядных целых чисел вам, очевидно, придется использовать 4 шага вместо двух.

Answer 6

Вы можете попытаться объединить лучшее из обоих миров: если ключ маленький, поместите его в массив данных в виде массива, размер которого не превышает предварительно заданный максимальный ключ. Если ключ большой, поместите его в хеш-таблицу.

Answer 7

Я бы рекомендовал Пропустить список здесь. Пакет java.util.concurrent имеет хорошую реализацию, если вы в этом заинтересованы.

Answer 8

Вот общая идея для функции хеширования. Вы сказали, что вставки могут быть дорогостоящими.

Хешируйте ключ, который является целым числом, с простым модулем, хранящимся с каждым экземпляром хеш-таблицы

если вставка вызовет коллизию, повторно оптимизируйте вашу хеш-таблицу, рассчитав количество коллизий, которые могут возникнуть для каждого модуля в разумном диапазоне, скажем, количество элементов в вашей карте через некоторое постоянное число, кратное этому .

очевидно, ваши вставки на самом деле становятся довольно дорогими, примерно O (n ^ 2), если вы минимизируете выделения, но вы, вероятно, сможете добиться поиска с одним целочисленным делением и одной косвенной указкой, и вы знаете, потому что вы вычислил это во время вставки, какой будет наихудший поиск.

Answer 9

Вы можете попробовать хэш с открытым адресом с квадратичным зондированием вместо отдельного сцепления, если ваше N обычно мало. Вам нужно будет перераспределить, скажем, начальный размер от 32 до большей ширины, если вы получите редкий N-случай, который переполняет его. Линейное зондирование или хеширование кукушки даст вам хорошую производительность, если вы сможете заставить всю структуру поместиться в несколько строк кэша.

Честно говоря, я удивлен, что даже стандартная хеш-таблица дает вам такую ​​жалкую производительность. Может быть, вы могли бы войти в него, чтобы увидеть, что делает его таким медленным - если это сама хеш-функция, используйте простую, такую ​​как модуль степени двойки (например, ключ & (N-1), где N известен как быть 2 ^ x), что будет благоприятствовать распределениям с центром в любом случае около 0. Если это погрешность dcache в погоне за отдельной цепочкой, напишите реализацию, в которой первые четыре элемента хранятся в каждой корзине в самой корзине, чтобы вы как минимум быстро их получили. Насколько медленно N = 1?

Я бы хранил указатели на структуры, а не на сами структуры в цепочках ведра: если структуры большие, то при обходе их цепочки будет много промахов кэша. С другой стороны, вы можете разместить около 16 пар «ключ / указатель» в одной строке кэша и платить за промах только тогда, когда найдете правильный элемент.

Answer 10

Я бы рассмотрел хеш-таблицу, которая обрабатывает хеш-коллизии с самобалансирующимся двоичным деревом, а не с простой цепочкой. Вы должны быть в состоянии получить O (1) амортизированный поиск по всем ключам и поиск в худшем случае O (logN). Поскольку распределение ключей искажено, вполне вероятно, что у вас будут коллизии с низкими значениями индекса, и поиск по дереву действительно окупится.