Как сохранить последовательность данных с метками времени?

Question

У меня есть приложение, которое должно хранить последовательность данных о напряжении, каждая запись представляет собой что-то вроде пары {время, напряжение}

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

Проблема в том, что мне также нужно иметь функцию, которая ищет метку времени, например, getVoltageOfTimestamp (float2second (922.325))

Мое решение состоит в том, чтобы иметь декукоторый хранит пары, затем каждые 30 секунд я делаю выборку и сохраняю индекс в карте std :: map,

, поэтому внутри getVoltageOfTimestamp (float2second (922.325)) я просто нахожу ближайший интервал_of_30_seconds дляжелаемое время, а затем переместите мой указатель deque в соответствующее_index_of_deque, выполните итерацию оттуда и найдите правильное напряжение.

Я не уверен, существует ли здесь более «решение для компьютерных специалистов», может кто-нибудь дать мнеключ?

Answer 1

Вы можете использовать двоичный поиск на вашем std::deque, потому что временные метки расположены в порядке возрастания.

Если вы хотите оптимизировать скорость, вы также можете использовать std::map<Timestamp, Voltage>. Для нахождения элемента вы можете использовать upper_bound на карте и вернуть элемент до того, который был найден с помощью upper_bound. Этот подход использует больше памяти (потому что std::map<Timestamp, Voltage> имеет некоторые издержки, и он также выделяет каждую запись отдельно).

Answer 2

Вместо того, чтобы использовать отдельную карту, вы можете выполнить бинарный поиск непосредственно в деке, чтобы найти временную метку шкафа. Учитывая требования сложности std :: map, выполнение бинарного поиска будет столь же эффективным, как и поиск по карте (оба являются O (log N)) и не потребует дополнительных затрат.

Answer 3

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

Надеюсь, это поможет.

Answer 4

Вы не возражаете против использования con ++ con ++? Если нет, то deque<tuple<Time, Voltage>> сделает работу.