У меня нет официального обучения CS, поэтому терпите меня.
Мне нужно сделать симуляцию, которая может абстрагироваться от следующего (опуская детали):
У нас есть список действительных чисел, представляющих время событий. В
каждый шаг мы
- удалить первое событие и
- в результате "обработки" несколько других событий могут быть вставлены в список в более позднее время
и повторите это много раз.
Вопросы
Какую структуру данных / алгоритм я могу использовать для максимально эффективной реализации этого? Мне нужно значительно увеличить количество событий / номеров в списке. Приоритет - сделать это как можно быстрее для длинного списка.
Так как я делаю это в C ++, какие структуры данных уже доступны в STL или бусте, которые облегчат реализацию этого?
Подробнее:
Количество событий в списке является переменным, но оно гарантированно будет между n и 2*n, где n - некоторый параметр моделирования. В то время как время событий увеличивается, разница во времени самых последних и самых ранних событий также гарантированно будет меньше постоянной T. Наконец, я подозреваю, что плотность событий во времени, хотя и не является постоянной, также имеет верхнюю и нижнюю границу (то есть все события никогда не будут сильно сгруппированы вокруг одного момента времени)
Усилия на данный момент:
Как видно из названия вопроса, я думал об использовании отсортированного списка чисел. Если я использую связанный список для вставки в постоянное время, то у меня возникают проблемы с поиском позиции, в которой можно быстро (сублинейно) вставлять новые события.
Прямо сейчас я использую приближение, в котором я делю время на сегменты и отслеживаю, сколько событий в каждом сегменте. Затем обрабатывайте сегменты один за другим по мере того, как «проходит» время, всегда добавляя новый сегмент в конце при удалении одного из фронта, таким образом сохраняя количество блоков постоянным. Это быстро, но только приблизительное.