Автор Тема: Предложите альтернативный алгоритм  (Прочитано 9443 раз)

DIzer

  • Гость
Re: Предложите альтернативный алгоритм
« Ответ #15 : Февраль 27, 2012, 08:56:57 pm »
А имеет ли значение тот факт, что где-то там дерево? Может быть проще забыть о нём и сформулировать задачу иначе: Есть множество из N>1000 объектов, требуется найти все подобные (функция вычисляющая подобие двух объектов дана). Правда в таком общем виде потребуется полный перебор O(N^2), что для N>1000 считается неприемлемым. Чтобы ускорить вычисления надо знать детали функции подобия. Если она допускает сортировку, то да, сортировать надо, в отсортированном виде все подобные окажутся рядышком.
так так и ищется только поиск линейный за O(n). Для улучшения необходимо боле четко понимать задачу...

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Предложите альтернативный алгоритм
« Ответ #16 : Февраль 27, 2012, 09:20:19 pm »
Если функция подобия двух объектов сводится к сравниванию ключей, то лучше не сортировать, а пихать в хэштаблицу списков (в списках окажутся подобные), это О(1), а всего значит O(N).

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

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Предложите альтернативный алгоритм
« Ответ #17 : Февраль 28, 2012, 12:30:20 am »
Кстати, физический смысл этой задачи случайно не профилирование вызовов процедур?

Да, угадал, это профилирование! :) Спасибо всем за предложения, сейчас на другую задачу ушел, потом напишу чем все кончилось.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Предложите альтернативный алгоритм
« Ответ #18 : Февраль 29, 2012, 04:43:25 am »
Да, угадал, это профилирование! :) Спасибо всем за предложения, сейчас на другую задачу ушел, потом напишу чем все кончилось.

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

P.S. Чувствую следующим будет дебаггер... ;)

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Предложите альтернативный алгоритм
« Ответ #19 : Февраль 29, 2012, 05:52:20 am »
Я тоже на работе программу оборудовал (неотключаемым!!!) профилировщиком. Делая проход по всем объектам (отнаследованным от определённого класса) вычисляю их текущее количество. Измеряется скорость их создания и убиения текущая (за последние N-минут) и средняя-глобальная. По объектам сообщений замеряется какой тип сообщения к какому типу объектов был отправлен, сколько раз, время затраченное на обработку сообщения (с дисперсией), тоже текущее и средне-глобальное. Для логгера, если он активен, считается сколько сообщений и какого размера записывается в лог, с какой скоростью и т.п. Встроил паузомер сборщика мусора, он измеряет как часто запускается сборка мусора, средняя и максимальная продолжительность паузы текущая и средне-глобальная, сколько памяти зажрано. Для соединений с СУБД: как часто, в какие таблицы, какие запросы и т.п. Ну и ещё много чего другого... Вся эта информация (по умолчанию раз в минуту) сбрасывается на диск в текстовый файл. Помогает.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Предложите альтернативный алгоритм
« Ответ #20 : Февраль 29, 2012, 05:58:10 am »
Я тоже на работе программу оборудовал (неотключаемым!!!) профилировщиком.
Это про что - C# или BB?

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

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Предложите альтернативный алгоритм
« Ответ #21 : Февраль 29, 2012, 06:13:33 am »
Это про что - C# или BB?
На работе C#.