Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > задача на таймеры


Автор: boostcoder 16.10.2011, 10:11
всем привет.

алгоритм игры, требует создание огромного кол-ва временных отсчетов(таймеров).
т.е. некоторое событие в игре, к примеру, создает выдержку времени в 5 сек, по истечении которой, создатель этой выдержки, получит уведомление. но, т.к. игр одновременно выполняющихся могут быть тысячи, то и выдержек времени на одно событие тоже нужно тысячи. создавать http://www.boost.org/doc/libs/1_47_0/doc/html/boost_asio/reference/deadline_timer.html на каждую выдержку не разумно.
все подобные отсчеты, синхронизируются единым источником. квант времени - 1 сек.

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

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

спасибо.

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


struct object {
   boost::signals2::signal<...> signal;
   std::time_t interval;
   
   object(std::time_t interval)
      :interval(interval)
   {}

   void tick(std::time_t time) {
      if ( 0 == interval-- ) {
         signal(time);
      }
   }

};

std::map<std::time_t, std::map<std::time_t, object>> map;

...


void create_timeout(std::time_t interval, slot_type slot) {
   map[std::time(0)][interval].signal.connect(slot);
}

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

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

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

Автор: MAKCim 16.10.2011, 10:57
максимально возможный интервал известен? или он может быть любым?

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

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

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

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

Автор: boostcoder 16.10.2011, 11:09
поправил. более длительные интервалы не относятся к этой задаче. ими занимается планировщик.

Автор: MAKCim 16.10.2011, 11:13
boostcoder, 
какие у моего способа недостатки?

Автор: boostcoder 16.10.2011, 11:23
Цитата(MAKCim @  16.10.2011,  11:13 Найти цитируемый пост)
какие у моего способа недостатки?

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

Автор: mes 16.10.2011, 12:51
Цитата(boostcoder @  16.10.2011,  10:23 Найти цитируемый пост)
думаю над реализацией. 

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

Автор: MAKCim 16.10.2011, 13:06
Цитата(mes @  16.10.2011,  12:51 Найти цитируемый пост)
если пустоты MAKCim массива в варианте слишком большие но и не хочется терять в точности можно объеденить этот вариант с вашим..

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

Автор: volatile 16.10.2011, 15:07
Цитата(boostcoder @  16.10.2011,  10:11 Найти цитируемый пост)
первое что мне пришло в моцг, это некий map, ключем в котором будет интервал, а значением - некоторый объект

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

Автор: boostcoder 16.10.2011, 15:10
Цитата(volatile @  16.10.2011,  15:07 Найти цитируемый пост)
ключом не интервал, а время

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

Автор: mes 16.10.2011, 15:10
Цитата(volatile @  16.10.2011,  14:07 Найти цитируемый пост)
я бы сделал мультимап, и ключом не интервал, а время

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

Автор: volatile 16.10.2011, 15:14
Цитата(mes @  16.10.2011,  15:10 Найти цитируемый пост)
чем просто вектор/очередь не подходит ?

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

Автор: boostcoder 16.10.2011, 15:14
хотя немного не такой алгоритм...

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

Автор: mes 16.10.2011, 17:28
Цитата(volatile @  16.10.2011,  14:24 Найти цитируемый пост)
Единственно, что надо не забыть продумать, это  защиту/реакцию на изменения системного времени.

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

Автор: volatile 16.10.2011, 17:42
Цитата(mes @  16.10.2011,  17:28 Найти цитируемый пост)
имхо, на реальное системное время вообще не нужно цепляться.. 

почему?

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

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

Автор: Леопольд 16.10.2011, 20:28
Цитата(boostcoder @  16.10.2011,  10:11 Найти цитируемый пост)
т.к. игр одновременно выполняющихся могут быть тысячи

Если тысяч немного, то такой вариант должен справиться без проблем.
Код
#include <ctime>
#include <iostream>
#include <set>
#include <algorithm>
#include <functional>
#include <stdexcept>

#include <unistd.h>

struct Timer
{
   struct Exception: public std::runtime_error
   {
      Exception(std::string const& msg): std::runtime_error(msg)
      {}
   };

   struct ClockErrorExc: public Exception
   {
      ClockErrorExc(std::string const& msg): Timer::Exception(msg)
      {}
   };

   // секундный таймер
   Timer(std::time_t s, std::function<void()> const& callback): callback_(callback)
   {
      std::time_t current = ::clock();
      if(current != -1)
      {
         stamp_ = current / CLOCKS_PER_SEC + s;
      }
      else
      {
         throw ClockErrorExc("error in ::clock function");
      }
   }

   Timer()
   {
      std::time_t current = ::clock();
      if(current != -1)
      {
         stamp_ = current / CLOCKS_PER_SEC;
      }
      else
      {
         throw ClockErrorExc("error in ::clock function");
      }
   }

   void expire() const
   {
       callback_();
   }

   bool operator< (Timer const& rhs) const
   {
      return this->stamp_ < rhs.stamp_;
   }

private:
   std::time_t stamp_;
   std::function<void()> callback_;
};

struct TimerSet: private std::multiset<Timer>
{
   typedef std::multiset<Timer> Base;

   using Base::insert;
   void expire()
   {
      Base::iterator bound = std::upper_bound(this->begin(), this->end(), Timer());
      for(Base::iterator iter = this->begin(); iter != bound; ++iter)
      {
         iter->expire();
      }
      this->erase(this->begin(), bound);
   }
};

int main ()
{

   bool expired = false;
   TimerSet timers;

   timers.insert(Timer(1, [&]() { std::cout << "time's up" << std::endl; expired = true; }));
   while(!expired)
   {
      timers.expire();
//      sleep(1);
   }

   return 0;
}

http://liveworkspace.org/code/eb6aacd8331c66963ee1e4fb01b07a92

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)