Хорошо, я хотел бы поблагодарить вас всех за ваши ответы - очень интересные и полезные. :)
PriorityQueue - определенно правильный термин, который я искал - спасибо за это.
Теперь все дело в реализации.
Вот что я думаю:
Пусть N - размер очереди, а M - среднее количество событий на метку времени (так называемые «параллельные» события) во время обработки (плотность событий не будет равномерно распределена, «далекое будущее» «Будучи гораздо более разреженным, но с течением времени эта область времени становится намного более плотной (на самом деле, я думаю, что максимальная плотность будет где-то в будущем через 4–12 часов)». Я ищу масштабируемое решение, которое хорошо работает для значительно больших M. Цель - действительно обработать эти события M в течение одной секунды, поэтому я хочу потратить как можно меньше времени на их поиск.
- Если перейти к простому подходу tree , как предлагалось несколько раз, у меня будет вставка O (log N), что, я думаю, весьма неплохо. Если я прав, стоимость обработки одной временной отметки будет O (M * log N), что уже не так хорошо.
- Альтернативой может быть наличие дерева со списками событий вместо отдельных событий. должно быть возможным реализовать некоторую операцию getlistForGivenStampAndCreateIfNoneExists, которая была бы немного быстрее, чем дважды спускаться по дереву, если список не существует. Но в любом случае, с ростом М это не должно иметь большого значения. Таким образом, вставка будет O (log N), как и раньше, а обработка будет в O (M + log N), что, я думаю, также хорошо.
- Подход хэш списков событий , я сформулировал. Это также должно иметь O (1) вставку и O (M) стоимость обработки, хотя это не слишком тривиально с хешами. Звучит круто, на самом деле. Или я что-то упустил? Конечно, не так просто заставить хеш работать хорошо, но кроме этого есть ли проблемы? Или проблема с хешем? Википедия заявляет:
"В хеш-таблице с хорошими размерами средняя стоимость (количество инструкций) для каждого поиска не зависит от количества элементов, хранящихся в таблице. Многие конструкции хеш-таблиц также допускают произвольные вставки и удаления пар ключ-значение при постоянной средней (фактически амортизированной) стоимости за операцию. "
Быстрый тест показал, что стандартная реализация для моей платформы, кажется, соответствует этому.
- Подход массив списков событий , предоставленный DVK. Это имеет O (1) вставка. Теперь это хорошо. Но если я правильно понимаю, он имеет O (M + T) стоимость обработки, где T - это размер массива (если хотите, количество временных интервалов), потому что удаление из массивов происходит по линейной цене. Кроме того, это работает только при максимальном смещении времени.
На самом деле я хотел бы обсудить подход с использованием массива. O (M + T) не хорошо. Не за что. Но я вложил немного мозгов, и вот что я придумал:
Первая идея: лень
O (T) может быть раздавлен произвольным фактором, добавив немного лени, но в конце концов он останется O (T). Но насколько это плохо? Давайте T = 2419200, что составляет 28 дней. А потом, один раз в день, я бы его убрал (желательно, пока ожидается низкая нагрузка). Это потеряло бы меньше чем 5% массива. На моей целевой платформе операция копирования занимает 31 мсек на довольно старом 2 ГГц ядре, так что в конце концов это не кажется такой уж плохой идеей.
Вторая идея: куски
Подумав немного, я подумал об этом решении: хэш-интервалы, интервал (т.е. заданный временной интервал), в свою очередь, представляет собой массив списков событий. интервалы имеют одинаковые размеры, предпочтительно что-то простое, например, дни или часы.
Для вставки я ищу правильный интервал через хеш (создать, если ничего не существует), а в интервале - правильный список событий (снова создать, если его нет), а затем просто вставить его, который равен O ( 1).
Для обработки я просто беру текущий интервал и обрабатываю должные события, обрабатывая текущий список ожидаемых событий, а затем уничтожая его. Массив остается постоянной длины, поэтому мы находимся в O (M) (что является лучшим, что вы можете получить для обработки M элементов). Как только текущий интервал полностью обработан (таким образом, если интервал теперь представляет «прошлое»), я просто располагаю его в O (1). Я могу сохранить дополнительную ссылку на текущий интервал, избавляя от необходимости искать его, но, полагаю, это не даст заметного улучшения.
Мне кажется, что вторая оптимизация - действительно лучшее решение, так как она быстрая и несвязанная. Выбор подходящего размера для интервалов позволяет оптимизировать накладные расходы памяти и накладные расходы на поиск хэшей. Я не знаю, стоит ли мне вообще беспокоиться о времени поиска хеша. Для высокого М это не должно иметь большого значения, не так ли? Таким образом, я бы выбрал размер интервала 1, что возвращает меня к подходу № 3.
Я был бы очень признателен за любую информацию по этому поводу.