Реклама i
Стань нашим партнером - зарабатывай с нами!
| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Оптимизация обработки большого числа элементов

Оптимизация обработки большого числа элементов

Ответ
Поиск в этой теме
Непрочитано 15.09.2013, 04:25
Оптимизация обработки большого числа элементов
АлексЮстасу
 
топограф, технолог
 
Москва
Регистрация: 24.05.2009
Сообщений: 3,030

Наверное, есть отработанные и даже общепризнанные способы оптимизировать обработку в программах большого числа элементов dwg-файлов?
Я имею в виду программы, которые решают задачи вроде: найти все пересечения или найти все не пересекающееся, найти все, попадающее в контур или вне его, создать все возможные замкнутые контуры или т.п.
И имею в виду не использование чисто программных способов, а на уровне алгоритмов.
Может быть опытные поделятся, если не оч. большой секрет, конечно
Это нужно мне для общения с моим программистом, а может пригодиться начинающим программистом вообще.
Я сам не программист, но постараюсь в целом понять ответы, да и поспрашиваю, если что, у разбирающихся.

Как непосвещенный, я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления, т.е. их взаимные связи (соединение, наложение, пересечение и т.п.) никак не описаны, и их взаимное положение никак не структурировано, не описано. Это правильно? И поэтому, если действовать в лоб, в подобных программах приходится определять отношение всего со всем, и, возможно, не один раз?
Если же как-то ловко описать взаимное положение и/или взаимные связи элементов, то можно будет анализировать не все элементы, а только взаимно связанные или указанным образом расположенные. Что в теории скажется на скорости работы.

И подвопрос: для файлов примерно какого размера (+-полмегабайта) или какого числа элементов (+-1000), или числа вершин элементов (+-1000) подобные ухищрения имеют смысл на не очень мощных и на хороших компьютерах? Эмпирически-экспертно, конечно.
Просмотров: 46083
 
Непрочитано 15.09.2013, 18:49
#21
hwd

C, C++, C#
 
Регистрация: 07.10.2009
С-Пб.
Сообщений: 2,762
Отправить сообщение для hwd с помощью Skype™


Цитата:
Сообщение от АлексЮстасу Посмотреть сообщение
Это поможет программе в целом, но это же не оптимизация определения взаимного положения и отношений элементов друг к другу?
Это, как минимум, формирует наборы данных в удобной вам форме для их дальнейшей обработки в коде вашего алгоритма.
__________________
Надеюсь, ты не социальный овощ? Это определяется делами! :welcome:
hwd вне форума  
 
Автор темы   Непрочитано 15.09.2013, 19:33
#22
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от gomer Посмотреть сообщение
так вы давайте задачу и обсудим ее, а так все как-то абстрактно...
Конкретная задача - это же и будет абстрактно.
Чем не задачи, которые я привел в первом сообщении и в "т.п."? Мы сейчас пишем почти одновременно примерно семь подобных программ, и во всех делается фактически одно - многократный перебор всех элементов с установлением их взаимного положения, отношений и связей. И такого же рода программ придется писать еще несколько и в ближайшее время, и, похоже, позже.
Цитата:
Сообщение от hwd Посмотреть сообщение
Это, как минимум, формирует наборы данных в удобной вам форме для их дальнейшей обработки в коде вашего алгоритма.
Оптимизирует ли это количество обрабатываемых в каждый момент элементов?
Вероятно, просмотр всех элементов неизбежен, и в этом Ваше решение может быть очень полезным. Но это только подход к задаче. Как бы в процессе этого просмотра элементов создать такое описание их положения и формы, чтобы при последующем анализе просматривать уже не все, а в основном потенциально необходимые элементы?
АлексЮстасу вне форума  
 
Непрочитано 15.09.2013, 19:44
#23
hwd

C, C++, C#
 
Регистрация: 07.10.2009
С-Пб.
Сообщений: 2,762
Отправить сообщение для hwd с помощью Skype™


Цитата:
Сообщение от АлексЮстасу Посмотреть сообщение
Оптимизирует ли это количество обрабатываемых в каждый момент элементов?
Вероятно, просмотр всех элементов неизбежен, и в этом Ваше решение может быть очень полезным. Но это только подход к задаче. Как бы в процессе этого просмотра элементов создать такое описание их положения и формы, чтобы при последующем анализе просматривать уже не все, а в основном потенциально необходимые элементы?
Возможность оптимизации набора и избежание лишних просмотров конечно же присутствуют (в этом-то и заключается основная идея). Чтобы ответить на эти вопросы более конкретно, мне нужно видеть код, к которому это нужно прикрутить.
__________________
Надеюсь, ты не социальный овощ? Это определяется делами! :welcome:
hwd вне форума  
 
