Поиск наиболее эффективной структуры данных для создания индексного файла
У меня есть видео файл, который состоит из множества последовательных кадров двоичных данных. Каждый кадр также имеет уникальную метку времени (которая не является его порядковым номером в файле, а скорее значением, предоставленным камерой во время записи). С другой стороны, у меня есть функция API, которая извлекает этот кадр на основе порядкового номера этого кадра. Чтобы сделать все немного сложнее — у меня есть игрок, которому предоставлена метка времени, и я должен получить двоичные данные для этого кадра.
Еще одна печальная вещь: метки времени НЕ являются последовательными. Они могут быть последовательными, но это не гарантируется, так как может иметь место обертка вокруг максимального размера без знака.
Таким образом, последовательность временных меток может быть
54567, 54568, …, 65535, 65536, … или
54567, 54568, …, 65535, 0, 1, …
Так что это может выглядеть следующим образом:
Frame 0
timestamp 54567
binary data
........
Frame 1
timestamp 54569
binary data
........
Frame 2
timestamp 54579
binary data
.
.
.
Frame n
timestamp m
binary data
0 <= n <= 65536 (MAX_UNSIGNED_SHORT)
0 <= m <= MAX_UNSIGNED_INT
API проигрывателя клипов должен иметь возможность получать двоичный кадр по отметке времени. Однако внутри я могу получить кадр только по порядковому номеру кадра. Так что, если меня попросят отметку времени mМне нужно перебрать n кадры, чтобы найти кадр с отметкой времени m,
Чтобы оптимизировать его, я решил создать индексный файл, который дал бы мне соответствие между отметкой времени и порядковым номером кадра. И вот мой вопрос:
В настоящее время мой индексный файл состоит из двоичных пар размером 2*sizeof(unsigned int), который содержит метку времени и порядковый номер кадра. Плеер позже создает из этого файла stl map с key==timestamp, value==frame sequential number,
Есть ли способ сделать это более эффективно? Должен ли я создать свой индексный файл как дамп какой-то структуры данных, чтобы впоследствии он мог быть загружен в память проигрывателем клипов при открытии клипа, чтобы у меня был O (1) доступ к кадрам? У вас есть другие предложения?
UPD:
Я обновил имена и требования (временные метки не обязательно являются последовательными, а количество кадров ограничено значением MAX_UNSIGNED_SHORT). Также хотел бы поблагодарить всех, кто уже нашел время и дал ответ. Поиск интерполяции — интересная идея, хотя я никогда не пробовал ее сам. Я думаю, что вопрос будет дельта между O(1) а также O(log log N) во время выполнения.
Решение
Казалось бы, мы должны быть в состоянии сделать следующие предположения:
а) сам видеофайл не будет изменен после его создания
б) игрок может захотеть найти последовательные кадры, т.е. когда он делает нормальное воспроизведение
c) игрок может захотеть найти случайные кадры, то есть когда он делает FF, REW или пропускает или к главе
Учитывая это, почему бы просто не сделать HashMap, связывающий идентификатор кадра и индекс кадра? Вы можете создать его один раз, игрок может прочитать его, а затем может выполнить простой и ограниченный по времени поиск запрашиваемого кадра.
Другие решения
Есть ряд компромиссов, чтобы сделать здесь.
Ваш индексный файл уже является дампом структуры данных: массива. Если вы не планируете часто вставлять или удалять кадры и сохраняете этот массив в отсортированном порядке, легко выполнить бинарный поиск (используя std::binary_search) на массиве. Для вставки и удаления требуется O (N), но поиск по-прежнему O (log N). Массив будет занимать меньше места в памяти и будет быстрее читать и записывать из вашего индексного файла.
Если вы делаете много вставки и удаления рамок, то std::map структура даст вам лучшую производительность. Если количество кадров велико или вы хотите хранить с ними больше метаданных, вы можете посмотреть на B-древовидная структура, или просто использовать встроенную базу данных, как Sqlite или же BerkeleyDB. Оба они реализуют индексацию B-дерева и являются хорошо проверенными частями кода.
Просто сохраните данные кадра в массиве, где индексы представляют номера кадров. Затем создайте хэш-карту от индексов камеры до номеров кадров. Вы можете получить кадр, принадлежащий либо номеру кадра, либо индексу камеры в O (1), едва используя больше памяти, чем ваш текущий подход.
Кроме того, вы можете поддерживать массив, индексированный по номеру кадра, в котором хранится пара (индекс камеры, данные) и выполнять двоичный поиск O (log n), когда вам нужен доступ к нему по индексу камеры. Это использует тот факт, что индексы камеры отсортированы.
В стандартной библиотеке C ++ карты хеша доступны как std::unordered_map (если ваш компилятор / STL поддерживает их, что может быть не так, поскольку они только недавно были добавлены в стандарт C ++), хотя основано на дереве std::map (с поиском O (log n)), вероятно, достаточно для этой цели.
Бинарный поиск доступен как std::binary_search,