|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 10 Mar 2003 19:56:14
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
Dmitri Khanevski wrote:
>
> В общем всем больше спасибо, после пpаздников еще подумаю, может чего в голову
> и пpидет.
Я вот тоже подумал, и кажется, нашел решение.
Это нечто промежуточное между деревом и "кольцом выполнения",
описанным ранее.
Работать будет чуть помедленее, чем "кольцо выполнения",
но и память не особо будет использовать.
Вводная:
Как известно, в дереве поиск (элемента или места вставки)
очень быстрый - Log(N). Множитель N возникает за счет затрат
на перестройку дерева после ввода/удаления узла.
Если же дерево не перестраивать, легко свалиться в N^2.
Идея в следующем:
Hадо бы хранить данные в таком дереве, которое не требуется
перестраивать. Структура такого дерева ко мне пришла из анализа
дерева ветвлений поразрядной обменной сортировки.
Суть вот в чем:
Согласно твоему условию, макс. задержка
не может превышать 3.6 миллионов тиков. Такую задержку гарантировано
можно вместить в двоичное число разрядностью 22.
Введем понятие кольцевого времени. Кольцевое время - это 22 младших
бита от абсолютного времени.
Предположим, что таймерный счетчик считает время в кольцевом времени,
то есть вместо 2^22 он переходит в ноль.
Допустим, у тебя есть заявка на время T (абсолютное).
Посредством битовой маски преобразовываем его в кольцевое.
(неоднозначность от этого не возникает, так как apriori известно,
что заявка лежит на ближайшее время из циклов 2^22), и таймерный счетчик
кольевого времени совпадет с текущим кольцевым временим в "истинный"
момент выполнения заявки.
Рассмотрим биты int-a этого кольцевого времени (от старших к младшим) как
путь в дереве глубиной 22. То есть если тек. бит = 0 - идем к левому потомку,
если бит = 1 - к правому.
В терминальных узлах дерева в указателях left/right
лежат не потомки - узлы дерева, а головы линейных
списков заявок на данное время.
Таймерная программа, выполняющая заявки, живет в кольцевом времени.
По каждому тику, посчитав текущее кольцевое
время, она пытается из дерева вынуть список заявок и выполнить его.
После выполнения очередного списка заявок на тек время она
освобождает список и уникальную для этого списка часть дерева. Причем дерево не
перестраивается - от него просто "отпиливается ветка". Поэтому время
такой операции в худшем случае O(22). Точка пиления тоже находится
в процессе спуска по дереву, когда идем к тек. узлу.
Точка пиления - это наинизший узел дерева, имеющий всех детей непустыми.
Вставка в такое дерево делается аналогично, за время в худшем случае O(22).
Заявка вставляется в позицию, определяемую битовой цепочкой
значения кольцевого времени этой заявки.
Расходы по памяти на дерево также небольшие. В худшем случае это число
заявок Z умноженое на маск. глубину дерева, т.е. 500 * 22 = 11K.
Выше я рассмотрел дерево "ветвистостью 2". Hа самом деле,
дерево может быть "ветвистостью 4,8, etc".
При этом для дерева "ветвистостью 4" каждый шаг в дереве будет соответствовать
2-м битам int-a, то есть для такого дерева время/память будет О(11).
Хотя конечно при этом сам размер элемента дерева вырастет, и по памяти
ты проиграешь немного. Зато скорость подымешь.
Замечу, что каждая ветка дерева имеет фиксированую глубину 22.
Тогда из глубины дерева ты однозночно определяешь, на что указывает
указатель потомка - на след. элемент дерева, либо же на лин. список заявок.
PS. Можно оптимизировать:
Hе дергать таймерную программу, каждый тик, чтобы она в дерево ходила, а сделать
так:
После выполнения заявок на тек время и освобождения списка/части дерева
таймерная программа определяет путь в дереве к след. узлу, и представляет
его в виде int-a. После чего ложится спать на время t, равное разнице в
битовых путях между тек. узлом (что только что был удален) и вновь найденым
узлом.
Только в этом случае надо не забыть после вставки очередного нового узла дерева
(если элемент добавляем в уже готовый список, ничего делать не надо)
проверить - а не находится новая заявка в текушем sleep-интервале.
И в случае чего подкорректировать sleep-интервал, чтобы обработчик
не проспал текущую заявку.
--
#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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
