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

[evg_m]

Поскольку я предполагал традиционный поиск, то непосредственные имена хранятся у родителей.

т.е. каждый узел имеет отдельный массив(список) имен ребенков.
что мешает рядом с именем ребенка хранить и прямой индекс в массиве. (для реализации поиска по спуску).

=============
с\user\t
просматриваем все элементы
переходим к родителям и проверяем ключи ребенков (t) отбираем успешные.
в отобранном переходим к родителям и проверяем (user)
.....

[Utkin]

что мешает рядом с именем ребенка хранить и прямой индекс в массиве. (для реализации поиска по спуску).

Операции удаления и перемещения узлов. Удаление дерева как Вы и сами знаете вещь интересная, учитывая что элементы дерева могут быть разбросаны где угодно по массиву. Потому существует такая заморочка - для юзера символьное имя, для высокоуровневых операций - идентификатор-число, для реализации мы уже вынуждены опускаться на уровень индекса в массиве. Каждая операция атомарна и только в рамках нее вычисляется и используется индекс (это задел на многопотоковую работу с хранилищем узлов). То есть индекс вычисляется и используется максимально кратковременно, получается что в результате возможных преобразований (перемещение, копирование, удаление) узлы могут хаотично плавать в массиве (наиболее вероятна операция смещения индекса на 1 к началу из-за удаления узла), поэтому я предположил (возможно ошибочно), что прямая работа с индексами будет неэффективна. Для однозначной идентификации узла, где бы в массиве он не находился используется числовой идентификатор. То есть я работаю так - сцепленный ключ я преобразовывают в идентификатор и далее уже имеется стандартный набор операций над узлом по его идентификатору. И если индекс узла может меняться независимо от самого узла, идентификатор всегда постоянен и уникален во время всей жизни узла и позволяет гарантированно отличать один узел от другого (символьные имена узлов могут быть неуникальными, например корень-корень-корень-корень-корень-корень2). Отличия имеют только потомки одного и того же узла (включая корневые - все они есть потомки глобального узла, который создается при создании и инициализации массива). Поскольку глобальный узел безымянный (не имеет предка, а как писал ранее имена хранятся у родителей), то юзер напрямую обратиться к нему не может и ничего не подозревая считает прямых потомков глобального узла корневыми.

[evg_m]

Итак основная проблема:
узлы не имеют непосредственной адресации в массиве (будь то адрес ребенка, будь то адрес родителя),
а есть только косвенная адресация (тот самый идентификатор).

И здесь при любом алгоритме поиска по ключу (моем/вашем/...) остается только многократное "сканирование" массива.
Чего собственно и хочется избежать.

Конечно его можно ускорить если...
как-то упорядочить массив по тем самым идентификаторам(м.б. с использованием доп. массива индексов). нечто подобное кажется было в ваших первых постах.
И соответственно использовать алгоритмы для поиска в упорядоченных данных.

Но упорядочивание усложняет схему вставки и удаления, а может и нет если...
Выделять идентификаторы только с возрастанием (писать только в конец массива).
Не проводить уплотнения при удалении (по крайней мере каждый раз).
Но при этом возникают новые проблемы:
-хватит ли идентификаторов;
-хватит ли свободного места.

P.S. использование имен в списке дочерних делает выбор в пользу вашего алгоритма спуска по дереву против моего.
так что остается только оптимизация сканирования массива при использовании косвенной адресации (поиск узла по его идентификатору [не ключу!]).

[Utkin]

Итак основная проблема:
узлы не имеют непосредственной адресации в массиве (будь то адрес ребенка, будь то адрес родителя),
а есть только косвенная адресация (тот самый идентификатор).

Верно. Собственно это и есть узкое место.

И здесь при любом алгоритме поиска по ключу (моем/вашем/...) остается только многократное "сканирование" массива.
Чего собственно и хочется избежать.

Точно

Конечно его можно ускорить если...
как-то упорядочить массив по тем самым идентификаторам(м.б. с использованием доп. массива индексов). нечто подобное кажется было в ваших первых постах.
И соответственно использовать алгоритмы для поиска в упорядоченных данных.

Перемещать узлы в массиве? Некоторые операции будут очень быстрыми, а другие о-о-чень долгими.

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

Не уплотнять не получиться - многократное удаление/добавление узлов приведет к разрастанию массива. Удаление я оптимизировал так - я не перемещаю все узлы, а только последний на место удаляемого. А последний уменьшаю границей динамического массива. В тот момент когда я начал эту тему реализация удаления была как в списке (то есть перемещением узлов).

Но при этом возникают новые проблемы:
-хватит ли идентификаторов;
-хватит ли свободного места.

Идентификаторов хватит, там тоже хитро сделано, удаляемые идентификаторы не теряются, а раздаются снова добавляемым узлам.
Насчет свободного места не знаю.

[waleri]

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

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

миллион элементов это 2 ^ 20, значит максимум на один поиск - 20 сравнение. Если длинна пути 10 элементов, максимум будет 200 обращений к массиву. Если для вас это медленно, ну тогда не знаю. Храните полный путь, тогда на любой поиск будет уходить максимум 20 сравнений на миллион элементов. Кстати, если не использовать именно массив, тогда полный путь не обязательно нужно будет хранить явно - сохраняя указатель на родительский объект его можно будет генерить когда понадобится.

Почему обязательно именно массив? Чем не устраивают деревья? И вообще, почему данные не в базе?

[Utkin]

миллион элементов это 2 ^ 20, значит максимум на один поиск - 20 сравнение.

Подробней с такой арифметикой .

[Аватар]

Видимо речь о двоичном поиске. А сортированностью там пахнет вообще? Да и добавление новых элементов порушит её

[Utkin]

Нет, ничего не сортировано, но препятствий сортировке нет.

[evg_m]

Идентификаторов хватит, там тоже хитро сделано, удаляемые идентификаторы не теряются, а раздаются снова добавляемым узлам.

вот как раз этого и не надо бы.
При таком раскладе при сортировке придется писать в произвольное место (оч. долго!)
Но есть нюанс! раз такой узел был и если мы не сжимали массив (не удаляли физически из массива а только помечали удаление) то это место (с таким идентификаторам) ЕСТЬ и запись уже не в произвольное место а на место удаленного "как бы" элемента.

Да и добавление новых элементов порушит её

для этого и предлагается наложить ограничения на правило выделения новых идентификаторов (НЕ нарушать упорядоченность данных).
и также избежать перемещений в массиве.
1.добавление в конец массива с новым идентификатором заведомо большим всех предыдущих.
2.замена физического сжатия массива введением логического флага "исключен".
3.замена отмеченных удаленными с таким же идентификатором.

[Utkin]

1.добавление в конец массива с новым идентификатором заведомо большим всех предыдущих.
2.замена физического сжатия массива введением логического флага "исключен".
3.замена отмеченных удаленными с таким же идентификатором.

В результате массив будет разрастаться и никогда не будет уменьшаться, я правильно понял? То есть если после миллиона узлов потребуется их удаление, массив все равно будет содержать миллион "мертвых" узлов? Чего то мне это не нравится.