Здравствуйте, Centaur, Вы писали:

C>Здравствуйте, mr_trwister, Вы писали:

_>>>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

C>>>А мы их заранее свалим в какую-нибудь структуру, отсортированную по времени ближайшего наступления.

_>>а сортировать кто будет?

C>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

для такого случая самым эффективным вариантом будет контейнер priority_queue он хранит элементы в частично отсортированном виде, ему не важен полный правильный порядок, а важно чтобы "лучший, ближайший" по какому либо критерию элемент лежал на вершине. Здесь в ветке С++ как-то уже проводили замеры производительности, эта штука показывает хороший результат

_>>>>а если событий несколько тысяч? (десятков/сотен тысяч)

PD>>>Что значит несколько сотен тысяч ? В секунду ? В минуту ? Сколько их должно ожидаться в любой момент времени ?

_>>всего несколько десятков/сотен тысяч событий, которые могут возникать с заданной периодичностью.

_>>такое большое количество событий я указал, чтобы подвести к мысли, что WaitForMultipleObjects имеет ограничение на 64 ожидаемых WaitableTimer.

M>Интересно, где вы нашли ограничение 64 объекта обрабатываемых функцией WaitForMultipleObjects. Из своего опыта знаю, что 256 обектов она обрабатываает без проблем

DWORD WINAPI WaitForMultipleObjects(DWORD nCount, const HANDLE* lpHandles, BOOL bWaitAll, DWORD dwMilliseconds);

nCount — [in] The number of object handles in the array pointed to by lpHandles. The maximum number of object handles is MAXIMUM_WAIT_OBJECTS.

смотрим в winnt.h и видим #define MAXIMUM_WAIT_OBJECTS 64

_>>>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

C>>>А мы их заранее свалим в какую-нибудь структуру, отсортированную по времени ближайшего наступления.

_>>а сортировать кто будет?

C>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту. одновременно надо вычислить, сколько всем событиям осталось до наступления. разве нет? какая структура нам будет сама вычислять разницу м пересортировывать за время меньшее O(N) ?

Здравствуйте, mr_trwister, Вы писали:

C>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

Поскольку события хранятся отсортированными, то ближайшее событие — это первое в очереди. Его ближайшее время наступления предположительно уже вычислено и записано прямо в нём. Также пусть событие умеет пересчитать своё следующее время наступления.

_>одновременно надо вычислить, сколько всем событиям осталось до наступления.

Всем не обязательно, достаточно первому. Время следующего наступления меняется, когда событие наступает и отрабатывает.

class Event
{
public:
    Event(const Event& other);
    Event& operator=(const Event& other);

    DWORD time(); // of nearest occurence
    bool calculateNext(); // return false if no more occurences
    void execute();

    class earlier : public std::binary_function<Event, Event, bool>
    {
    public:
        bool operator()(const Event& lhs, const Event& rhs) const
        {
            return lhs.time() < rhs.time();
        }
    };
};

std::set<Event, Event::earlier> events;

while (!bStop)
{
    Event e = events.front();
    events.pop_front();
    e.execute();
    if (e.calculateNext()) events.insert(e);
    Sleep(events.front().time() - GetTickCount());
}

Расширение на случай, когда за одну итерацию сразу отрабатывает много событий, тривиально и предоставляется читателю в качестве упражнения

C>>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

C>Поскольку события хранятся отсортированными, то ближайшее событие — это первое в очереди. Его ближайшее время наступления предположительно уже вычислено и записано прямо в нём. Также пусть событие умеет пересчитать своё следующее время наступления.

_>>одновременно надо вычислить, сколько всем событиям осталось до наступления.

C>Всем не обязательно, достаточно первому. Время следующего наступления меняется, когда событие наступает и отрабатывает.

[...]

теперь понятна ваша мысль. хорошее решение с алгоритмической точки зрения.

с практической же — постоянное удаление из контейнера и добавление в контейнер объекта кажется мне несколько неоптимальным =)


зы: ок. думаю, что обсуждение можно смело заканчивать. все основные подходы к организации были рассмотрены — начиная с алгоритмических и заканчивая очередями таймеров win32. всем огромное спасибо за советы и помощь!

Здравствуйте, mr_trwister, Вы писали:

C>>>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>>>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

C>>Поскольку события хранятся отсортированными, то ближайшее событие — это первое в очереди. Его ближайшее время наступления предположительно уже вычислено и записано прямо в нём. Также пусть событие умеет пересчитать своё следующее время наступления.

_>>>одновременно надо вычислить, сколько всем событиям осталось до наступления.

C>>Всем не обязательно, достаточно первому. Время следующего наступления меняется, когда событие наступает и отрабатывает.

_>[...]

_>теперь понятна ваша мысль. хорошее решение с алгоритмической точки зрения.

_>с практической же — постоянное удаление из контейнера и добавление в контейнер объекта кажется мне несколько неоптимальным =)

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

_>зы: ок. думаю, что обсуждение можно смело заканчивать. все основные подходы к организации были рассмотрены — начиная с алгоритмических и заканчивая очередями таймеров win32. всем огромное спасибо за советы и помощь!

я писал подобное на питоне, работает.

Остаются мелочи:
— после обработки события надо перебирать и обрабатывать события, которые просрочены.
— ввести системное событие для управления этой самой очередью и завершения работы, вызывать его достаточно часто, чтобы не было ощущения, что программа зависла; самый простой пример -- раз в 5 секунд смотреть свободное место на диске, если меньше гигабайта -- завершать цикл.

Успехов.