А есть ли в природе эффективные алгоритмы построения дерева, подобное кларионовскому?
Т.е., есть неотсортированная очередь (queue). Каждая запись имеет ссылку на "родителя".
Нужно отсортировать (построить) это queue в виде дерева (кларионовского).
Структура очереди примерно такая:
Код: Выделить всё
qTree queue
ID signed ! ИД текущей записи
ParentID signed ! ИД "родителя" (верхней ветки)
end Простым перебором очень долго, хотелось бы пошустрее
) Сергей - chusha@mail333.com ; chusha@hotbox.ru
(Добавление)
Примерно так.
Код: Выделить всё
!Создаём стек (очередь ключ-уровень-прочие данные) !
Stack Queue,Pre(Sta)
Key ...
Level Long
End
! Кладём на вершину пустой элемент (Пустой ключ,уровень=0)
Free(Stack)
Clear(Stack)
Add(Stack)
!Цикл
Loop
!Если стек пуст, всё завершено
If ~Records(Stack) Then Break.
! Снимаем элемент с вершины стека
Get(stack,Records(Stack))
Loc:Key=Sta:Key
Loc:Level=Sta:Level
!Отправляем элемент на выход
OutputQueue=Stack
Add(Outputqueue)
Delete(Stack)
!Добавляем на вершину стека его подчинённых в порядке убывания ключа
(уровень на 1 больше, чем у родителя)
Loop ! Цикл добавления подчинённых
...
Sta:Level=Loc:Level+1
End
End ! Конец цикла--
C уважением
Yuri
Адрес:yufil@mail.ru
Спасибо.
Со стеком я пробовал, но это не даёт заметных преимуществ перед работой с одной очередью(перебором). Может я что не так делал?
Хочется именно ЭФФЕКТИВНЫЙ алгоритм.
Скажем, построение дерева структуры классов ABC (с методами) идет порядка 5 сек. Это простым рекурсивным перебором одной очереди в 3.5 тыс.записей.
5 сек это долго. Хотелось бы секунды 2 или даже меньше...
Сергей
Программера SV который делал для C6 тормознутый парсер заголовков ABC и в итоге не справился с количеством файлов в каталоге LibSrc уволили? И пригласили тебя?
Ты прямо скажи, мы уж тут подмогнем
Круто!
__________________________________
Владимир Якимченко (IСQ 16 993 194)
А как работать перебором, я что-то не понимаю.
Может быть, стоит подумать, как для каждой записи искать подчинённые, чтобы не листать всю очередь
Если аккуратно сделать, каждая запись просматривается один-два раза, не больше
А что значит простым рекурсивным перебором? Это тот же стек, только реализованный по-другому.Скажем, построение дерева структуры классов ABC (с методами) идет порядка 5 сек. Это простым рекурсивным перебором одной очереди в 3.5 тыс.записей.
--
C уважением
Yuri
В приципе, можно свести перебор только к одному обращению к каждой записи, если удалять обработанные записи из входной очереди. Еще есть один алгоритм, когда идет обычный линейный обход входной очереди и обработанные записи копируются в результирующую очередь, находя при этом, свое место в ней.
Примерный алгоритм:
- ищем в результируюшей очереди родителя по его индексу.
Если нашли, то текущую запись из входной очереди вставляем в результирующую очередь сразу за родителем.
- если не нашли родителя на предыдущем шаге, то ищем потомков текущей записи в результирующей очереди. Если нашли, то текущую запись из входной очереди вставляем в результирующую очередь перед первым потомком.
- если не нашли потомков на предыдущем шаге, то просто вставляем текущую запись в начало или конец результирующей очереди.
Естественно, что результирующая очередь не подвергается явной сортировке. А поиск на первом и втором шаге производится по неявным ключам, которые будут созданы автоматом при первом обращении к ним.
В результате, в выходной очереди получим дерево.
Алгоритм примерный и не включает в себя дополнительную обработку гарантированного нахождения первого потомка.
Так как здесь может быть несколько вариантов от обычного восхождения вверх по записям до предварительной обработки двух соседних потомков при их вставке в выходную очередь.
В последнем случае всегда получаем у первого потомка вспомогательное поле равное 0, что позволяет быстро находить первого потомка одним GET-ом.
Есть еще несколько вариантов быстрого построения дерева.
Но они, обычно, подразумевают наличие некой специфической инфы в записях источника.
У меня, к примеру, в одной программе, в плане счетов, у каждого счета есть строчное поле с полным идентификатором, включающим всех родителей этого счета. Что-то типа: "1:15:10:120", где цифры - уникальные индексы каждого счета.
Естественно, что этот идентификатор не используется для ссылок на этот счет в проводках.
Он используется только при построении отчетов - после обычной закачки в очередь и сортировки по этому полю и наименованию самого счета получаем стандартное дерево.
Ну а сам идентификатор обновляется отдельной процедурой, если производятся модификации какой-либо ветки в плане счетов. Так как модификация плана счетов - процедура довольно редкая, то эти доп. накладные расходы практически никак не влияют на работу операторов.
Зато какой выигрышь и удобство получаем в дальнейшем!
Кстати, кроме построения отчетов этот идентификатор используется еще и для фильтрации проводок, когда необходимо, к примеру, вывести проводки по всем подчиненным счетам заданной ветки.
Попробуй сделай такой фильтр быстрым в обычных условиях! Как минимум, прийдется вставлять вызов отдельной процедурки, которая будет для КАЖДОГО счета подниматся вверх по его ветке для проверки ВСЕХ его родителей! А так - обычный INSTRING прямо в фильтре - и все!
Сергей имеет в виду, очевидно, рекурсию процедуры обхода ветки, которая обычно и используется при обходе вышеназванных деревьев. Т.е. без ручной организации стека.А что значит простым рекурсивным перебором? Это тот же стек, только реализованный по-другому.
Довольно удобно.
=============================
С уважением, Олег А. Руденко.
Oleg_Rudenko@mail.ru
Oleg_Rudenko@mail333.com
Библиотека DynaLib
http://dynalib.narod.ru
Я имел в виду, что при поиске потомков иногда приходится залазить на следующую запись.В приципе, можно свести перебор только к одному обращению к каждой записи, если удалять обработанные записи из входной очереди.
Всё-таки хочется иметь сортированный список потомков ...Если нашли, то текущую запись из входной очереди вставляем в результирующую очередь сразу за родителем.
Так дерево в смысле Кларион предполагает знание номера уровня. А здесь мы его узнаем только после завершения построения дерева ...Если нашли, то текущую запись из входной очереди вставляем в результирующую очередь перед первым потомком.
Это я понимаю. Просто в реальной жизни это делается внутри рутинки, а она не сильно совместима с рекурсией. А кроме того, алгоритм совершенно обязательно должен включать контроль на зацикливание, то есть проверку наличия объекта в выходной очереди.Т.е. без ручной организации стека.
Довольно удобно.
---------------------------------------
C уважением,
Юрий Философов
Написал: ClaList(2)
