Как эффективно хранить данные временных рядов
У меня есть последовательность обновлений с метками времени, которые монотонно увеличиваются
<t1,d1> , <t2,d2> , <t3, d3> .... <tn, dn>
Мне нужно хранить эти данные. Я заранее знаю максимальную дельту времени, которая меня волнует.
Так, скажем, дельта времени, о которой я забочусь, — это Т. Так что мне нужно хранить только самые последние обновления, которые не более чем на T единиц старше, чем tn.
Я хотел бы хранить их в том порядке, в котором они мне даны.
Подводя итог, я хочу сохранить отсортированную последовательность, в которой я могу эффективно удалить более ранние элементы. Что-то вроде C ++ dequeue.
Любые предложения о том, как эффективно найти элемент отсечки, после которого я могу удалить все старые записи?
Решение
То, что вы описываете, — это очередь, которая по прибытии нового элемента может удалить несколько самых старых. Я также собираюсь предположить, что вам нужен произвольный доступ ко всем элементам.
Таким образом, вам нужна очередь «первым пришел — первым обслужена», и после каждой операции добавления удаляйте самый старый элемент, пока самый старый не станет достаточно новым.
А как получить очередь FIFO с произвольным доступом? Есть std::deque в STL, который делает именно это.
По моему опыту std::deque удивительно неэффективно, хотя, вероятно, из-за плохого поведения кэширования. Это не имеет значения для большинства проектов, но этот вопрос был конкретно об эффективности.
Так что если вы действительно заботитесь об эффективности, вы можете использовать std::vector + итератор к логическому началу. Поэтому в любое время, когда вы хотите удалить самый старый элемент, вы просто увеличиваете итератор. Уловка в том, что таким образом вы никогда не удалите элементы. Эту проблему можно решить, проверив, превышает ли количество логически удаленных элементов в векторе половину его размера, а затем перестроив вектор только из необходимых. Если есть верхняя граница для количества элементов в вашей очереди, вы можете оптимизировать ее, используя массив статических размеров вместо вектора.
Другие решения
Я бы использовал круговой буфер. Когда вы собираетесь добавить новую точку данных, убедитесь, что значение, которое вы собираетесь перезаписать, является старым для удаления. Если это так, иди и переписать. В противном случае перераспределите буфер, скажем, в два раза больше, и скопируйте указатель данных в новый буфер.
Перераспределение и копирование может занять немного времени, но общее влияние будет ограничено тем фактом, что алгоритм в основном амортизируется постоянным временем.
Если вам действительно нужно, вы можете распространить копирование, только скопировав фиксированное количество элементов из старого буфера в новый. Вы должны переместить это количество элементов с каждым новым назначением данных. Пока число равно как минимум 2, вы будете копировать все старые данные, прежде чем новый буфер будет заполнен входящими данными.
C ++ dequeue является <deque>. Вы также можете использовать <list>, но обычно это только полезно, если вы можете выполнять итерацию и удаление из середины коллекции; если вы просто добавляете и выталкиваете с концов, deque гораздо эффективнее как по памяти, так и по скорости.
Я думаю, что вы можете использовать multimap из tupleдля этого.