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

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

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

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

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

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

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


 
Регистрация: 16.08.2006
Санкт-Петербург
Сообщений: 508
<phrase 1=


АлексЮстасу, я не очень вникал в ваш алгоритм, но если претит R-Tree, или другие предложенные варианты, может будет более понятно quadtree
Но мне лично кажется, что для работы с объектами произвольных размеров (не точками), лучше работать с помощью R-Tree, хотя может я и ошибаюсь, quadtree я не пробовал
__________________
Алексей

Последний раз редактировалось bargool, 29.09.2013 в 15:17.
bargool вне форума  
 
Автор темы   Непрочитано 30.09.2013, 01:32
#122
АлексЮстасу

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


Цитата:
Сообщение от zamtmn Посмотреть сообщение
сдвинте 1 "крестик" коданибудь в сторону например на 10000000 едениц чертежа - все "приемущества" регулярного разбиения на этом сразу закончатся
В чем именно при таком сдвиге проблема для регулярного разбиения?
Цитата:
Сообщение от bargool Посмотреть сообщение
я не очень вникал в ваш алгоритм, но если претит R-Tree, или другие предложенные варианты, может будет более понятно quadtree
Но мне лично кажется, что для работы с объектами произвольных размеров (не точками), лучше работать с помощью R-Tree, хотя может я и ошибаюсь, quadtree я не пробовал
И совсем не против деревьев, и ни одно из них мне не претит. Да и регулярное разбиение содержит в себе возможности деревьев.
Пытаюсь разобраться, какое или как лучше. Не в последнюю очередь - практически. Ведь из названных в теме вариантов пока нет под Автокад ни одного реализованного.

Последний раз редактировалось АлексЮстасу, 30.09.2013 в 03:12.
АлексЮстасу вне форума  
 
Непрочитано 30.09.2013, 07:41
#123
zamtmn

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


>>В чем именно при таком сдвиге проблема для регулярного разбиения?
ээх, сколько можно об одном и томже)) В этом случае может быть 2 варианта реализации:
1 - ячейки в линейном "массиве" с быстрым доступом по индексу (как вы и предлагаете насколько я понял), но 99.99999% "ячеек" пустые и занимают всю доступную память - расход памяти зависит от геометрических размеров модели, а не от ее наполнения.
2 - храним только "заполненные" ячейки - доступ к ним не по индексу, а "перебором" с поиском нужной. И тут, ВНИМАНИЕ, для ускорения поиска в этой структуре придется вводить бинарное дерево.

>>Ведь из названных в теме вариантов пока нет под Автокад ни одного реализованного
Давайте уже делайте и выкладывайте))
zamtmn вне форума  
 
Непрочитано 30.09.2013, 08:03
#124
Мансур

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


Цитата:
Сообщение от zamtmn Посмотреть сообщение
Мансур
>>тем не менее скорость более чем приемлемая
для лиспа очень даже.
Пожалуйста прогоните через "объеденялку" файл из #57 ,будут теже 2 митуты? мне интересно для статистики.
Команда: MTMDJOIN
Выберите объекты: Противоположный угол: найдено: 45306
Допустимое отклонение <0.2>: 1235 polylines generated, 43776 lines joined
Выполнено за 21.013 сек.
Что сырой лисп, что компилированный - время примерно одно - 20-21 сек на моей машине.
UPD: только что проверил на свежескачанной бете BricsCAD 14 x64 - на глаз скорость чуть ли не в два раза выше, чем AutoCAD. Где-то читал, что Бриксис очень хорошо оптимизировал свой лисп-движок

Последний раз редактировалось Мансур, 30.09.2013 в 08:50.
Мансур вне форума  
 
Автор темы   Непрочитано 30.09.2013, 20:19
#125
АлексЮстасу

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