Непрочитано 15.09.2013, 19:49
#24
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


>>Как непосвещенный, я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е. их взаимные связи (соединение, наложение, пересечение и т.п.) никак не описаны, и их взаимное положение никак не структурировано, не описано. Это правильно?
Нет, не правильно. При обработке примитивов автокад вовсю использует пространственное разбиение
>>для файлов примерно какого размера (+-полмегабайта) или какого числа элементов (+-1000), или числа вершин элементов (+-1000) подобные ухищрения имеют смысл на не очень мощных и на хороших компьютерах? Эмпирически-экспертно, конечно.
Всякого рода "ухищрения" имеют смысл всегда, иначе программа будет тормозить на любом компьютере
zamtmn вне форума  
 
Автор темы   Непрочитано 15.09.2013, 20:42
#25
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от hwd Посмотреть сообщение
Возможность оптимизации набора и избежание лишних просмотров конечно же присутствуют (в этом-то и заключается основная идея). Чтобы ответить на эти вопросы более конкретно, мне нужно видеть код, к которому это нужно прикрутить.
Но я не вижу в Вашем описании упоминания о геометрической оптимизации. Если она есть, то опишите, плз, эту часть Вашего алгоритма. По возможности общечеловеческими словами.
Цитата:
Сообщение от zamtmn Посмотреть сообщение
При обработке примитивов автокад вовсю использует пространственное разбиение
Можно узнать какое, в чем оно выражается? И как им лучше воспользоваться?
АлексЮстасу вне форума  
 
Непрочитано 15.09.2013, 20:59
#26
hwd

C, C++, C#
 
Регистрация: 07.10.2009
С-Пб.
Сообщений: 2,762
Отправить сообщение для hwd с помощью Skype™


Цитата:
Сообщение от АлексЮстасу Посмотреть сообщение
Но я не вижу в Вашем описании упоминания о геометрической оптимизации.
Похоже мы на разных языках разговариваем... Обозначенный мною выше код позволяет манипулировать данными, имеющими свой ObjectId, создавая наборы элементов, подлежащих обработке и, при необходимости, модифицируя их. Код писался не для некой "геометрическую оптимизации", а для более общих задач. Я не знаю как ещё объяснять - вроде там всё должно быть понятно из кода, т.к. постарался там разжевать всё как можно подробней, насколько это возможно.
__________________
Надеюсь, ты не социальный овощ? Это определяется делами! :welcome:
hwd вне форума  
 
Непрочитано 15.09.2013, 21:15
#27
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


>>Можно узнать какое, в чем оно выражается?
Выражается в скорости работы, недостижимой при подходе "я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е.". Т.е. в dwg файле они так и хранятся (хотя там присутствуют некие SPATIAL_FILTER, SPATIAL_INDEX - не вникал что они в себе несут), но обрабатывается всё это хозяйство явно не "всё по очереди"
>>И как им лучше воспользоваться?
Это вопрос к местным корифеям, какие свои механизмы автокад предоставляет наружу.
В порядке ознакомления что это и зачем лучше заглянуть в википедию и почиать про http://en.wikipedia.org/wiki/K-d_tree и подобные алгоритмы
zamtmn вне форума  
 
Автор темы   Непрочитано 16.09.2013, 00:29
#28
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от hwd Посмотреть сообщение
Похоже мы на разных языках разговариваем... Обозначенный мною выше код позволяет манипулировать данными, имеющими свой ObjectId, создавая наборы элементов, подлежащих обработке и, при необходимости, модифицируя их. Код писался не для некой "геометрическую оптимизации", а для более общих задач. Я не знаю как ещё объяснять - вроде там всё должно быть понятно из кода, т.к. постарался там разжевать всё как можно подробней, насколько это возможно.
Просто я не вижу, где в Вашем способе описано, что он позволит для созданного набора элементов оптимизировать (ускорить, упростить) решение геометрических задач. С помощью чего в нем становится известно, что такую-то полилинию могут, допустим, пересекать такие-то полилинии, а другие можно не рассматривать, что в допустимой близости могут находиться вот эти полилинии, а другие нет и т.д. и т.п.? Хотя бы укажите соответствующие пункты или абзацы в Вашей ссылке.
Цитата:
Сообщение от zamtmn Посмотреть сообщение
Выражается в скорости работы, недостижимой при подходе "я предполагаю, что в dwg-файле элементы хранятся в целом просто в порядке их поступления,т.е.". Т.е. в dwg файле они так и хранятся (хотя там присутствуют некие SPATIAL_FILTER, SPATIAL_INDEX - не вникал что они в себе несут), но обрабатывается всё это хозяйство явно не "всё по очереди"
Т.е. сама фирма некую оптимизацию использует, но какую - неизвестно? И Вы считаете, что в самих dwg файлах есть что-то вроде индексации или т.п., но что именно - тоже неизвестно?
АлексЮстасу вне форума  
 
