Предложения по структуре данных

Question

Я изо всех сил пытался найти подходящую структуру данных, которая удовлетворяет этим требованиям:

1. Элементы этой структуры данных организованы в блоки. Порядок этих блоков несколько не имеет значения, но элементы в блоке поддерживают определенный порядок.
2. Количество вставок не частое.
3. Поиски гораздо чаще.
4. Получение индекса элемента в структуре данных имеет решающее значение.
5. После поиска элемента структуры данных следующий или предыдущий (соседний) элемент в структуре данных должен быть легко доступен.

Имея это в виду, у меня есть следующие соображения:

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

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

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

Что ты думаешь? Любое предложение будет более чем оценено.

Большое спасибо

Answer 1

Массив, вероятно, будет лучшей структурой данных в этом случае.

Вставка в массив включает в себя поиск правильного слота для нового элемента, а затем смещение всего большего на один элемент вправо, используя memmove. Это может быть дорогостоящим, если вставки происходят часто, но если они не часты, как вы говорите, тогда это не должно быть проблемой. Затем у вас есть O(1) поиск по индексу и O(log n) поиск.

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

Таким образом, у вас есть массив, содержащий данные, к которым добавляются только данные, и массив указателей, которые пересчитываются (то есть находят правильную точку и сдвиг) при каждой вставке.

Answer 2

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

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

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

Answer 3

А как насчет дерева поиска? Это хорошо подходит для всех ваших требований, кроме 4.

Чтобы справиться с этим требованием, вы можете поддерживать дополнительный счетчик для каждого узла. Этот счетчик будет записывать количество узлов в поддереве ниже узла.

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