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

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

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

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

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

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

И подвопрос: для файлов примерно какого размера (+-полмегабайта) или какого числа элементов (+-1000), или числа вершин элементов (+-1000) подобные ухищрения имеют смысл на не очень мощных и на хороших компьютерах? Эмпирически-экспертно, конечно.
Просмотров: 46084
 
Непрочитано 26.09.2013, 15:35
#101
Мансур

Инженер САПР
 
Регистрация: 12.11.2004
Тюмень
Сообщений: 36
<phrase 1=


Цитата:
Сообщение от bargool Посмотреть сообщение
Поправьте меня, если я ошибаюсь: эта волшебная функция требует, что бы данный прямоугольник был на экране. Т.е. либо скакать по всему чертежу, либо масштабировать, что бы весь чертёж сразу был на экране.
Да, именно так. Скакать по чертежу имхо не стоит, можно принудительно делать "zoom extents".
Абсолютно согласен, каждый подход имеет свое предназначение. Просто про вариант с ssget мало кто задумывается, а в большинстве случаев надо "не шашечки, а ехать". Да и объем кода получается на порядок меньше, проще сопровождать потом, в случае надобности.
Мансур вне форума  
 
Непрочитано 27.09.2013, 14:13
#102
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


ssget действительно хорошо оптимизированна но работать общая программа будет медленно - т.к. между вызовами ей все равно все по новой пересчитывать.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 27.09.2013, 16:07
#103
Мансур

Инженер САПР
 
Регистрация: 12.11.2004
Тюмень
Сообщений: 36
<phrase 1=


Цитата:
Сообщение от Дима_ Посмотреть сообщение
ssget действительно хорошо оптимизированна но работать общая программа будет медленно - т.к. между вызовами ей все равно все по новой пересчитывать.
Или я чего-то недопонял, или...
С чего программе работать медленно? Возьмем цифры с потолка - пусть в чертеже 10000 объектов. Если устроить тупой перебор: каждая линия с остальными, можете сами посчитать количество сочетаний (если не ошибаюсь, это будет 10000*9999/2= 49 995 000). А если пользуемся ssget (опять же условно возьмем, что в среднем ssget вернул 10 объектов для каждой анализируемой линии), то количество сочетаний 10000*10 = 100 000. Есть разница между 50 миллионами итераций и сотней тысяч? У меня чертеж с 20 000 объектов обрабатывается в лиспе за пару десятков секунд.
Мансур вне форума  
 
Непрочитано 27.09.2013, 16:25
#104
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Цитата:
Сообщение от Мансур Посмотреть сообщение
А если пользуемся ssget (опять же условно возьмем, что в среднем ssget вернул 10 объектов для каждой анализируемой линии)
Вернул-то он их не с потолка, ему так-же надо перебрать все объекты (для начала просто габариты ну и далее по нарастающей сложности). Ведь для создания двревовидной структуры нужно время и для эффективного выполнения она создается 1 раз - а ssget'у не известно проходили-ли изменения чертежа между вызовами или нет.
Цитата:
Сообщение от Мансур Посмотреть сообщение
У меня чертеж с 20 000 объектов обрабатывается в лиспе за пару десятков секунд.
а 40 тысяч за сколько он обработает - линейная зависимость??
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 27.09.2013, 16:34
#105
zamtmn

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


>>Ведь для создания двревовидной структуры нужно время и для эффективного выполнения она создается 1 раз - а ssget'у не известно проходили-ли изменения чертежа между вызовами или нет.
Думаю в автокаде оная структура поддерживается в актуальном состоянии всегда. т.к. она важна не только для поиска чегонибудь, а практически для всех операций с чертежем.

но ssget даже в реализации на компилируемом языке всеравно проиграет поиску с прямым доступом к "дереву" - т.к. он вынужден всегда начинать поиск с корня. также свое дерево заглаза себя оправдает для операций не на всем чертеже, а только над частью примитивов - дерево нужно будет строить только для них - операции с ним будут быстрее и сбалансированность лучше
zamtmn вне форума  
 
Непрочитано 27.09.2013, 16:43
#106
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Цитата:
Сообщение от zamtmn Посмотреть сообщение
Думаю в автокаде оная структура поддерживается в актуальном состоянии всегда. т.к. она важна не только для поиска чегонибудь, а практически для всех операций с чертежем.
Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.
Offtop: В этой строке немой намек вопрос главному по ARX А.Ривилису.
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 27.09.2013, 17:15
#107
zamtmn

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


>>Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.
Чудес не бывает, без "дерева" автокад бы ползал. Даже если в arx этого нет (хотя имхо и недолжно быть) много других "следов"
zamtmn вне форума  
 
