Оптимизация доступа к данным в деревьях

[Utkin]

Итак, есть дерево строк (по предыдущим темам должно быть понятно). Ну например:
Планета
...Континенты
......Азия
......Европа
.........Москва
......Южная Америка
......Северная Америка
......Австралия
...Океаны
......Тихий океан
......Атлантический океан
......Индийский океан

Все узлы физически размещены в динамическом массиве. Для поиска узлов используется идентификатор (так как элементы могут удаляться идентификатор узла и его индекс в массиве это разные вещи). Суть проблемы ранее уже озвучивали, но мне не когда было ранее обращать на это внимание. Теперь же вот например я хочу добавить Москве в угоду админу вон Химки. Соответственно рекурсивно - нужно преобразовать строковое имя в идентификатор, а по нему в индекс. Все это делается пока что простым перебором. Проблема в том что сразу индекс элемента массива получить нельзя, так как имена у различных ветвей на разных уровнях могут повторяться. То есть нужно строить всю цепочку последовательно: Планета-Континенты-Европа-Москва. То есть я должен как минимум 4 раза перебирать массив, а если Москву добавляли последней, то как минимум один раз полностью пройти его.
Вопрос как ускорить процесс? Мне нужно быстро получить идентификатор или индекс для элемента Москва. Пока ничего не придумал, только сделать по уровням привязку имен/идентификаторов (помним, что элементы в массиве могут менять местоположение, потому сразу индексы непонятно как прикрутить). Ну то есть где-то хранить Планета(0 - идентификатор, 0 - начальный уровень) и т.д. В пути уровень определить уже можно и так ускорить построение пути до нужного идентификатора, а там уже полным перебором в массиве найти нужный индекс.

[Аватар]

А узлы просто строки или объекты? Если объекты, то почему бы не искать по ссылкам на дочерние? Ссылочки конечно в объект придется встраивать

[Pavia]

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

Использовать поиск в дереве, а не в линейном массиве.

а если Москву добавляли последней, то как минимум один раз полностью пройти его.

Кешируй последний запрос. Хранишь последний индекс выдачи.
Если он совпадает с подзапросом из нового запроса, то поиск начинай от него.

Индексировать надо то по чему у вас чаще идут запросы.

А вообще вам надо начинать с архитектуры. Опишите данные их объемы. Напишите какой вид операций чаще используется: вставка, удаление или поиск. Выберете из сходя из этого нужную коллекцию(динамическую структуру).
Для оптимизации используйте индексы и кеши, которые должны ускорить работу выбранной коллекции данных под конкретные разновидности запросов.
И помните золотое правило программиста: выигрываешь в скорости проигрываешь в памяти.

[Utkin]

А узлы просто строки или объекты?

Это записи. Они хранят информацию о родителе и дочерних узлах. Но такая структура при поиске элементов заставляет рекурсивно для каждого шага перебирать массив.

Кешируй последний запрос. Хранишь последний индекс выдачи.

А если предпоследний? Это нельзя предсказать заранее.

Индексировать надо то по чему у вас чаще идут запросы.

К корневому узлу. Его индекс я и так знаю.

Опишите данные их объемы.

Объемы неизвестны как выглядит написал в пером посте.

// Описание структуры узла
type
    TSNode = record

           Name: String;             // Имя узла
           Parent: Integer;          // Индекс родителя
           Value: String;            // Строковое значение узла
           Childs: TIntList;         // Индексы дочерних узлов
           ID: Integer;              // Собственный идентификатор узла
    end;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

В хранилище всех узлов/деревьев есть такая беда:

          // Поля класса
          Nodes: Array of TSNode;                                                               // Набор узлов
          IdFree: Integer;                                                                      // Свободный идентификатор
          DeletedId: TIntList;                                                                  // Список удаленных

Напишите какой вид операций чаще используется: вставка, удаление или поиск.

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

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

Вот про это и тема. Представьте что в том примере карта городов всего мира. Поиск Москвы в таком массиве элементов займет ого-го сколько времени, так как операция рекурсивна - алгоритм спускается по дереву вниз и каждый узел в массиве ищется заново. В идеально лажовом варианте, время поиска займет примерно факториал от числа элементов. Мне нужно это ускорить. Потому что даже если среднее время поиска будет факториал от половины элементов - это все равно много. Тут для 100 элементов вырисовывается степень в 50, а мне это не нравится.

И помните золотое правило программиста: выигрываешь в скорости проигрываешь в памяти.

Пофиг. Сейчас критична именно скорость, поскольку вся суть вычислительных процессов будет замешана на поиске одно-двух элементов в дереве и работе с ними. Так вот и получается что поиск элемента значительно превосходит саму операцию. Мне это не нравится и чувствуется отсутствие гармонии в жизни.

[Аватар]

А чего на родителя и детей индексы, а не Pointer? Тогда положение в массиве не важно будет. Да и сам массив не очень актуален.

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

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

[Utkin]

Тогда положение в массиве не важно будет.

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

Москву искать не нужно, она уже есть в родителе, а указатель на Австралию задать

А родитель где? Его нужно найти сначала. А чтобы найти родителя нужно найти родителя родителя. Это как:

