Re: быстрая вставка в очередь

From

Oleg I. Khovayko ()

To

Dmitri Khanevski ()

Date

2003-03-07T18:59:18Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Dmitri Khanevski wrote:
> 
> Один недостаток - если много элементов на одном вpемени - медленно. А как pаз
> часто бывает что пачками пpиходят. 

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

> Хотелось бы уменьшить максимально вpемя
> pаботы, а не сpедневзвешенное.

Намного лучше уже не сделаешь. Хотя можно извернуться и организовать
древовидную структуру. Или же готовым STL-ным воспользоваться "priority_queue".

> 
> А зачем ? У меня нет никакой циклической обpаботки голов.
> Ключ(остаток) является индексом массива. Дальнейшая pабота уже с этой очеpедью.

Ну а когда остаток достигает конца массива - ты же опять в ноль возвращаешься!
То есть у тебя и есть зацикленый массив. 
И каждый раз, ты вычисляешь индекс массива,
потом прибавляешь к нему смещение, и таким образом получаешь адрес головы
текущей очереди. А я предложил такой финт ушам, который избавит тебя от суммирования
базы со смешением. А именно pointer на головы будет бегать по кругу.

То есть, ты зацикливаешь индекс массива, а я - указатель на тек. элемент.
Экономится суммирование при диступе к элементу массива.



>  VK> Попробуй деревья, если на С++, то это std::map<>.

> Хм. А поподpобней для данного случая можно ?

Не обращай внимания. Клиент сам не знает, чего пишет.

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

Если уж использовать STL-ные заморочки, надо не извращаться и
использовать "priority_queue". А никак не "map".
Если же без map-ов жизнь не мила - тогда уж надо использовать "multimap".
Но это будет извращение. Ибо "priority_queue" как раз и была сделана
именно для таких целей.

Но это тебе будет полезно, только если ты на C++ пишешь.
В других языках такого нету.


> VK> И как ты из него выбираешь следующий элемент?

> В том то и пpоблема что пеpемоткой по списку.

Что?!?!?!?!?

Я что-то не понял?
У тебя элементы в списке как лежат: в порядке вставки (как пришли) или
в порядке выполнения (как будут выполнены)?????

Все нормальные люди очередь к таймеру держат в линейном списке, сортированому
по времени выполнения!!!

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

Как только след. элемент тек. очереди на большее время - переходим к 
след. очереди. и т.д.

При вставке же надо пробежать в среднем половину отсортированой 
тек. очереди, и вставить новый элемент на место.

-- 
#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)