Непрочитано 16.09.2013, 00:48
#29
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


>>Т.е. сама фирма некую оптимизацию использует, но какую - неизвестно? И Вы считаете, что в самих dwg файлах есть что-то вроде индексации или т.п., но что именно - тоже неизвестно?
Неизвестно мне и вам. Я же говорю, пусть знатоки выскажутся - что на эту тему можно выудить из arx - вполне возможно что ничего, но это не значит что не использует. Говоря про dwg файл я подразумеваю файл лежащий на диске, а не dwg открытый автокадом.
zamtmn вне форума  
 
Автор темы   Непрочитано 16.09.2013, 02:27
#30
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от zamtmn Посмотреть сообщение
Неизвестно мне и вам. Я же говорю, пусть знатоки выскажутся - что на эту тему можно выудить из arx - вполне возможно что ничего, но это не значит что не использует. Говоря про dwg файл я подразумеваю файл лежащий на диске, а не dwg открытый автокадом.
Offtop: В тему наблюдение из жизни: Microstation в среднем работает явно быстрее Автокада. В том числе и с dwg-файлами.
Расколюсь. В пятницу, 13-го, в конце рабочего дня породил некий алгоритмище оптимизации (ну, сами понимаете, что может придумать 13-го в пятницу вечером не программист ). Стеснялся об этом здесь поминать.
Но попробую приложить - для некоего примера того, что я имею в виду.
Вложения
Тип файла: doc Алгоритм_оптимизации_геом_обработки_1.doc (30.0 Кб, 84 просмотров)

Последний раз редактировалось АлексЮстасу, 16.09.2013 в 04:35.
АлексЮстасу вне форума  
 
Непрочитано 16.09.2013, 02:38
#31
trir


 
Регистрация: 18.12.2010
Сообщений: 5,047


Книжки читать видимо не модно, то что вы изобретаете - называется k-d дерево, в книжке Препараты глава 2 Геометрический поиск, 2.3.2. Метод многомерного двоичного дерева (k-D-дерева)
trir вне форума  
 
Автор темы   Непрочитано 16.09.2013, 03:05
#32
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от trir Посмотреть сообщение
Книжки читать видимо не модно, то что вы изобретаете - называется k-d дерево, в книжке Препараты глава 2 Геометрический поиск, 2.3.2. Метод многомерного двоичного дерева (k-D-дерева)
Приведенные Вами книги обязательно передам программисту.
Почему именно этот метод? Чем этот метод лучше других?
Вы полагаете, что этот метод не только лучший, но еще и хорошо реализуется программно?
Вам известны примеры его применения в каких-то программах под Автокад?

Кстати, в #27 zamtmn привел в пример именно K-d_tree.

Последний раз редактировалось АлексЮстасу, 16.09.2013 в 04:39.
АлексЮстасу вне форума  
 
Непрочитано 16.09.2013, 07:31
#33
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


trir
Придумывать, а потом читать книжки реально интересней))

АлексЮстасу
Добавте в алгоритм пару пунктов:
-Лучше ввести древовидную структуру данных, т.к. 1)еще больший профит за счет отбраковки всех дочерних "подпространств" путем отбраковки вышестоящего, 2) реальные а не подготовленные данные наврятли можно вписать в какую либо "сетку" - всегда будут примитивы которые будут всё портить - пересекать границы в которые хорошо вписываются другие примитивы, 3) удобно "ограничить" процесс построения такого дерева количеством примитивов в "листах" и глубиной вложенности
-В случае наличия в данных "длинных" примитивов - например полилиний с большим кол-вом сегментов ваш алгоритм стоит применять и внутри примитивов (т.е. грубо говоря считать полилинию набором отрезков и дуг)

update:
Цитата:
Offtop: В тему наблюдение из жизни: Microstation в среднем работает явно быстрее Автокада. В том числе и с dwg-файлами.
хз, Microstation видел лет 10 назад. В качестве примера программы которяа не использует подобные оптимизации могу привести LibreCAD - он всё обрабатывает "в лоб". Поставте, сравните на большом чертеже.

