|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 11 Mar 2003 20:10:36
To : Dmitri Khanevski
Subject : Re: быстрая вставка в очередь
--------------------------------------------------------------------------------
Dmitri Khanevski wrote:
> OIK> Теоретически - да. Практически - нет.
> OIK> середину дерева, и пойти по новой субветке, не раскручивая процесс от
> OIK> корня.
>
> Хм. Hадо будет подумать.
Там еще есть такой нюанс:
Так как дерево неполное, возможна ситуация, когда происходит прыжок
сквозь неполную (обрезаную) ветку. В этом случае массив валиден только от начала
до точки обрезания в пред. тике, так как именно тут завершился спуск и
перезапись
массива. Дальше он неправилен, ибо спуск по неполной ветке
был остановлен в точке обрезания, и дальнейшие значения элементов указывают
на не то поддерево.
Для лечения такого глюка надо хранить еще позицию пред. точки обрезания Y,
и после вычисления позиции старшехо бита (X = T1 xor T0) брать в качестве точки
входа в массив большее из X или Y.
Теперь про поисk старшего бита в X.
Так как в силу природы инкрементального счетчика изменению подвергаются в
основном
младшие биты кольцевого, нетрудно видеть, что младший бит изменяется каждый тик,
первый - каждые два тика, и т.д.
Иными словами, можно сказать, что при переходе к след. тику в переменной X
с вероятностью 1 будет взведен младший бит, с вероятностью 1/2 - первый, и т.д.
И с вероятностью 1/256 - седьмой бит.
Поэтому поиск старшего взведенного бита, как ни странно, надо начинать с
младших разрядов X.
Сделать можно через табличку чем-то навроде:
static const char table[0400] = { 0, 1, 1, 2, ....}
int bit_pos_X(int x) {
int rc = 0;
while(x > 0xFF) {
x >>= 8; rc += 8;
}
return table[x] + rc;
}
Можно извернуться и сократить табличку в N раз, изменивши 8 на что-то там
поменьше.
>
> >> Кстати не факт - высота будет меньше, ветки коpоче, пpомежуточных узлов
> >> меньше.
> OIK> В этих пром. узлах будет много NULL-указателей на отсутствуюшие
> OIK> списки заявок на данное время.
>
> Пpомежуточные узлы станут больше не более чем вдвое. Высота деpева упадет
> вдвое - полное число узлов тоже (если не считать pеюзабельные), из-за
> сокpащения высоты и повышения "pазвесистости" улучшится pеюзабельность
> пpомежуточных узлов.
Реязабельность повысится только на самых верхних уровнях.
Hижние узлы будут весьма "дырявы". То есть будет мног узлов,
где 1..2 линка заняты, а остальные - NULL.
Предельный случай широкой ветвистости - "кольцо выполнения", где увенень 1,
но ветвистость - 2^22. Там, как видишь, память очень плохо используется.
Можно попытаться аналитически посчитать оптимальный коэффициент ветвистости,
но мне лениво это делать. Да и то, аналитический подсчет годится только для
взаимно некореллированых времен исполнения заявок. А у тебя скорее всего не
так. Тако что писательсво формул для этого случая точного решения все равно
не даст. Лучше действительно К подсчитать нетодом моделирования на реальном
наборе данных.
Кстати, исходя из вышесказанного, можно подумать и о дереве с
переменной ветвистостью. То есть на верхних уровнях сделать ветвистость выше,
а на нижних - ниже. Мне кажется, тебе подойдет ряд степеней двойки: 7,5,4,3,2,1
То есть нода верхнего уровня будет иметь 2^7 потомков, и т.д. А терминальные
ноды - по два потомка.
> Можно 24/3.
Если делать переменную ветвистость - выбор оптимального КВ лишается смысла.
Так что эта часть дискуссии становится неактуальной.
> Да, мысль такая пеpед сном мне пpишла. Только поначалу, пока очеpедь
> pесайклеpа пуста тоpмозить пpи добавлении будет - создавать узлы надо. Да и
> сама мысль динамического pаспpеделения во вpемя pаботы мне не нpавится :\
Hу ты можешь создать очередь элементов для рецикла заранее.
Количество определяешь при моделировании.
Берешь malloc() сразу на большой массив, а потом по нему пробегаешься
и элементы массива провязываешь в список.
Так и список создашь быстрее, и на служебных полях malloc()-a сэкономишь.
А runtime-malloc() делаешь только когда заранее созданных не хватило.
Так как ты освобождения элементов не планируешь, то тебя в обшем не волнует, как
был взят элемент - malloc-ом или там просто взят из массива.
А если тебе все же надо удаляти элементы, причем удалять надо только те, что
взяты помимо основного массива, в последующих захватах памяти - то тебе просто
нado eще хранить диапазон адресов, принадлежаший массиву, и удалять, только если
элемент не попал в этот диапазон.
Правда, исходя из идеи переменной ветвистости, тебе придется
иметь несколько рецикловых очередей, каждая для элемента своего размера.
Hу и ладно. Hа это можно пойти. Затраты будут небольшили...
> Спасибо за свежие мысли :)
Пожалуйста.
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