Цитата:
Сообщение от zamtmn Посмотреть сообщение
Давайте уже делайте и выкладывайте))
Первые результаты на неплохой машине 64-разрядной, 16 Гб памяти:
regular.dwg
Цитата:
Элементов для обработки: 20000
Построение сетки: 0.06 сек.
Размер сетки: 64x64
Поиск пересечений: 0.02 сек.
Пересечений: 9003
Создание объектов: 2.19 сек.
Это, кстати, раза в 1.5-2 лучше, чем у Autocad Map 3D, Drawing cleanup.
nonregular2.dwg
Цитата:
Элементов для обработки: 1172
Построение сетки: 0.03 сек.
Размер сетки: 64x64
Поиск пересечений: 0.01 сек.
Пересечений: 23856
Создание объектов: 2.20 сек.
nonregular.dwg
Цитата:
Элементов для обработки: 20000
Построение сетки: 143.7 сек.
Размер сетки: 64x64
Поиск пересечений: 6.07 сек.
И результата для nonregular.dwg я за 1.5 часа не дождался - все ресурсы компьютера были съедены созданием 10 с гаком миллионов новых примитивов.
Взял regular.dwg, и перенес один крест на 10000000 в сторону:
Цитата:
Построение сетки: 9.43 сек.
Размер сетки: 64x64
Поиск пересечений: 0.34 сек.
Пересечений: 8020
Создание объектов: 1.99 сек.
Т.е. в сумме почти 12 секунд.
Это первый блин, который только сегодня мне, наконец, выложили.
Как видите, "сетка" пока всегда одинаковая - 64x64.
И что за "сетка", как что куда записывается, создается ли параллельно дерево и т.п. - пока не спрашивайте. Даже не спрашивайте, сетка ли там на самом деле или баобаб. Поскольку и наш программист тоже разговаривает на другом языке
Надеюсь, мы "сетку" еще оптимизируем. Тогда главная будет проблема - требуются гигантские ресурсы на создание новых элементов, т.е. на разбиение на пересечениях?
АлексЮстасу вне форума  
 
Непрочитано 30.09.2013, 23:23
#126
zamtmn

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


Поздравляю с первым блином)) не совсем понял толко почему время создания так отличается на исходном и сдвинутом regular - сетка то там и там одинаковая - видимо реализация очень "наколенная". Также неясно с колвом пересечений - в регуляр их 10000 точно, в нонрегуляр2 - 22067 и нонрегуляр - 11559108 по моим результатам
Неплохо было бы приводить результаты для сетки 1х1 - чтоб было наглядно видно ускорение от повышения разрешения "сетки"

>>требуются гигантские ресурсы на создание новых элементов
требуется создание ~23 миллионов примитивов, помоему невыполнимая задача без промежуточных сохранений результатов. Да и нужно оно толко для "теста" - в реалной жизни такого не попадется.
Имхо зря вы так схватились за сетку - это интересно только как "эксперимент", с практической точки зрения закончится тупиком - причины выше описаны
zamtmn вне форума  
 
Непрочитано 03.10.2013, 01:08
#127
zamtmn

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