update2:
когда я вникал в потроха LibreCAD он был еще 1.0, сейчас уже 2.0rc, такчто возможно он уже поумнел и не "в лоб"

Последний раз редактировалось zamtmn, 16.09.2013 в 08:18.
zamtmn вне форума  
 
Непрочитано 16.09.2013, 08:01
#34
gomer

строю, ломаю
 
Регистрация: 03.04.2008
Украина
Сообщений: 5,515


что будет, если после того, как вы посадили дерево, кто-то захочет приклеить еще листик к чертежу? И что, охранять дерево всю жизнь? А если оно разрастется так, что перестанет влезать в ваш кабинет?
gomer вне форума  
 
Непрочитано 16.09.2013, 08:13
#35
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


Если автокад не предоставляет подобных "интерфейсов" то дерево садить придется только перед проведением массивных геометрических вычислений, после рубить на дрова. Хотя уверенн что все элементарные операции (типа поиска пересечений или примитивов в окресности) в автокаде подобным образом и устроены и только ради них такое городить нестоит

Последний раз редактировалось zamtmn, 16.09.2013 в 08:19.
zamtmn вне форума  
 
Автор темы   Непрочитано 16.09.2013, 19:52
#36
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от gomer Посмотреть сообщение
что будет, если после того, как вы посадили дерево, кто-то захочет приклеить еще листик к чертежу? И что, охранять дерево всю жизнь? А если оно разрастется так, что перестанет влезать в ваш кабинет?
Я предложил алгоритм без изысков, во-первых, чтобы в принципе объяснить, что имею в виду, и, во-вторых, мне - непрограммисту - неизвестна трудоемкость операций для Автокада или для программиста. Возможный ассортимент действий тоже неизвестен. Поэтому пытался использовать минимум действий с элементами. Фактически два: определять общие габариты элементов и определять габариты сегментов. Написал, было, создавать при ID элементов для ячеек списки вершин, попадающих в эти ячейки, но убрал. Все потому же - не могу оценить трудоемкость (вредоносность/эффективность).
Т.е. этот алгоритм следует понимать не совсем буквально, а как некий эскиз для предложений.
Алгоритм предназначен для работы самой программы, его описание данных живет только в процессе выполнения программ - и никак не влияет на сами данные, на их структурирование в файле. Поэтому и изменение данных ("приклеивание листьев", веток и пр. к чертежу) не влияет на него.
Цитата:
Сообщение от zamtmn Посмотреть сообщение
-Лучше ввести древовидную структуру данных, т.к. 1)еще больший профит за счет отбраковки всех дочерних "подпространств" путем отбраковки вышестоящего, 2) реальные а не подготовленные данные наврятли можно вписать в какую либо "сетку" - всегда будут примитивы которые будут всё портить - пересекать границы в которые хорошо вписываются другие примитивы, 3) удобно "ограничить" процесс построения такого дерева количеством примитивов в "листах" и глубиной вложенности
-В случае наличия в данных "длинных" примитивов - например полилиний с большим кол-вом сегментов ваш алгоритм стоит применять и внутри примитивов (т.е. грубо говоря считать полилинию набором отрезков и дуг)
Поясните, плз, пункт 2).
Габарит сетки >= габариту файла.
Цитата:
Сообщение от zamtmn Посмотреть сообщение
Если автокад не предоставляет подобных "интерфейсов" то дерево садить придется только перед проведением массивных геометрических вычислений, после рубить на дрова. Хотя уверенн что все элементарные операции (типа поиска пересечений или примитивов в окресности) в автокаде подобным образом и устроены и только ради них такое городить нестоит
Да, оптимизировать имеет смысл только тяжелые задачи и для большого объема данных.
И да, мне уже говорят, что в Автокаде все устроено через такие гланды, что проще прямо перебирать элементы, чем еще и грузить его (и себя) оптимизацией.
АлексЮстасу вне форума  
 
Непрочитано 16.09.2013, 20:34
#37
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


>>Поясните, плз, пункт 2).
Для примера файл из 10 полилиний по 10000 сегментов в каждой. Построение дерева на уровне примитивов в таком случае эффекта иметь не будет. Если же для каждой полилинии выполнить разбиение (отдельно или в общей структуре данных) эффект появится - т.к. перебор 10000 сегментов заменится двоичным поиском.

