forum.clarionlife.net

Здравствуйте

А есть ли в природе эффективные алгоритмы построения дерева, подобное кларионовскому?
Т.е., есть неотсортированная очередь (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)

Программера SV который делал для C6 тормознутый парсер заголовков ABC и в итоге не справился с количеством файлов в каталоге LibSrc уволили?

Хм, вроде справляется с LIBSRC. По крайней мере у меня проблем не было.
А что медленно, тут уж против фактов не попрёшь

Насчёт уволили - не знаю, не в курсе. Лично я бы не уволил по первому разу, но шею намылил бы и пинков надавал.

)

И пригласили тебя?
Ты прямо скажи, мы уж тут подмогнем

Не, я как занимался графикой так и занимаюсь.
А это так, для души

Но если хорошо получится (уже сейчас работает вдвое быстрее, а если ещё и оптимизировать!!!), то почему бы и не предложить заменить то что есть на более лучший вариант

Сергей

(Добавление)

Тормоза начались в C6 и усугубились в C6.1, так что не по первому уже разу

Судя по SV news у некоторых в C6.1 возникли проблемы как-то связанные с превышением некоего предела количества файлов в LibSrc, по крайней мере при выяснении обстоятельст падения Clarion, SV зачем-то интересовались именно количеством файлов в LibSrc, настрораживает-с.

А это так, для души Но если хорошо получится (уже сейчас работает вдвое быстрее, а если ещё и оптимизировать!!!), то почему бы и не предложить заменить то что есть на более лучший вариант

Дерзай!

Удачи!
__________________________________
Владимир Якимченко
Написал: ClaList(2)

Это я понимаю. Просто в реальной жизни это делается внутри рутинки, а она не сильно совместима с рекурсией.

Кто такое сказал?! Сколько пользуюсь именно рекурсиями рутинок - ни разу не было никаких сбоев!
Тем более, что на уровне машинного кода рутинка оформляется аналогично обычной процедуре.
Единственное отличие - если в рутинке есть оператор Return - в этом случае дополнительно используется механизм так называемых "длинных джампов" из Clarion-RTL.
Но и с ними, вроде-бы, проблем не было!

А кроме того, алгоритм совершенно обязательно должен включать контроль на зацикливание, то есть проверку наличия объекта в выходной очереди.

А зачем?! Мы ведь рассматриваем обратный связный список записей (перевернутое дерево) - т.е. список, в котором связь идет снизу-вверх (от листьев к веткам и далее - к корню), а обход начинается от корня и далее по веткам до листьев.
А при таком обходе зацикливание просто невозможно!
Точнее - возможно только в двух случаях:
- совпадение идентификаторов как минимум у двух разных записей.
Согласись - при нормальном состоянии ключей это - нереальная ситуация?
- идентификатор одной из записей равен 0 (нулю).
Т.е. дублирования ключей нет, но зацикливание возможно, т.к. начинаем обход дерева обычно с корневых записей, у которых идентификатор родителя = 0.
Я как-то "попал" один раз в такой цикл - в одни прекрасный момент програ стала "падать" на расчете - обход всего дерева.
И только после тщательного разбора "полетов" оказалось, что "падает" она из-за исчерпания выделенного стека.
Решение простое - проверять каждую запись на нулевой идентификатор. Или в блоке периодических проверок БД или непосредственно при обходе дерева. Я у себя использовал сразу оба эти варианта.

=============================
С уважением, Олег А. Руденко

А я вот стараюсь рекурсией вообще не пользоваться, потому как всегда можно заменить на манипуляции со стеком. И не вижу особых проблем.

Единственное отличие - если в рутинке есть оператор Return - в этом случае дополнительно используется механизм так называемых "длинных джампов" из Clarion-RTL. Но и с ними, вроде-бы, проблем не было!

Речь идёт не об этом. Для рекурсивного построения дерева надо рекурсивной процедуре передать параметр - корень текущего поддерева. А у рутинки параметра нет. Да и не вижу особого смысла - алгоритм со стеком действует быстро и надёжно, без особых наворотов.

а обход начинается от корня и далее по веткам до листьев.
А при таком обходе зацикливание просто невозможно!

Ещё как возможно-то. Правда, у меня деревья не в очереди, а в базе данных, так что удалить запись после добавления не получится.

У вершины A родитель B. У вершины B родитель C. У вершины С родитель A. Дальше пошло по кругу... Другое дело, что если начинаешь с корня, на эту ветку просто никак не попадёшь. Но часто приходится начинать не с корня, а с некоторой конкретной записи, чтобы восстановить дерево "снизу" (пример Tree.zip у меня на сайте).

Решение простое - проверять каждую запись на нулевой идентификатор. Или в блоке периодических проверок БД или непосредственно при обходе дерева. Я у себя использовал сразу оба эти варианта.

Я просто перед добавлением в стек проверяю запись на наличие в выходном списке. Если она там есть, то в стек не добавляется .

А вообще-то, разговор беспредметный.... Пусть цветут сто цветов, пусть сосуществуют сто школ (Мао цзе-Дун).

---------------------------------------
C уважением,
Юрий Философов

я использую следующий механизм создания деревьев приёмная структура что то типа:

Код: Выделить всё

myTreeQueue    QUEUE,TYPE
 LIKE(TreeFile)
Q                     &myTreeQueue
 END

рекурсивно раскручиваю уровни, потом строю линейную очередь для LIST

- легко сортировать отдельно по подуровням
- лёгкая навигация по подуровням (меняем вершину)
- динамическая подгрузка подуровней при раскрытии

Andrew Myalin
andrew@arsis.ru
http://mavcla.arsis.ru (MAV Direct ODBC)
ICQ: 10659412
Yahoo group: clarion@yahoogroups.com

У меня на такую конструкцию компилятор ругается: Illegal parametr for LIKE,
а такую пропускает:

Код: Выделить всё

myTreeQueue    QUEUE,TYPE
  LIKE(TreeFile:RECORD)
Q                     &myTreeQueue
END

В чем может быть дело ?

С уважением, Марина.

да всё правильно, в моём случае, приёмные буфера не файловые структуры, а группы.

Andrew Myalin

А как Вы определяете, что в группе типа

Код: Выделить всё

MyRec    GROUP
Id            LONG
sTS         STRING(8)
sTsGr      GROUP,OVER(sTS)
D             DATE
T             TIME
          END
NAME    CSTRING(22)
    END

группа sTsGr имеет атрибут OVER и в нее входят два поля ?
Еще знать бы OVER на какое поле ? Но это уже не обязательно.

С уважением, Марина.

Написал: ClaList(2)

А какое это имеет значение к обсуждаемой теме?
Ну, а если конкретно, то OVER-аттрибут поля определяется довольно легко - по перекрытию адресов этого поля и любого из предыдущих полей группы.

=============================
С уважением, Олег А. Руденко.
Oleg_Rudenko@mail.ru
Oleg_Rudenko@mail333.com
Библиотека DynaLib
http://dynalib.narod.ru

Спасибо, Олег. Я уже покопалась в архиве и в папочке "Руденко" нашла Ваш ответ на этот вопрос.

А какое это имеет значение к обсуждаемой теме?

Просто я испоьзую FILE:Record, а тут подумала, что GROUP иногда была бы "экономней"

С уважением, Марина.

Спасибо всем. Всё-таки удалось "убедить" кларион строить дерево относительно шустро - меньше секунды для ABC.
Итого, меньше 3-х секунд вместе с чтением и разбором.
Уже приятно.

Хотя, наверное можно и ещё быстрее...

Сергей
Написал: ClaList(2)

forum.clarionlife.net

Алгоритмы построения TREE