Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Подскажите оптимальный алгоритм составления дерева


Автор: gesper 11.12.2012, 10:25
Если глупый вопрос, не судите строго, программы пишу для собственных нужд, а не по работе, и 5 лет на программиста не учился.

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

-Проект
--
--Завод ОАО Печеньки
----Печеньки круглые
----Печеньки квадратные
-------Печенька 60х40
-------Печенька 80х80 сладкая
и. т.д.

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

Или надо разбивать список на части и в потоки разные запускать?

Автор: Pavia 11.12.2012, 10:45
Нарушены правила построения БД. 
http://ru.wikipedia.org/wiki/Нормальная_форма 

Во-вторых тормозить при 100 не должно.
Вот при 100 000 ещё поверю.

Как решение отсортировать.  Но правильно будет переделать БД.

Автор: gesper 11.12.2012, 11:06
Цитата(Pavia @  11.12.2012,  10:45 Найти цитируемый пост)
Нарушены правила построения БД. 
http://ru.wikipedia.org/wiki/Нормальная_форма 

Во-вторых тормозить при 100 не должно.
Вот при 100 000 ещё поверю.

Как решение отсортировать.  Но правильно будет переделать БД.

1) Если чесно, то что написано в Wiki, это набор умных слов без характеристики что и как выглядеть должно, а главное почему так. Примеров нет, слова на дело перевести сложно очень.

2) Посмотрел сейчас, 150 записей обрабатываются 3 секунды, визуально это долго выглядит, если убрать построение дерева, и просто все под один узел загонять, списком, то обрабатывается в миг, а как начинаешь структурировать по каталогам, то тормоза.
Отказаться от списка общего нельзя, структурировать в дереве данные тоже обязательно нужно.
Ладно, буду искать...

3)Но правильно будет переделать БД.
Это вобще по факту не БД, а Класс языка программирования (ObjectList). От использования БД отказался сразу из-за некоторых особенностей их применения.

Автор: DarkProg 11.12.2012, 11:36
Хм... как бы попроще объяснить. Есть два способа построения дерева - обходом в глубину и в ширину.
В глубину - идём по одной ветке до конца пока не дойдём, в ширину - строим по уровням(сначала 1-й, потом 2-й и т.д.). Что лучше зависит от задачи.
Алгоритмы построения дерева по сути рекурсивные, то что делаете вы будет действительно медленно работать.

Лучше всего нормально организовать систему классов, чтобы можно было как-то строить узлы без проблем, т.е. по сути классы должны отражать дерево. Тогда можно будет делать обход дерева.

P.S. У меня в дереве строится наверное 1000 узлов и где-то около того же компонентов на форме в зависимости от дерева итого 4 секунды на всё про всё уходит со всеми перестройками и алгоритмами вычисления.

Автор: DarkProg 11.12.2012, 11:36
//что за странный дубль затесался

Автор: Pavia 11.12.2012, 12:38
Цитата(gesper @  11.12.2012,  11:06 Найти цитируемый пост)
Это вобще по факту не БД, а Класс языка программирования (ObjectList). От использования БД отказался сразу из-за некоторых особенностей их применения.

Вы отказались не от БД, а от СУБД. И начале городить свою на классах.

Цитата(gesper @  11.12.2012,  11:06 Найти цитируемый пост)
2) Посмотрел сейчас, 150 записей обрабатываются 3 секунды, визуально это долго выглядит, если убрать построение дерева, и просто все под один узел загонять, списком, то обрабатывается в миг, а как начинаешь структурировать по каталогам, то тормоза.Отказаться от списка общего нельзя, структурировать в дереве данные тоже обязательно нужно.Ладно, буду искать...

Об этом и речь. Структур надо было придумывать сразу при конструирование БД.  На данный момент вы решаете проблему структурирования. При этом вы её выполняете каждый раз при загрузке программы. А должны были сделать это один раз при вводе данных в БД.
И более того вы используете довольно не оптимальный способ структурировать. Каждый раз выполняя обход дерева при добавления новой записи. 
Но даже при этом у вас где-то косяк, так как эта операция должна выполняться раз в 100-1000 быстрее. 

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

Цитата

1) Если чесно, то что написано в Wiki, это набор умных слов без характеристики что и как выглядеть должно, а главное почему так. Примеров нет, слова на дело перевести сложно очень.

Просто убрать дублирование данных и убрать лишние связи. Организовать упорядоченные данные для быстрого обращения к ним. 

Автор: gesper 11.12.2012, 12:53
Цитата(DarkProg @  11.12.2012,  11:36 Найти цитируемый пост)
Хм... как бы попроще объяснить. Есть два способа построения дерева - обходом в глубину и в ширину.
В глубину - идём по одной ветке до конца пока не дойдём, в ширину - строим по уровням(сначала 1-й, потом 2-й и т.д.). Что лучше зависит от задачи.
Алгоритмы построения дерева по сути рекурсивные, то что делаете вы будет действительно медленно работать.

Лучше всего нормально организовать систему классов, чтобы можно было как-то строить узлы без проблем, т.е. по сути классы должны отражать дерево. Тогда можно будет делать обход дерева.

P.S. У меня в дереве строится наверное 1000 узлов и где-то около того же компонентов на форме в зависимости от дерева итого 4 секунды на всё про всё уходит со всеми перестройками и алгоритмами вычисления.

Очень понятно обьяснил smile

Цитата(Pavia @  11.12.2012,  12:38 Найти цитируемый пост)
Об этом и речь. Структур надо было придумывать сразу при конструирование БД.  На данный момент вы решаете проблему структурирования. При этом вы её выполняете каждый раз при загрузке программы. А должны были сделать это один раз при вводе данных в БД.
И более того вы используете довольно не оптимальный способ структурировать. Каждый раз выполняя обход дерева при добавления новой записи. 
Но даже при этом у вас где-то косяк, так как эта операция должна выполняться раз в 100-1000 быстрее. 

Я понял. Правда организацией структуры я как раз и занимался, поскольку имеющийся вариант был для меня оптимальным, чтобы программа выполняла расчеты с использованием данных из списка изделий и подбора изделий.  Списком быстрее, чем дерево лопатить с отдельными классами, но вот при создании менеджера управления самой БД, где то ошибся, буду искать.

Pavia, DarkProg, за теорию спасибо smile

Автор: DarkProg 11.12.2012, 19:06
Цитата(gesper @  11.12.2012,  13:53 Найти цитируемый пост)
Pavia, DarkProg, за теорию спасибо  

Не за что, главное чтобы в конечном итоге вышел толк.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)