>>Все потому же - не могу оценить трудоемкость (вредоносность/эффективность).
на коленке написаный алгоритм разбиения на паскале занял ~500 строк. эффект получился значительный - в программе-тормозилке стало возможно вполне комфортно работать. Но были большие сложности подружить его с уже работающими фрагментами.
построение дерева для 21000 примитивов, 500 примитивов в ноде, максимальная глубина берева 16:
Цитата:
Running command:RebuildTree
Rebuild drawing spatial: 0.04 second
Total entities: 21250
Tree depth : 8
построение дерева для 21000 примитивов, 10 примитивов в ноде, максимальная глубина берева 16:
Цитата:
Running command:RebuildTree
Rebuild drawing spatial: 0.07 second
Total entities: 21250
Tree depth : 15
zamtmn вне форума  
 
Автор темы   Непрочитано 16.09.2013, 20:45
#38
АлексЮстасу

топограф, технолог
 
Блог
 
Регистрация: 24.05.2009
Москва
Сообщений: 3,030


Цитата:
Сообщение от zamtmn Посмотреть сообщение
построение дерева для 21000 примитивов, 500 примитивов в ноде, максимальная глубина берева 16
Что такое "примитивы в ноде"?
Можете на пальцах изложить принципы, метод "построения дерева"? Для не математиков в том числе
АлексЮстасу вне форума  
 
Непрочитано 16.09.2013, 21:05
#39
hwd

C, C++, C#
 
Регистрация: 07.10.2009
С-Пб.
Сообщений: 2,762
Отправить сообщение для hwd с помощью Skype™


Цитата:
Сообщение от АлексЮстасу Посмотреть сообщение
Что такое "примитивы в ноде"?
Можете на пальцах изложить принципы, метод "построения дерева"? Для не математиков в том числе
Node (узел). Уже сто раз можно было в интернете самостоятельно найти и прочитать информацию по теме построения деревьев...
__________________
Надеюсь, ты не социальный овощ? Это определяется делами! :welcome:
hwd вне форума  
 
Непрочитано 16.09.2013, 21:19
#40
zamtmn

КИПиА
 
Регистрация: 21.03.2005
Tyumen
Сообщений: 1,352
<phrase 1=


Я не програмист поэтому извиняюсь если путаю термины. Также это всё хозяйство было написано без оглядки на толковые книжки - я их читал когдато давно в детстве.
Нода в моей реализации - ограничивающий объем+плоскость делящая ноду+ссылка на ноду "левее" плоскости+ссылка на ноду "правее" плоскости+список примитивов которые пересекаются плоскостью

1.На вход приходит срисок примитивов+уже посчитаный ограничивающий объем всех примитивов
2.создаем ноду
3.если (примитивов<примитивов в ноде)или(глубина дерева>максимальная глубина берева) то пишем все примитивы в список пересекающихся плоскостью, выходим возвращая созданную ноду
3.выбираем плоскость разбиения (тут я прибумывал всякие хитрые способы, но просто разбивать пополам перпендикулярно самой длинной оси ничють не хуже всяких хитростей)
4.список примитивов делим на 3 списка 1-левее плоскости, 2-правее плоскости, 3-пересекаются плоскостью
5. пишем список 3 в список пересекающихся плоскостью
6. ссылка на ноду "левее" плоскости=рекурсивный вызов п.1 со списком 1 и его ограничивающим объемом
7. ссылка на ноду "правее" плоскости=рекурсивный вызов п.1 со списком 2 и его ограничивающим объемом

на выходе получается рекурсивное дерево ограничивающих объемов с перечнем примитивов в него попавших. разбиение продолжается пока не будет достигнута максимальная глубина или количество примитивов в ноде не будет меньше заданного
Цитата:
Что такое "примитивы в ноде"?
также отдельно обрабатываются случаи когда разбиение невозможно впринципе (хотя этим можно не заморачиваться, всеравно ограничение по глубине сработает)

ps. На оптимальность алгоритма я не претендую

Последний раз редактировалось zamtmn, 16.09.2013 в 21:25.
zamtmn вне форума  
Ответ
Вернуться   Форум DWG.RU > Программное обеспечение > Программирование > Оптимизация обработки большого числа элементов

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Документация Проектировщику на Torrents DEM Разное 262 24.02.2024 17:19
Жилые и общественные здания: краткий справочник инженера-конструктора. Под ред. Ю.А. Дыховичного и В.И. Колчунова. 2011 (Впечатления и отзывы). Armin Поиск литературы, чертежей, моделей и прочих материалов 19 22.03.2018 15:41
Порекомендуйте литературу для повышения квалификации(грунты, геотехника) acid Поиск литературы, чертежей, моделей и прочих материалов 6 13.05.2015 22:14
Случайный эксцентриситет p_sh Прочее. Архитектура и строительство 14 22.07.2009 11:32
Защита от распространения большого числа dwg E.D. AutoCAD 24 21.11.2008 09:02