Авраам родил Исаака; Исаак родил Иакова; Иаков родил Иуду и братьев его;
Иуда родил Фареса и Зару от Фамари; Фарес родил Есрома; Есром родил Арама;

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

По другому - искать перебором по дереву

Вот сейчас так и ищется. Берется корневой узел Планета, в ней ищется Континенты. Потому что юзер мог ошибиться и написать например Материки, а это лажа. Поэтому мы сначала должны убедиться что на планете вообще есть континенты. Потом среди названий континентов ищется Европа по той же схеме - мы должны быть уверены, что на нашей планете есть Европа - структура динамическая и сегодня Европа на карте есть, а завтра нету - кто знает? И так далее. Все это оборачивается длительными забегами на дальние дистанции по массиву узлов. Первый раз найди им Европу, второй раз найди Австралию. В следующей операции могут ведь Токио добавить - опять перебор, чтобы удостовериться что Азия вообще есть на планете. А представьте потом раз и стерли Европу - это опять каскад событий.

[Pavia]

Utkin
Вам надо посмотреть на проблему глобально. Вы сейчас ищете локальное решение. Это не даст вам решения, будет как в анекдоте:
Хвост поднял - нос увяз.
Нос поднял - хвост увяз!

А если предпоследний? Это нельзя предсказать заранее.

Можно. Статистика вещь сильная.

Объемы неизвестны как выглядит написал в пером посте.

Так оцените: топонимов у нас в России 10 000 тысяч. 100 стран мира. = 1 милион. По вселенной пусть 2 миллиона.
Т.е. не больше 10 миллионов.

Доступ к элементу. Например хочу Москву в Австралию перенести. Так вот ее сначала нужно найти.

Так поиск или доступ? Если доступ почему тема про поиск?
Зачем вам делать поиск? Кто ищет человек или машина? Если человек ему главное уложиться <1 секунды. Это выполняется в линейном списке при линейном поиске.
А у вас есть дерево вот и делайте обход дерева в глубину или в ширину.
Будет в 1000-1 000 000 быстрее линейного поиска. И тут вы гарантированно уложитесь.

Если поиск это делает машина, то она делает по некоторым входным данным. Вот коллекцию надо подстраивать под структуру этих данных.

Храните полный путь 'Планета.Континенты.Азия.Европа.Мос ква' в линейном отсортированном списке. Можно будет искать бинарным поиском.

[Pavia]

А родитель где? Его нужно найти сначала. А чтобы найти родителя нужно найти родителя родителя. Это как:

Выкиньте все и сделайте по нормальному. Если у вас доступ происходит чаще всего надо хранить не идентификатор, а индекс от массива.
И будет ваша операция O(1)

[Аватар]

Так и я к тому - вместо не понятных индексов родителя и детей их адреса. Я об этом

type PMyRecord = ^TMyRecord;
     TMyRecord = record
       Text: String;
       Parent: PMyRecord;
       Childrens: array of PMyRecord;
     end;

[Utkin]

Так оцените: топонимов у нас в России 10 000 тысяч. 100 стран мира. = 1 милион. По вселенной пусть 2 миллиона.
Т.е. не больше 10 миллионов.

Пусть будет от нуля до 10 лямов.

Так поиск или доступ? Если доступ почему тема про поиск?

В данном случае это одно и тоже.

Зачем вам делать поиск? Кто ищет человек или машина?

Ищет машина. Но по указке человека.

А у вас есть дерево вот и делайте обход дерева в глубину или в ширину.

Да блин это и есть рекурсия типичная. То есть медленно.

Если поиск это делает машина, то она делает по некоторым входным данным. Вот коллекцию надо подстраивать под структуру этих данных.

Я привел образец. Там может быть все что угодно - генеалогическое дерево, информационная система, периодическая таблица Менделеева. Там может быть многомерный массив. Куб данных например. Вот и подстройте попробуйте.

Если у вас доступ происходит чаще всего надо хранить не идентификатор, а индекс от массива.

Я уже писал про удаление! Удалили элемент из середины массива и? Все индексы съехали к чертям собачим . Причем не линейно, так как возможны все операции - перемещение одной ветви в другую, удаление узла (а если он имеет дочерние то и всю ветвь) и т.д. В результате Вам нужно будет удалить по массиву там и сям кучу элементов, какие и как неизвестно. Ну и как Вам просто индексы помогут? Вы как перемещать например по индексам будете? Физически элементы в массиве перестраивать?

И будет ваша операция O(1)

В дереве? Ага, размечтались.

вместо не понятных индексов родителя и детей их адреса.

Не индексов, а идентификаторов.

Я об этом

Проблема осталась. Попробуйте Вашими структурами переместить Москву в Австралию. Вы просто смотрите на другом уровне абстракции, но алгоритм реализуется для дерева - стало быть не меняет своей сути и сложности процесса. А именно - Вам тоже надо доползти до Европы. Единственно, Вы избавились от идентификатора, который я ввел искусственно. Это несомненно плюс.
Я вот Вам чего предлагаю - Вы вот то что все мне предлагаете попробуйте пошагово выполнить сами. Операция же проста - переместить Москву из Европы в Австралию. Просто чтобы понять проблему изнутри, я может просто объяснить не могу правильно.
Вот как Вы будете перемещать Москву?