Предложите альтернативный алгоритм

[vlad]

В продолжении темы о частных велосипедах против стандартных решений.

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

Стандартное решение: строим дерево, потом бежим по нему и заносим ссылки на все узлы в отсортированную последовательность. Если очередной узел подобен найденному - связываем узлы.

Я подумал, что может я мыслю слишком шаблонно и есть более эффективный велосипед...

[Peter Almazov]

Сразу возникает 2 вопроса.
1. Почему это не делается сразу в процессе построения дерева.
2. Почему "в отсортированную последовательность", а не в хеш-таблицу.

[vlad]

Сразу возникает 2 вопроса.
1. Почему это не делается сразу в процессе построения дерева.

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

2. Почему "в отсортированную последовательность", а не в хеш-таблицу.

А есть принципиальная разница?

[Peter Almazov]

А есть принципиальная разница?

Хеш быстрее работает.

[valexey]

А есть принципиальная разница?

Хеш быстрее работает.

Не всегда.

[vlad]

А есть принципиальная разница?

Хеш быстрее работает.

Быстрее когда? При построении (вставке), при поиске? Например, применительно к данной задаче - вставок будет много (все дерево, которое достаточно большое > 1000 узлов), одинаковых элементов мало, поиска много (опять же - на каждый элемент).

[DIzer]

1.) А какое дерево создается?
2.)Правильно ли я понял, что структура  произвольного узла  может изменяться?

[DIzer]

И, наконец, какие операции вы определяете над деревом

[vlad]

1.) А какое дерево создается?

В смысле? Обычное дерево. С произвольным количеством листьев/веток в узле.

2.)Правильно ли я понял, что структура  произвольного узла  может изменяться?

Да, узел можно сделать каким угодно.

[vlad]

И, наконец, какие операции вы определяете над деревом

После построения? Оно обходится и по нему строится еще одно дерево С игнорированием некоторых узлов (оказавшихся ненужными). И подсчетом статистики для подобных узлов (для такого узла есть столько-то подобных и сума их атрибутов вот такая). Да, потом уже в линейном виде все это будет еще раз сортироваться уже согласно статистике

[DIzer]

После построения? Оно обходится и по нему строится еще одно дерево С игнорированием некоторых узлов (оказавшихся ненужными). И подсчетом статистики для подобных узлов (для такого узла есть столько-то подобных и сума их атрибутов вот такая). Да, потом уже в линейном виде все это будет еще раз сортироваться уже согласно статистике

Правильно ли я понимаю задачу
1. есть дерево  - набор узлов , с количеством ребер m  принадлежащем интервалу 1..M
2. каждый узел МОЖЕТ содержать вариативную составляющую (набор полей) по которой ведется поиска.
Требуется оптимизировать поиск?

[DIzer]

Если это так, то целесообразно помещать  (при создании дерева) узел в  структуру с доступом O(1) - массив, хэш таблица
Если дополнительно известно, что поиск будет вестись СТРОГО по одному ключу - рассмотреть возможность использования BST- сбалансированный вариант,  (либо красно черный)  либо запихивать отсортированные данные

[DIzer]

Вообще говоря общее решение нам дает гаранированное время поиска O(n) - так что можно использовать в качестве контейнера обычный односвязанный список и не заморачиваться.
Частные решения могут дать поиск O( log2(n))

[DIzer]

Таким образом в стандартном случае наша система описывается :

TYPE


TNodeDesc=RECORD (* описание узла*)
.....
END;

PListNnode = POINTER TO TLISTNODE;

TLISTNODE = RECORD
TreeNode:TNodeDesc;
Next: PListNnode;
END:

(*Ключ поиска*)
TSearchKey =RECORD
....
END;

(*Поиск*)
PROCEDURE SearchList(aList :PListNnode, Akey:TSearchKey ):PListNnode;

[Губанов Сергей Юрьевич]

А имеет ли значение тот факт, что где-то там дерево? Может быть проще забыть о нём и сформулировать задачу иначе: Есть множество из N>1000 объектов, требуется найти все подобные (функция вычисляющая подобие двух объектов дана). Правда в таком общем виде потребуется полный перебор O(N^2), что для N>1000 считается неприемлемым. Чтобы ускорить вычисления надо знать детали функции подобия. Если она допускает сортировку, то да, сортировать надо, в отсортированном виде все подобные окажутся рядышком.