всем привет.

алгоритм игры, требует создание огромного кол-ва временных отсчетов(таймеров).
т.е. некоторое событие в игре, к примеру, создает выдержку времени в 5 сек, по истечении которой, создатель этой выдержки, получит уведомление. но, т.к. игр одновременно выполняющихся могут быть тысячи, то и выдержек времени на одно событие тоже нужно тысячи. создавать deadline_timer на каждую выдержку не разумно.
все подобные отсчеты, синхронизируются единым источником. квант времени - 1 сек.

первое что мне пришло в моцг, это некий map, ключем в котором будет интервал, а значением - некоторый объект, содержащий в себе boost::signals2::signal(на который подписываются создатели интервалов), и значение интервала уменьшающееся при каждом тике системных часов. при достижении нуля будет испущен сигнал, который оповестит об окончании интервала подписчиков.
но данный способ не подходит потому что, отсчет для каждого создателя интервалов, должен начинаться с момента создания интервала. т.е. как бы намек на то, что создание объектов должно происходить по двум критериям: 1)текущему времени, 2)требуемому интервалу.
т.е., к примеру, если в течении одной секунды поступит три запросов на создание интервалов длительностью в 5, 5, 15 секунд, то будет создано два объекта, при том на первый будет подписано два создателя, на второй - один. этот способ решает проблему тысяч объектов... но что-то в нем не то... пока что не могу понять что, и на###кодить зря, тоже не хочется.

что скажите по этому поводу?
возможно есть иные варианты?

спасибо.

Добавлено через 9 минут и 17 секунд


Это сообщение отредактировал(а) boostcoder - 16.10.2011, 10:14

Up.
интервалов бывает два типа:
1. единажды испускаемые.
2. постоянно испускаемые.

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

Добавлено через 4 минуты и 1 секунду
Up.
вообще-то, для первых и вторых, нужно две карты  

максимально возможный интервал известен? или он может быть любым?

вообще, интервалы могут быть следующими:
5 сек.
15 сек.
5 мин.
15 мин.

Добавлено @ 11:02
Up.

Это сообщение отредактировал(а) boostcoder - 16.10.2011, 11:08

тогда предлагаю заюзать массив размером
72 * 3600 элементов
и переменную, содержащую индекс в массиве
элемент с этим индексом обрабатывается через 1 сек. (при след. срабатывании таймера)
каждый тик увеличивает индекс на 1
таким образом за О(1) на каждом тике мы точно знаем, какие обработчики вызвать

постоянно испускаемые реализуются просто: достаем слот из array[i] и помещаем в array[i + K], K - интервал срабатывания (может быть отрицательным из-за цикличности массива и текущего индекса)

поправил. более длительные интервалы не относятся к этой задаче. ими занимается планировщик.

boostcoder, 
какие у моего способа недостатки?

не вижу пока недостатков. думаю над реализацией.

если пустоты MAKCim массива в варианте слишком большие но и не хочется терять в точности можно объеденить этот вариант с вашим..
т.е. сажать группу близких интервалов в один элемнт таблицы.. и когда к ним уже подойдет очередь декрементировать до вызова.. 

72 * 3600 * 8 = ~2M
т. е. я не думаю, что тут оверхед по памяти

я бы сделал мультимап, и ключом не интервал, а время. На одно время может быть назначено несколько событий.
Один таймер, приходя в процедцру обработки каждую секунду, обрабатывает начало мультимапа, и выполняет события, для которых настало время.
Мультимап отсортирован по времени, поэтому, все события для которых настало время, расположены в начале, посему обрабатывать мультимап долго не придется.
Событий может естественно и не быть  (если первый элемент указывает в будущее)

это вариант я выше тоже описал.

если все равно сортированный, то чем просто вектор/очередь не подходит ?
 

mes, добавлять удобней.

хотя немного не такой алгоритм...

Единственно, что надо не забыть продумать, это  защиту/реакцию на изменения системного времени.
Хот это и не часто происходит но все-же... Этот момент надо продумать...

имхо, на реальное системное время вообще не нужно цепляться..

почему?

Я именно, говорю чтобы цепляться на системное время. В этом случае получается самый быстрый и экономный алгоритм. А изменение системного времени (значительное) - это настолько редкая операция, что можно вообще считать что этого не будет. (разве что сервер переезжает в другую страну  ) Но это уже форс мажор. Просто об этом нужно помнить.

Добавлено @ 17:48
mes, А впрочем, вы правы! зачем именно системное время. Можно же сделать свои локальные часы в программе. В принципе достаточно простой тикер.
Тогда вообще проблем не будет. 


Это сообщение отредактировал(а) volatile - 16.10.2011, 17:55

Если тысяч немного, то такой вариант должен справиться без проблем.
http://liveworkspace.org/code/eb6aacd8331c...ee1e4fb01b07a92

Это сообщение отредактировал(а) Леопольд - 17.10.2011, 08:13

Леопольд, оригинальное решение как для singleshot-таймеров, и подчищаются как раз...Но топикстартеру, скорее всего, для этого дела требуется отдельный поток (того же asio::deadline_timer с worker-ом в отдельном потоке), да и возможность циклических запусков тоже. Но, наверное, вполне можно доработать и этот интересный пример используя std::thread и т.п. 

Это сообщение отредактировал(а) serghd - 17.10.2011, 01:14