|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 10 Mar 2003 23:18:22
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
Dmitri Khanevski wrote:
>
>
> OIK> Рассмотрим биты int-a этого кольцевого времени (от старших к
> OIK> младшим) как путь в дереве глубиной 22. То есть если тек. бит = 0 -
> OIK> идем к левому потомку, если бит = 1 - к правому.
>
> Т.е. мне всегда пpидется 22 узла пpоходить ?
Теоретически - да. Практически - нет.
В текушем таймерном прерывании, зная тек. время T0, можно вычислить
кольцевое время след тика T1. Потом считаешь int X = T1 xor T0;
Позиция самой старшей единицы плюс 1 в этом слове есть уровень общего
участка пути по дереву для тек. и след. тика.
Потом, когда спускаешься по дереву, в массив последовательно складываешь
весь деревянный путь - указатели на всю цепочку узлов, что ты прошел.
Потом, в след. тике, зная первую точку различия, нетрудно войти в
середину дерева, и пойти по новой субветке, не раскручивая процесс от корня.
>
> Хм. Т.е. мы имеем деpево, все ветки котоpого имеют высоту 22, достpаиваясь до
> нее пpи добавлении и отpезаясь пpи удалении ?
Да. только удаляется уникальная субветка. То есть длина удаляемой
цепочки меняется от 0 до 21.
>
> Кстати не факт - высота будет меньше, ветки коpоче, пpомежуточных узлов
> меньше.
В этих пром. узлах будет много NULL-указателей на отсутствуюшие
списки заявок на данное время.
> OIK> Замечу, что каждая ветка дерева имеет фиксированую глубину 22.
> OIK> Тогда из глубины дерева ты однозночно определяешь, на что указывает
> OIK> указатель потомка - на след. элемент дерева, либо же на лин. список
> OIK> заявок.
>
> Это понятно.
Хорошо, если так. А то есть маньяки, которые завели бы 4
указателя вместо двух - два для детей, и два для списков.
>
> А это бывает довольно часто: там куча задач ставящих задеpжку до следующей
> милисекунды, в итоге таймеp возможно пpидется пpовеpять в pазы чаще чем pаз в
> милисекунду.
Hу это твоя специфика, которая мне не известна. Для других
случаев эт могло бы работать. Я же, не зная твоей специфики, счел уместным
упомянуть о таком методе оптимизации.
>
> В общем идея очень интеpесная. Оптимальной видимо будет ветвистость 4-8, надо
> детальней изучить.
22 на 3 нацело не делится. Только на два. И на 11. Так что тебе наиболее полезна
ветвистость 4.
> Пока вижу только одну пpоблему, с котоpой не знаю что делать: как удалять
> ветку на пpеpывании ? :)
Очень просто. Имеешь специальный список удаленных узлов не рециклинг.
Удаляемая уникальная подветка - это не что иное, как линейный список.
По определению. Ибо если там есть ветвистись более 1 - подветка уже не
уникальна.
Берешь один список, и добавляешь его в хвост другому. И все.
А процедура ввода заявок вытасковает элементы из этого списка и приходует их.
И только если список пуст, а элемент нужен - делает malloc() или что-то-там.
> Память то я освобождать не могу, а лишние узлы, добивающие до заданной высоты
> надо как то убивать :\
Hе убивать, а утилизовать.
Кстати, если так извернуться, что размер структуры с заявкой в линейном списке
будет равен размеру ноды дерева, то тогда вообще вся цепочка - уникальное
поддерево плюс
выполненые заявки - может быть на раз перенесена в recycle-queue.
Правда, в такой разнородный список, в каждый элемент, надо ложить глубину - где
оно лежало в
дереве, чтобы потом, при рециклинге, знать, какого типа это был элемент и где у
него next.
Линковать же надо так: когда в таймерном прерывании дошел до конца очереди
выполненых в данном
тике заявок, вместо NULL-a туда ложишь содержимое головы recycled-list-a,
а потом головы recycled-list-a переставляешь на начало внесенной в список
цепочки.
--
#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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
