|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Val Krigan 2:5020/400 07 Mar 2003 23:29:57
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
"Dmitri Khanevski" wrote
> VK> Попробуй деревья, если на С++, то это std::map<>. Красно-черное
> VK> сбалансированное дерево. Возможно тебе его производительности хватит за
> VK> глаза, останется время пооптимизировать в других местах.
>
> Хм. А поподpобней для данного случая можно ?
Красно-черное дерево - это такое сбалансированное дерево, в котором узлы
помечены красным или черным цветом, там еще есть несколько требований, элементы
отсортированы. Далее есть свои алгоритмы для вставки и удаления элементов. В
интернете по ключевым словам (red black tree) можешь найти исходные тексты.
Применительно к твоему случаю: делаешь время ключом (по которому сравниваются
два элемента). При вставке нового элемента он попадет в нужное место (между
большим и меньшим), при этом дерево возможно немного перестроится. Удаляешь ты
всегда первый элемент (меньший), при этом дерево тоже перестраивается (в данном
случае так называемые "повороты"). Остается проверить на практике достаточно ли
быстро все это происходит.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
