Я предполагаю, что вы хотите искать значения по отметке времени, и что N будет оставаться стабильным во времени (это может измениться, но не повлияет на сложность амортизированного времени).
Сначала (так же, как @MattОтвет Тиммерманс), вы можете использовать очень простую структуру данных для хранения пар (timestamp, value): взять массив pairs размера N и смещение cur_pair.Чтобы добавить новый элемент, в псевдокоде:
pairs[cur_pair] = (timestamp, value)
cur_pair = cur_pair + 1 % N
Это O (1) .
Для поиска заданной отметки времени в O (n) , просто переберите pairs[cur_pair], ..., pairs[N-1], pairs[0], ..., pairs[cur_pair-1], пока вы не превысите отметку времени, которую вы ищете.Результатом является последнее значение, которое вы прочитали перед выходом из цикла.(Вам решать, что вы делаете, когда отметка времени находится до первой сохраненной отметки времени или после последней сохраненной отметки времени).
Как вы уже видели, можно ускорить поиск с помощью двоичного поиска:
# look for timestamp t
s = cur_pair, e = (cur_pair-1) % N
loop:
if (e-s) % N <= 1:
return pairs[s].value
middle = (s+e) // 2 % N # // is integer division
if pairs[middle].timestamp > t:
s = middle
else:
e = middle
Это O (log N) .
Теперь вы можете, при некоторых предположениях, искать в O (1) амортизируется .Прежде чем дать предположения, давайте рассмотрим идею.
Сохраните предыдущий массив pairs, но добавьте новый массив timestamps длины M.Этот массив разрезает время на равные промежутки времени длительностью slice.У вас есть cur_ts для хранения текущего индекса.Добавить сейчас:
new_ts = timestamp // slice
for ts in [cur_ts + 1, ..., new_ts]: # every time slice bewteen cur+1 and new ts...
timestamps[ts % M] = cur_pair # ...gets the value of the index in pair array.
cur_ts = new_ts % M
# and the previous add:
pairs[cur_pair] = (timestamp, value)
cur_pair = cur_pair + 1 % N
Это все еще O (1).Обратите внимание, что сохраняется только первая временная метка во временном интервале.
Теперь ищите отметку времени t (я не пишу крайние случаи):
index = t // slice
s = timestamps[index] # lower bound
e = timestamps[index + 1 % M] # upper bound
# do the full lookup or the binary search here.
Теперь, почему я говорю, что это O (1) амортизированная сложность времени?
- вычислить индекс метки времени в
timestamp (деление по модулю M: O (1) ) - найти индекс пары(доступ к элементу в массиве: O (1) )
- найти правильную метку времени, начиная с преобладающего индекса.
Шаг 3. is O (1) только если вы можете выбрать значение slice, которое достаточно мало, чтобы быть уверенным, что у вас почти никогда не будет двух временных меток в срезе.То, что «почти никогда» означает, является частью известного компромисса пространства-времени.
Обратите внимание, что у вас есть некоторая работа, чтобы справиться с крайними случаями (M должно быть достаточно большим, чтобы хранить N отметки времени,и др.).