Попал в руки ноут с i7 16Гб озу и 32Гб свапа.
nonregular.dxf таки был порезан, но с получеными на выходе миллионами линий графический движек зкада не совладал и впал в большую тоску(( поэтому цитата с лога, а не с вывода командной строки

Код:
[Выделить все]
!!!! 23:40:28  HISTORY: Запущена команда:FindAllIntersections---- t:=10:17.849, dt:=10:17.849 tick:=739738009, dtick:=739738009
!!!! 23:40:40  HISTORY: Search intersections and storing data:  14.49 секунд t:=10:30.367, dt:=10:30.367 tick:=754725139, dtick:=754725139
!!!! 23:40:52  HISTORY: Placing points:  14.04 секунд--------------------- t:=10:42.497, dt:=10:42.497 tick:=769247721, dtick:=769247721
!!!! 23:48:09  HISTORY: Cutting lines:  505.55 секунд--------------------- t:=17:59.329, dt:=17:59.329 tick:=1292258916, dtick:=1292258916
!!!! 23:48:09  HISTORY: Lines modified: 20000----------------------------------- t:=17:59.331, dt:=17:59.331 tick:=1292261051, dtick:=1292261051
!!!! 23:48:09  HISTORY: Lines created: 23118220--------------------------------- t:=17:59.331, dt:=17:59.331 tick:=1292261241, dtick:=1292261241
!!!! 23:48:10  HISTORY: Freeing memory:  0.47 секунд---------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744068, dtick:=1292744068
!!!! 23:48:10  HISTORY: Line-AABB tests count: 601354--------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744348, dtick:=1292744348
!!!! 23:48:10  HISTORY: Line-Line tests count: 86247095------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744502, dtick:=1292744502
!!!! 23:48:10  HISTORY: Intersections count: 11559110--------------------------- t:=17:59.735, dt:=17:59.735 tick:=1292744652, dtick:=1292744652
всё тоже самое, только обрамлено дополнительной информацией - t и tick - отладочная информация о времени и тиках процессора, ее можно не глядеть. 14.5 сек поиск пересечений, 14 сек расстановка точек, 506 сек подрезка линий. в процессе работы было съедено всё озу и 50% свапа, по окончании перед повисанием на отображении полученое месиво из линий весило 9Гб в ОЗУ.

update:
откудато набежало 2 "лишних" пересечения, вроде ничего серъезного не менял((. и со времнем внутри программы и фиксации в логе чтото нето((

Последний раз редактировалось zamtmn, 03.10.2013 в 01:40.
zamtmn вне форума  
 
Непрочитано 05.10.2017, 01:18
#128
zamtmn

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


Расчехлю лопату.
Переделал статистику по разбиению пространства и приделал визуализацию. может кому будет интересно.

regular.dwg
Цитата:
Запущена команда:TreeStat
Total entities in drawing: 20000
Max tree depth: 16
Max in node entities: 500
Current drawing spatial index Info:
Total entities: 20000
Memory usage (bytes): 18415
Total nodes: 127
Total overflow nodes: 0
Fact tree depth: 6
By levels:
level 0
Entities: 0
Entities(%)[summary]: 0.00[0.00]
Nodes: 1
Overflow nodes: 0
level 1
Entities: 80
Entities(%)[summary]: 0.40[0.40]
Nodes: 2
Overflow nodes: 0
level 2
Entities: 199
Entities(%)[summary]: 1.00[1.40]
Nodes: 4
Overflow nodes: 0
level 3
Entities: 239
Entities(%)[summary]: 1.20[2.59]
Nodes: 8
Overflow nodes: 0
level 4
Entities: 495
Entities(%)[summary]: 2.47[5.07]
Nodes: 16
Overflow nodes: 0
level 5
Entities: 795
Entities(%)[summary]: 3.97[9.04]
Nodes: 32
Overflow nodes: 0
level 6
Entities: 18192
Entities(%)[summary]: 90.96[100.00]
Nodes: 64
Overflow nodes: 0
Nodes with population 0: 1
Nodes with population 24: 18
Nodes with population 25: 26
Nodes with population 26: 1
Nodes with population 27: 1
Nodes with population 28: 2
Nodes with population 32: 1
Nodes with population 33: 1
Nodes with population 37: 1
Nodes with population 38: 1
Nodes with population 40: 2
Nodes with population 49: 3
Nodes with population 50: 5
Nodes with population 244: 1
Nodes with population 245: 1
Nodes with population 247: 1
Nodes with population 248: 1
Nodes with population 249: 1
Nodes with population 252: 1
Nodes with population 254: 1
Nodes with population 256: 1
Nodes with population 260: 1
Nodes with population 262: 1
Nodes with population 264: 1
Nodes with population 269: 6
Nodes with population 270: 5
Nodes with population 271: 2
Nodes with population 272: 4
Nodes with population 273: 1
Nodes with population 280: 1
Nodes with population 281: 1
Nodes with population 288: 2
Nodes with population 291: 3
Nodes with population 292: 1
Nodes with population 293: 2
Nodes with population 294: 4
Nodes with population 296: 2
Nodes with population 297: 3
Nodes with population 298: 2
Nodes with population 300: 3
Nodes with population 308: 1
Nodes with population 318: 3
Nodes with population 319: 3
Nodes with population 320: 2
Nodes with population 321: 2
nonregular.dwg
Цитата:
Запущена команда:TreeStat
Total entities in drawing: 20000
Max tree depth: 16
Max in node entities: 500
Current drawing spatial index Info:
Total entities: 20000
Memory usage (bytes): 4495
Total nodes: 31
Total overflow nodes: 7
Fact tree depth: 4
By levels:
level 0
Entities: 4987
Entities(%)[summary]: 24.93[24.93]
Nodes: 1
Overflow nodes: 1
level 1
Entities: 3824
Entities(%)[summary]: 19.12[44.06]
Nodes: 2
Overflow nodes: 2
level 2
Entities: 4962
Entities(%)[summary]: 24.81[68.86]
Nodes: 4
Overflow nodes: 4
level 3
Entities: 2865
Entities(%)[summary]: 14.33[83.19]
Nodes: 8
Overflow nodes: 0
level 4
Entities: 3362
Entities(%)[summary]: 16.81[100.00]
Nodes: 16
Overflow nodes: 0
Nodes with population 171: 1
Nodes with population 180: 1
Nodes with population 187: 1
Nodes with population 192: 1
Nodes with population 199: 1
Nodes with population 202: 1
Nodes with population 203: 1
Nodes with population 205: 2
Nodes with population 215: 1
Nodes with population 216: 1
Nodes with population 223: 1
Nodes with population 231: 1
Nodes with population 233: 1
Nodes with population 240: 1
Nodes with population 260: 1
Nodes with population 319: 1
Nodes with population 327: 1
Nodes with population 331: 1
Nodes with population 341: 1
Nodes with population 369: 1
Nodes with population 378: 1
Nodes with population 388: 1
Nodes with population 412: 1
Nodes with population 1207: 1
Nodes with population 1228: 1
Nodes with population 1258: 1
Nodes with population 1269: 1
Nodes with population 1908: 1
Nodes with population 1916: 1
Nodes with population 4987: 1
nonregular2.dwg
Цитата:
Запущена команда:TreeStat
Total entities in drawing: 1172
Max tree depth: 16
Max in node entities: 500
Current drawing spatial index Info:
Total entities: 1172
Memory usage (bytes): 1015
Total nodes: 7
Total overflow nodes: 0
Fact tree depth: 2
By levels:
level 0
Entities: 27
Entities(%)[summary]: 2.30[2.30]
Nodes: 1
Overflow nodes: 0
level 1
Entities: 109
Entities(%)[summary]: 9.30[11.60]
Nodes: 2
Overflow nodes: 0
level 2
Entities: 1036
Entities(%)[summary]: 88.40[100.00]
Nodes: 4
Overflow nodes: 0
Nodes with population 27: 1
Nodes with population 40: 1
Nodes with population 69: 1
Nodes with population 243: 1
Nodes with population 246: 1
Nodes with population 271: 1
Nodes with population 276: 1
Картинки с разбиением прилагаю. regular.png на форум не влез, лежит тут https://imgur.com/a/YQ569
Миниатюры
Нажмите на изображение для увеличения
Название: nonregular.jpg
Просмотров: 18
Размер:	36.9 Кб
ID:	194369  Нажмите на изображение для увеличения
Название: nonregular2.png
Просмотров: 23
Размер:	42.5 Кб
ID:	194370  
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