|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Mar 2003 23:20:12
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
Dmitri Khanevski wrote:
>
>
> Дело в том что они пpиходят из pазных источников асинхpонно, т.е.
> пpедваpительно не отсоpтиpовать.
Hу есть другой вариант:
Допустим, ты apriori знаешь, что максимальная задержка заявки в очереди - N
тиков
(например, N=1024). Тогда заводишь массив из N элементов. Каждый элемент массива
содержит голову списка событий, которые должны быть выполнены в некий момент Т.
С каждым тиком таймера обработчик бегая по кругу, перескакивает на след. элемент
массива,
и выполянет весь список, который там лежит. После чего весь список освобождает,
и
заносит в элемент NULL. Если же там и ранее лежал NULL - то ничего не делает, а
просто
выходит из таймерного прерывания.
То есть выборка происходит очень быстро. Аналогично быстро можно сделать
добавление
заявки. Пусть известно, что данная заявка должна простоять в очереди X тиков.
Тогда ты ее добавляешь в голову списка, находящуюся в элементе массива
с позицией (CUR_POS + X) % N.
Таким образом, и добавление, и извлечение делается за O(1) времени.
Первый недостаток способа - то, что заявки на одно и то же время будут
выполняться
задом наперед. Если это критично, надо иметь для списка два указателя - на
начало и на
конец списка. тогда можно быстро дибавлять заявки в конец.
Второй недостаток способа - то, что N может быть достаточно большим, а заявки -
сравнительно
редкими. В этом случае надо сделать, чтобы каждый элемент массива соответствовал
не
одному тику, а скажем, M=10. И чтобы обработчик потихоньку вынимал заявки из
тек. очереди.
Hадеюсь, идея понятна.
> >> Хотелось бы уменьшить максимально вpемя
> >> pаботы, а не сpедневзвешенное.
См. выше. Только, возможно, памяти многовато понадобится...
>
> Я так понял что там удалять медленней будет.
Hу там и есть замаскированое дерево. Или же "система черпаков", аналогичная
вышевысказанной идее группирования тиков в группы по M.
А лучше ничего не сделаешь. Дерево - это тоже NlogN времени.
И тоже в худшем случае может свалиться в N**2.
А способ, который я дал - хоть и памяти требует - зато вообще
за константное время работает...
> оно штука медленная. Только вот иницииpовать указатель очень аккуpатно
> пpидется :\
Это да.
>
> В данный момент не на плюсах. А в чем pазница ?
В том, что только для C++ есть STL.
В котором есть map, multimap, priority_queue, etc.
> OIK> При вставке же надо пробежать в среднем половину отсортированой
> OIK> тек. очереди, и вставить новый элемент на место.
>
> Вот это-то и долго :(
> К тому же в сpеднем это одно, а в худшем дpугое. Я вынужден pасчитывать на
> худший случай.
Hу ты можешь число очередей побольше сделать.
Ты же сам писал, что у тебя заявок в системе примерно несколько сотен.
Сделай 256 очередей - и в каждой будет лежать от силы 10 элементов.
А 256 удобно с той точки зрения, что индекс массива хорошо считать -
приведением времени к unsigned char.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
