вернуть вставленные элементы за указанный интервал

Question

Как можно разработать эффективную для памяти систему, которая принимает элементы, добавленные в нее, и позволяет извлекать элементы с заданным интервалом времени (т. Е. Возвращать элементы, вставленные между временем T1 и временем T2).БД не задействована.Элементы хранятся в памяти.Какова структура данных и связанный алгоритм.

Обновлено: Предполагается чрезвычайно высокая скорость вставки по сравнению с запросом данных.

Answer 1

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

1. элементы не переделаны
2. элементы вставляются в порядке [если элемент i был вставлен после элемента j, то key(i)>key(j)].

По этой причине дерево не рекомендуется, так как оно является "сверхмощным", и вставка в него - O(logn), где вы можете получить вставку O(1).Я предлагаю использовать одно из следующих:

(1) Массив : массив всегда будет заполняться в конце.Когда выделенный массив заполнится, перераспределите массив [двойного размера] и скопируйте в него существующий массив.
Преимущества: хорошо кеширование обычно ожидается в массивах, O(1) вставка с ручным управлением, используемое пространство не более 2*elementSize*#elemetns
Недостатки: high latency : когда массив заполнен, для добавления элемента потребуется O(n), поэтому следует ожидать, что время от времени будет дорогостоящая операция.

(2) Список пропусков Список пропусков также позволяет вам O(logn) искать и O(1) вставлять в конце, но у него нет проблем с задержкой.Тем не менее, он будет страдать больше от кеша, чем массив.Используемое пространство в среднем составляет elementSize*#elements + pointerSize*#elements*2 для пропуска списка.
Преимущества : O(1) вставка, без дорогостоящих операций.
Недостатки : ожидается плохое кэширование.

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

В обоих случаях нахождение нужного интервала:

findInterval(T1,T2):
  start <- data.find(T1)
  end <- data.find(T2)
  for each element in data from T1 to T2:
     yield element

Answer 2

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

Сохранитьуказатель на корневой узел, чтобы вы могли выполнять поиск в O (log (n)) и сохранять указатель на последний вставленный узел N (который обязательно является узлом с самым высоким ключом - его временная метка будет самой высокой).Когда вы вставляете узел, проверьте, сколько дочерних элементов N имеет:

• Если 0, то замените N новым узлом, который вы вставляете, и сделайте N его левым потомком.(На этом этапе вам нужно обновить поле глубины дерева максимум для O (log (n)) узлов.)
• Если 1, то добавить новый узел в качестве его правого потомка.
• Если 2, то все становится интересно.Идите вверх по дереву от N до тех пор, пока не найдете узел, у которого есть только 1 дочерний элемент, или корень.Если вы найдете узел только с одним дочерним элементом (это обязательно левый дочерний элемент), то добавьте новый узел в качестве его нового правого дочернего элемента.Если все узлы вплоть до корня имеют двух дочерних элементов, то текущее дерево заполнено.Добавьте новый узел в качестве нового корневого узла и старый корневой узел в качестве его левого потомка.В противном случае не изменяйте старую древовидную структуру.

---

Приложение: для того, чтобы улучшить поведение кеша и использование памяти, лучшим решением, вероятно, является создание дерева или списка пропусков массивов .Вместо того чтобы каждый узел имел одну временную метку и одно значение, пусть каждый узел имеет массив, скажем, 1024 временных меток и значений.Когда массив заполняется, вы добавляете новый в структуру данных верхнего уровня, но на большинстве шагов вы просто добавляете один элемент в конец «текущего массива».Это не повлияет на поведение big-O в отношении памяти или времени, но уменьшит накладные расходы в 1024 раза, в то время как задержка все еще очень мала.

Answer 3

Вы можете добавить их все в простой массив и отсортировать их.

Выполните бинарный поиск в расположениях T1 и T2 .Все элементы массива между ними - это то, что вы ищете.

Это полезно, если поиск выполняется только после добавления всех элементов.Если нет, вы можете использовать AVL или Красно-черный дерево

Answer 4

Как насчет дерева интервалов отношений (закодировать ваши элементы как интервалы, содержащие только один элемент, например, [a, a])?Хотя уже было сказано, что соотношение ожидаемых операций имеет значение (на самом деле очень много).Но вот мои два цента:

Я полагаю, что элемент X, который вставляется в момент времени t (X), связан с этой отметкой времени, верно?Это означает, что вы не вставляете элемент, который имеет отметку времени недели назад или что-то в этом роде.Если это так, перейдите к простому массиву и выполните интерполяционный поиск или что-то подобное (ваши элементы будут уже отсортированы по атрибуту, к которому относится ваш запрос, т. Е. По времени t (X)).

Answer 5

Либо BTree, либо Binary Search Tree могут быть хорошей структурой данных в памяти для выполнения вышеперечисленного.Просто сохраните отметку времени в каждом узле, и вы сможете выполнить запрос диапазона.