Oberon space
General Category => Общий раздел => Тема начата: vlad от Февраль 27, 2012, 01:52:27 pm
-
В продолжении темы о частных велосипедах против стандартных решений.
Строится дерево. У него встречаются подобные узлы (с одинаковым атрибутом, например, именем). Эти узлы надо связать между собой.
Стандартное решение: строим дерево, потом бежим по нему и заносим ссылки на все узлы в отсортированную последовательность. Если очередной узел подобен найденному - связываем узлы.
Я подумал, что может я мыслю слишком шаблонно и есть более эффективный велосипед... :)
-
Сразу возникает 2 вопроса.
1. Почему это не делается сразу в процессе построения дерева.
2. Почему "в отсортированную последовательность", а не в хеш-таблицу.
-
Сразу возникает 2 вопроса.
1. Почему это не делается сразу в процессе построения дерева.
Дерево строится как "побочный эффект" в процессе некоторого вычисления (через механизм коллбэков). Специфика такова, что чем меньше времени будет потрачено в коллбэках - тем лучше (иначе это время придется учитывать, что создаст дополнительную сложность). Т.е., все дополнительные действия, не связанные напрямую с постройкой дерева лучше отложить на потом. Но можно попробовать игнорировать это ограничение, если оно сильно мешает хорошему (простому и быстрому) решению.
2. Почему "в отсортированную последовательность", а не в хеш-таблицу.
А есть принципиальная разница?
-
А есть принципиальная разница?
Хеш быстрее работает.
-
А есть принципиальная разница?
Хеш быстрее работает.
Не всегда.
-
А есть принципиальная разница?
Хеш быстрее работает.
Быстрее когда? При построении (вставке), при поиске? Например, применительно к данной задаче - вставок будет много (все дерево, которое достаточно большое > 1000 узлов), одинаковых элементов мало, поиска много (опять же - на каждый элемент).
-
1.) А какое дерево создается?
2.)Правильно ли я понял, что структура произвольного узла может изменяться?
-
И, наконец, какие операции вы определяете над деревом
-
1.) А какое дерево создается?
В смысле? Обычное дерево. С произвольным количеством листьев/веток в узле.
2.)Правильно ли я понял, что структура произвольного узла может изменяться?
Да, узел можно сделать каким угодно.
-
И, наконец, какие операции вы определяете над деревом
После построения? Оно обходится и по нему строится еще одно дерево :) С игнорированием некоторых узлов (оказавшихся ненужными). И подсчетом статистики для подобных узлов (для такого узла есть столько-то подобных и сума их атрибутов вот такая). Да, потом уже в линейном виде все это будет еще раз сортироваться уже согласно статистике :)
-
После построения? Оно обходится и по нему строится еще одно дерево :) С игнорированием некоторых узлов (оказавшихся ненужными). И подсчетом статистики для подобных узлов (для такого узла есть столько-то подобных и сума их атрибутов вот такая). Да, потом уже в линейном виде все это будет еще раз сортироваться уже согласно статистике :)
Правильно ли я понимаю задачу
1. есть дерево - набор узлов , с количеством ребер m принадлежащем интервалу 1..M
2. каждый узел МОЖЕТ содержать вариативную составляющую (набор полей) по которой ведется поиска.
Требуется оптимизировать поиск?
-
Если это так, то целесообразно помещать (при создании дерева) узел в структуру с доступом O(1) - массив, хэш таблица
Если дополнительно известно, что поиск будет вестись СТРОГО по одному ключу - рассмотреть возможность использования BST- сбалансированный вариант, (либо красно черный) либо запихивать отсортированные данные
-
Вообще говоря общее решение нам дает гаранированное время поиска O(n) - так что можно использовать в качестве контейнера обычный односвязанный список и не заморачиваться.
Частные решения могут дать поиск O( log2(n))
-
Таким образом в стандартном случае наша система описывается :
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 считается неприемлемым. Чтобы ускорить вычисления надо знать детали функции подобия. Если она допускает сортировку, то да, сортировать надо, в отсортированном виде все подобные окажутся рядышком.
-
А имеет ли значение тот факт, что где-то там дерево? Может быть проще забыть о нём и сформулировать задачу иначе: Есть множество из N>1000 объектов, требуется найти все подобные (функция вычисляющая подобие двух объектов дана). Правда в таком общем виде потребуется полный перебор O(N^2), что для N>1000 считается неприемлемым. Чтобы ускорить вычисления надо знать детали функции подобия. Если она допускает сортировку, то да, сортировать надо, в отсортированном виде все подобные окажутся рядышком.
так так и ищется только поиск линейный за O(n). Для улучшения необходимо боле четко понимать задачу...
-
Если функция подобия двух объектов сводится к сравниванию ключей, то лучше не сортировать, а пихать в хэштаблицу списков (в списках окажутся подобные), это О(1), а всего значит O(N).
Кстати, физический смысл этой задачи случайно не профилирование вызовов процедур? Подобные узлы - это когда случился рекурсивный вызов процедуры? Ключ - сигнатура процедуры. Тут точно пихай узлы по сигнатуре в хэштаблицу списков прямо "на лету". Потом пройдёшься по получившимся спискам и соединишь подобные узлы. А ещё круче если хэштаблицу списков узлов реализовать врукопашную интрузивно на самих узлах, тогда всё соберётся вообще за один проход.
-
Кстати, физический смысл этой задачи случайно не профилирование вызовов процедур?
Да, угадал, это профилирование! :) Спасибо всем за предложения, сейчас на другую задачу ушел, потом напишу чем все кончилось.
-
Да, угадал, это профилирование! :) Спасибо всем за предложения, сейчас на другую задачу ушел, потом напишу чем все кончилось.
В довесок к профайлеру (незаконченному) сделал анализатор объектов в памяти (лики надо как-то ловить). Заюзал много всяких векторов, ассоциативных контейнеров, уникальных списков и размотал рекурсию в цикл :) Расписывать подробности лень, потому что борьба была главным образом с долбанутым API, а не с анализом графа объектов (это намного интереснее, но руки, видимо, не скоро дойдут). Если кто в курсе готовой тулзы для анализа графов - подскажите плз.
P.S. Чувствую следующим будет дебаггер... ;)
-
Я тоже на работе программу оборудовал (неотключаемым!!!) профилировщиком. Делая проход по всем объектам (отнаследованным от определённого класса) вычисляю их текущее количество. Измеряется скорость их создания и убиения текущая (за последние N-минут) и средняя-глобальная. По объектам сообщений замеряется какой тип сообщения к какому типу объектов был отправлен, сколько раз, время затраченное на обработку сообщения (с дисперсией), тоже текущее и средне-глобальное. Для логгера, если он активен, считается сколько сообщений и какого размера записывается в лог, с какой скоростью и т.п. Встроил паузомер сборщика мусора, он измеряет как часто запускается сборка мусора, средняя и максимальная продолжительность паузы текущая и средне-глобальная, сколько памяти зажрано. Для соединений с СУБД: как часто, в какие таблицы, какие запросы и т.п. Ну и ещё много чего другого... Вся эта информация (по умолчанию раз в минуту) сбрасывается на диск в текстовый файл. Помогает.
-
Я тоже на работе программу оборудовал (неотключаемым!!!) профилировщиком.
Это про что - C# или BB?
-
Это про что - C# или BB?
На работе C#.