Непрочитано 27.09.2013, 18:27
#108
Мансур

Инженер САПР
 
Регистрация: 12.11.2004
Тюмень
Сообщений: 36
<phrase 1=


Цитата:
Сообщение от Дима_ Посмотреть сообщение
а 40 тысяч за сколько он обработает - линейная зависимость??
Код:
[Выделить все]
Команда: DATE
Fri 2013/9/27 20:20:16.621

Команда:
Команда: MTMDJOIN

Выберите объекты: Противоположный угол: найдено: 42921

Выберите объекты:

Допустимое отклонение <0.2>:
3666 polylines generated, 23978 lines joined

Команда:
Команда: DATE
Fri 2013/9/27 20:22:01.750
Меньше двух минут. Понятное дело, зависимость не линейная, тем не менее скорость более чем приемлемая
Мансур вне форума  
 
Непрочитано 27.09.2013, 23:12
#109
zamtmn

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


Мансур
>>тем не менее скорость более чем приемлемая
для лиспа очень даже.
Пожалуйста прогоните через "объеденялку" файл из #57 ,будут теже 2 митуты? мне интересно для статистики.
zamtmn вне форума  
 
Автор темы   Непрочитано 28.09.2013, 00:04
#110
АлексЮстасу

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


Цитата:
Сообщение от Мансур Посмотреть сообщение
Волшебная функция (ssget "_C" p1 p2) наверняка уже тыщу раз оптимизирована разработчиками, берите и используйте - тогда даже на обыкновенном autolisp все шустро просчитывается. Если непонятно: берете примитив, получаете его bounding box, по ним ssget - получаете (обычно) небольшой набор, по нему уже тупо перебором проверили реальные пересечения.
Для непосвещенных.
Эта ssget выдает набор чего? Примитивов, пересекающих указанный? Примитивов, попадающих в габарит указанного примитива? Или еще что-то?
Эта ssget чисто лисповская или у нее есть аналоги в ARX?
АлексЮстасу вне форума  
 
Непрочитано 28.09.2013, 00:44
#111
Александр Ривилис

программист, рыцарь ObjectARX
 
Регистрация: 09.05.2005
Киев
Сообщений: 2,405
Отправить сообщение для Александр Ривилис с помощью Skype™


Цитата:
Сообщение от Дима_ Посмотреть сообщение
Ну вряд-ли бы "прятали" соответствующее апи - как минимум на уровне ARX.
Так вроде никуда и не прячут. AcGi/AcGs классы. Вообще-то ssget (acedSSGet в ObjectARX), кроме варианта с опцией "_X" работает с проекцией примитивов на плоскость. На виртуальный экран.
Александр Ривилис вне форума  
 
Непрочитано 28.09.2013, 00:55
#112
Дима_

Продуман
 
Регистрация: 22.02.2007
Питер
Сообщений: 2,840


Я не про то, что там есть аналог ssget - может из ARX можно разглядеть структуру которую использует эта функция (то есть определяет простым перебором по БД, либо она таки использует пространственное индексирование - на основе например R-tree)?
__________________
Когда в руках молоток все вокруг кажется гвоздями.
Дима_ вне форума  
 
Непрочитано 28.09.2013, 01:32
#113
Александр Ривилис

программист, рыцарь ObjectARX
 
Регистрация: 09.05.2005
Киев
Сообщений: 2,405
Отправить сообщение для Александр Ривилис с помощью Skype™


Алгоритм конечно не виден. Но точно не простой перебор по БД, т.к. эта функция вообще с БД (AcDbDatabase) не работает, а работает с виртуальным экраном, т.е. с проекциями примитивов. Но этот подход имеет свой минус - примитивы должны быть видны и различимы.
Александр Ривилис вне форума  
 
Непрочитано 28.09.2013, 10:36
#114
zamtmn

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


>>а работает с виртуальным экраном
т.е. acedSSGet не выберет например сплайн если в область выбора попадает "математически правильный" фрагмент кривой но не попадает его кусочно-линейная апроксимация?
zamtmn вне форума  
 
Непрочитано 28.09.2013, 18:03
#115
Александр Ривилис

программист, рыцарь ObjectARX
 
Регистрация: 09.05.2005
Киев
Сообщений: 2,405
Отправить сообщение для Александр Ривилис с помощью Skype™


Цитата:
Сообщение от zamtmn Посмотреть сообщение
т.е. acedSSGet не выберет например сплайн если в область выбора попадает "математически правильный" фрагмент кривой но не попадает его кусочно-линейная апроксимация?
Да. Во всяком случае так было в те времена, когда я это проверял. Возможно что-то изменилось в последних трёх-четырёх версиях, но я сомневаюсь.
Александр Ривилис вне форума  
 
