Индексирование количества сегментов

Question

Итак, вот моя маленькая проблема.

Допустим, у меня есть список сегментов a ₀ ... a _n , которые соответственно содержат L <=c <sub>0 ... c _n

Порядок сегментов имеет значение.Я не могу пойти и поменять их местами.

Теперь я бы хотел проиндексировать эти ведра так, чтобы:

• Я знал общее количество предметов
• Я могу найти i-й элемент
• Я могу добавлять / удалять элементы из любого сегмента и эффективно обновлять индекс

Кажется, легко, правда?Увидев эти критерии, я сразу подумал о дереве Фенвика.Вот для чего они действительно предназначены.

Однако, когда вы думаете о сценариях использования, появляется несколько других вариантов использования:

• , если количество сегментов падает ниже L,ведро должно исчезнуть (пока не беспокойтесь об элементах)
• если количество ведер достигнет H, то необходимо создать новое ведро, потому что оно заполнено

У меня нетне мог понять, как эффективно редактировать дерево Фенвика: удалить / добавить узел, не перестраивая целое дерево ...

Конечно, мы могли бы установить L = 0, чтобы удаление стало ненужным, однако добавление элементов не можетдействительно следует избегать.

Так вот вопрос:

Знаете ли вы лучшую структуру для этого индекса или как обновить дерево Фенвика?

Основная проблема заключается в том,эффективность, и потому что я планирую реализовать это соображения кэша / памяти, о которых стоит беспокоиться.

Фон :

Я пытаюсь придумать структуру, похожую наB-Trees и ранжированные списки пропусков, но с локализованным индексом.Проблема этих двух структур заключается в том, что индекс хранится вдоль данных, что неэффективно с точки зрения кэширования (т. Е. Вам нужно извлечь несколько страниц из памяти).Реализации базы данных предполагают, что сохранение индекса изолированным от фактических данных является более дружественным к кешу и, следовательно, более эффективным.

Answer 1

Я понял вашу проблему как:

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

Чтобы решить это:

Что вы можете сделать, это сохранить дерево «накопленных значений», где узлы листа (x1, x2, ..., xn) являются размерами сегмента.Значение узла - это сумма значений его непосредственных потомков.Если оставить значение 2, то все будет просто (вы всегда можете заполнить его сегментами нулевого размера в конце), и дерево будет полным деревом.

В соответствии с каждым баком вы будете поддерживать указатель на соответствующийлистовой узел.

Например, скажем, размеры сегмента 2,1,4,8.

Дерево будет выглядеть так:

     15
    /  \
   3    12
  / \  / \
 2  1  4  8

Если вы хотите общее количествопрочитайте значение корневого узла.

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

Например, если вы добавите 4 элемента во второе ведро, это будет (узлы, отмеченные * - это те, которые изменились)

     19*
    /   \
   7*    12
  / \   / \
 2  5*  4  8

Если вы хотите найти i-й элемент, вы идете по вышеприведенному дереву., эффективно делающий бинарный поиск.У вас уже есть левый ребенок и правый ребенок.Если я> значение левого дочернего узла текущего узла, вычтите значение левого дочернего узла и выполните рекурсию в правом дереве.Если i <= значение левого дочернего узла, вы идете налево и снова выполняете рекурсию. </p>

Скажем, вы хотели найти 9-й элемент в вышеприведенном дереве:

Поскольку левый дочерний элемент root равен 7 <9. Вы вычитаете 7 из 9 (чтобы получить 2) и идете направо. </p>

Поскольку 2 <4 (левый потомок 12), вы идете налево. </p>

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

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

Получение общего количества равно O (1).Обновление отдельного сегмента / поиска элемента - O (logn).

Добавление нового сегмента амортизируется O (1).

Использование пространства равно O (n).

Вместо двоичного дерева вы, вероятно, можете сделать то же самое сB-Tree.

Answer 2

Я все еще надеюсь на ответы, однако вот что я могу придумать, следуя совету @Moron.

Очевидно, моя маленькая Fenwick Tree идея не может быть легко адаптирована. Легко добавлять новые корзины в конец дерева фенвиков, но не в середину, так что это своего рода безнадежное дело.

У нас осталось 2 структуры данных: Binary Indexed Trees (по иронии судьбы, само имя Фенвик использовал для описания своей структуры) и Ranked Skip List.

Как правило, это не отделяет данные от индекса, однако мы можем получить это поведение следующим образом:

1. Использовать косвенность: элемент, содержащийся в узле, является указателем на корзину, а не на сам контейнер
2. Используйте выделение пула, чтобы элементы индекса, даже если они размещались независимо друг от друга, все еще находились в памяти, что должно помочь кешу

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

Эти структуры позволили бы получить элемент ih в O(log N), я не знаю, возможно ли получить более быструю асимптотическую производительность.

Еще одна интересная деталь реализации: У меня есть указатель на этот элемент, но другие, возможно, были вставлены / удалены, как мне узнать ранг моего элемента сейчас?

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