Оптимизация с деревьями

[Utkin]

Суть: Имеется структура данных в ввиде набора узлов деревьев. Все узлы (то есть узлы различных деревьев) хранятся в одном обычном массиве (делается из соображений скорости и кроссплатформенности). Доступ к элементу дерева на данный момент осуществляется через полный сцепленный ключ. Примером может служить система каталогов на диске. Есть вот какой-нибудь сцепленный ключ - путь d:\users\1\desktop
Так вот чтобы осуществить любую операцию (например, копирование одного узла в другой) необходимо вычислить индекс искомого узла (desktop) в общем массиве всех узлов. Схема поиска в общем пока такова - ищем d:\ (а в результате различных операций он может располагаться где угодно и в начала и в конце массива), затем запрашиваем имена дочерних узлов и уже ищем индекс users (то есть опять перебираем массив) и т.д. в рекурсии. Понятно, что это ни разу не быстро. Например, если организовывать иерархическую базу данных, хранящая реальные данные какой-нибудь отрасли деятельности организации, то такая система всю жизнь будет заниматься вычислением местоположения узлов. Вопрос - как ускорить поиск?

[Аватар]

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

Так уж и всю жизнь. Для этого есть иерархические СУБД.

хранятся в одном обычном массиве

Вспомнился Foxpro и индексные файлы. Там реализовано с помощью B+ деревьев и весьма оптимально. В том числе и вставка. Может в эту сторону копнуть?

[waleri]

Сообщение от Utkin

Вопрос - как ускорить поиск?

Например хранить полный путь для каждого элемента.

Еще кэширование, чтоб искать только в под-пути.

А вообще, если есть индекс по имени и по идентификаторы, то перебор массива будет не таким уж и медленным.

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

[Utkin]

Так уж и всю жизнь. Для этого есть иерархические СУБД.

Я такую и хочу со своими преферансом и поэтессами. Поскольку весь комплекс родить будет сложно, наверно все это будет представлено в виде какой-нибудь БД в FireBird, мне кажется будет эффективное хранилище данных. Но мне надо теперь продумать эффективный способ организации данных.

Например хранить полный путь для каждого элемента.

Много информации и потом в случае перемещения опять изменения вносить... Думал я так, плохо представляю как красиво запилить.

А вообще, если есть индекс по имени и по идентификаторы, то перебор массива будет не таким уж и медленным.

В миллион элементов будет однозначно длинным. Представьте в массиве миллион элементов, длина пути до узла скажем десять узлов. Если элементы раскиданы в массиве равномерно, то примерно нужно перебрать полмиллиона узлов (даже если идентификатор число) на один узел. Того 5 миллионов узлов среднее время и практически 10 миллионов узлов крайний случай. Мне кажется даже на современной тачке это будет не очень быстро.
Я думал над кешем последних использованных элементов (типа запоминать пути и индексы скажем последних 32-х использованных узлов), но не знаю насколько это будет эффективным решением....

[Аватар]

FireBird

Вот неплохая статья по организации иерархии в FireBird http://rxlib.ru/WinLesson/bles3.htm

[evg_m]

Все узлы (то есть узлы различных деревьев) хранятся в одном обычном массиве

Все ячейки(узлы) либо обязаны знать свой полный ключ.
Но уж наверняка они знают свой частичный ключ и знают кто их родитель (имеют прямую ссылку к нему(индекс)).
Либо они всегда могут узнать свой полный ключ без полного перебора массива (просто рекурсивно пройдя по своим ссылкам на родителя).

Опрашиваем ВСЕ ячейки на предмет их ключа и выбираем искомую.
Если при опросе проверять на частичное совпадение то можно будет и не строить полного ключа.
ключ 'с\user\t' не может быть у ячейки с частичным ключом 'f' ('t'<>'f')

нелинейное построение ключей для дочерних узлов <-> линейное построение ключей по родителям.

Каждый элемент(узел) должен уметь проверить на совпадение предоставленный ключ и свой собственный. ну и просить также проверять своего родителя.

[Kostia]

Если я правильно понял, то Closure Table

[Utkin]

Все ячейки(узлы) либо обязаны знать свой полный ключ.
Но уж наверняка они знают свой частичный ключ и знают кто их родитель (имеют прямую ссылку к нему(индекс)).
Либо они всегда могут узнать свой полный ключ без полного перебора массива (просто рекурсивно пройдя по своим ссылкам на родителя).

Ситуация обратная - мне нужно из корня спуститься вниз, а не от конечного элемента вернуться в корень.

Каждый элемент(узел) должен уметь проверить на совпадение предоставленный ключ и свой собственный. ну и просить также проверять своего родителя.

Это не проблема - структуры пассивные данные, не объекты (ну в смысле без методов). Есть один класс, где его полем является массив узлов.

Опрашиваем ВСЕ ячейки на предмет их ключа и выбираем искомую.
Если при опросе проверять на частичное совпадение то можно будет и не строить полного ключа.
ключ 'с\user\t' не может быть у ячейки с частичным ключом 'f' ('t'<>'f')

Узлам известен идентификатор родителя.

[evg_m]

Так вот чтобы осуществить любую операцию (например, копирование одного узла в другой) необходимо вычислить индекс искомого узла (desktop) в общем массиве всех узлов.

Зная ключ надо найти в данном массиве (вычислить индекс) элемент имеющий такой ключ.

Есть два типа поиска:
1. Разбор заданного ключа.
СПУСК от корневого к дочерним (предполагает что родители знают о всех своих детях). это то что вы пытаетесь реализовать.
Но у вас есть проблема: родители на самом деле ничего не знают о своих детях.
2. сравнение ключей
Перебор всех элементов массива и восстановление ключа каждого проверяемого элемента.
подъем от дочернего (проверяемый узел) к родителю.
И сравнение восстановленного ключа с искомым.
Как только успех мы НАШЛИ искомое.

Сравнение слева направо (спуск+разбор)
Сравнение справа налево (подъем+восстановление).

=====================
Найти ключ 'с\user\t'
ищем все элементы c именем 't'
от найденных переходим к родителям, проверяем 'user' и исключаем неудовлетворяющие
продолжаем подъем до исчерпания ключа.

[Utkin]

А, интересная фишка, теперь я понял, какой Вы предлагаете алгорит - от противного . В общем-то интересная идея... Но как всегда есть одно но... Поскольку я предполагал традиционный поиск, то непосредственные имена хранятся у родителей. То есть потомок имеет идентификатор и список идентификаторов и имен потомков. Сам узел имени не имеет, имя находится у родителя. Чуть позже скину структуру узла (дома в свободное время занимаюсь). В принципе это не так уж и сложно реализовать... Надо обдумать.
Есть еще одна идея - что если помимо узла, хранить идентификатор родителя? Тогда наверно отбор по корневому узлу мог бы ускорить работу...