Непрочитано 28.09.2013, 23:11
#116
zamtmn

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


Собственно ничего не мешает автокаду строить "деревъя" не над базой данных, а над хозяйством полученым после worldDraw (или что там для "отрисовки") всех примитивов, так даже проще на уровне примитивов - все сложности уходят в дпугой "слой" программы. Однако теже привязки считаются не над "проекциями" примитивов - иначе они бы сильно врали
zamtmn вне форума  
 
Непрочитано 28.09.2013, 23:42
#117
Кулик Алексей aka kpblc
Moderator

LISP, C# (ACAD 200[9,12,13,14])
 
Регистрация: 25.08.2003
С.-Петербург
Сообщений: 39,787


Цитата:
Сообщение от zamtmn Посмотреть сообщение
Однако теже привязки считаются не над "проекциями" примитивов - иначе они бы сильно врали
Не совсем так.
__________________
Моя библиотека lisp-функций
---
Обращение ко мне - на "ты".
Все, что сказано - личное мнение.
Кулик Алексей aka kpblc вне форума  
 
Непрочитано 28.09.2013, 23:51
#118
zamtmn

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


>>Не совсем так.
В смысле? насколко помню из своих экспериментов например пересечение сплайнов это действительно пересечение сплайнов с точностью заданной в примитивах, а не пересечение линий их апроксимирующих
zamtmn вне форума  
 
Автор темы   Непрочитано 29.09.2013, 05:15
#119
АлексЮстасу

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


Цитата:
Сообщение от trir Посмотреть сообщение
Пурга. Сложность поиска в списке O(n) - где n - количество элементов. Сложность поиска в дереве O(h) - где h - высота дерева.
Вы не поняли моего предложения. Предлагается не список примитивов, а списки примитивов, попадающих в ячейки сетки. Массив списков примитивов по ячейкам.
Цитата:
Сообщение от zamtmn Посмотреть сообщение
Насколько я понимаю АлексЮстасу хочет сказать что в его сетке сложность будет O(1), но это действительно пурга, т.к. идеально разбить не подготовленные специально данные не получится.
Цитата:
Сообщение от Дима_ Посмотреть сообщение
Ваш "алгоритм" будет эффективен только на специально приготовленных для него чертежах.
Вы говорите о необходимости подготовке данных, наверное, исходя из посылки, что один примитив необходимо описывать в одной единице объема. Да, один примитив при регулярном разбиении в общем случае окажется в нескольких ячейках, и ничего не нужно подготавливать. Но ничего страшного в этом нет - по вершинам примитива, по его габариту, просто просмотром соседних ячеек находятся все нужные ячейки. Да, это издержка метода. Но, возможно, единственная.
Общее соображение: т.к. в общем случае примитивы равнозначны, то привязывать сведения о положении в пространстве примитивов к разным уровням дерева некорректно. Естественно определять их на одном, нижнем уровне. А на уровнях выше, соответственно, определять сведения о положении уже их множеств. Точнее - подпространств, из которых состоит пространство файла.
При регулярном разбиении пространства файла есть преимущества. Оно представляет весь файл в виде матрицы или в виде как бы "растра"- кому какой образ больше говорит. На построение и сохранение собственно дерева время тратить не нужно. Но по регулярным ячейкам можно использовать любой подходящий для конкретной задачи алгоритм поиска, в том числе и дерево. Разделяя все множество ячеек (все пространство) на любые подходящие их подмножества: делением на две части, на четыре, сразу на 16, на нужное число уровней и т.п. Т.е. регулярное разбиение уже содержит все возможности дерева, уже есть дерево, причем, допущу, любого типа.
Или, при анализе "снизу", можно брать смежные ячейки в нужном количестве. И не обязательно прямоугольниками, но и в наборе произвольной формы.
При этом, взаимное положение любых ячеек априори известно без всякого дополнительного структурирования, без обращения к возможностям дерева.
Сам оценить O() регулярного разбиения не возьмусь.
АлексЮстасу вне форума  
 
Непрочитано 29.09.2013, 11:35
#120
zamtmn

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


>>При регулярном разбиении пространства файла есть преимущества. Оно представляет весь файл в виде матрицы или в виде как бы "растра"- кому какой образ больше говорит
Возмите regular.dxf и сдвинте 1 "крестик" коданибудь в сторону например на 10000000 едениц чертежа - все "приемущества" регулярного разбиения на этом сразу закончатся, древовидная структура проглотит это незаметив, просто увеличив глубину на еденицу и сохранив тоже качество разбивки

Последний раз редактировалось zamtmn, 29.09.2013 в 11:46.
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