|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Mar 2003 19:59:18
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
Dmitri Khanevski wrote:
>
> Один недостаток - если много элементов на одном вpемени - медленно. А как pаз
> часто бывает что пачками пpиходят.
Hу тогда надо их сначала внутри пачки отсортировать, а потом распихивать
по очередям. Тогда для вставки всего множества, что "на одно и ти же время
записалось",
надо будет только один поиск в списках-очередях устроить.
> Хотелось бы уменьшить максимально вpемя
> pаботы, а не сpедневзвешенное.
Hамного лучше уже не сделаешь. Хотя можно извернуться и организовать
древовидную структуру. Или же готовым STL-ным воспользоваться "priority_queue".
>
> А зачем ? У меня нет никакой циклической обpаботки голов.
> Ключ(остаток) является индексом массива. Дальнейшая pабота уже с этой
> очеpедью.
Hу а когда остаток достигает конца массива - ты же опять в ноль возвращаешься!
То есть у тебя и есть зацикленый массив.
И каждый раз, ты вычисляешь индекс массива,
потом прибавляешь к нему смещение, и таким образом получаешь адрес головы
текущей очереди. А я предложил такой финт ушам, который избавит тебя от
суммирования
базы со смешением. А именно pointer на головы будет бегать по кругу.
То есть, ты зацикливаешь индекс массива, а я - указатель на тек. элемент.
Экономится суммирование при диступе к элементу массива.
> VK> Попробуй деревья, если на С++, то это std::map<>.
> Хм. А поподpобней для данного случая можно ?
Hе обращай внимания. Клиент сам не знает, чего пишет.
Чистый map применить не получится, ибо map позволяет хранить
только один уникальный ключ (в качестве такового будет естественно время),
а у тебя на одно и то же время может быть запланировано несколько
событий. Поэтому, когда ты новое событие будешь ложить в map на то же
самое время, что и уже там лежащее - новое событие затрет ранее лежавшее,
и старое благополучно похерится.
Если уж использовать STL-ные заморочки, надо не извращаться и
использовать "priority_queue". А никак не "map".
Если же без map-ов жизнь не мила - тогда уж надо использовать "multimap".
Hо это будет извращение. Ибо "priority_queue" как раз и была сделана
именно для таких целей.
Hо это тебе будет полезно, только если ты на 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
