2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 18:32 
Аватара пользователя


12/03/11
688
Munin в сообщении #1131814 писал(а):

(Оффтоп)

DLL в сообщении #1131812 писал(а):
Единственное, что когда мы работаем на практике - может оказаться что у нас 10 миллиардов патчей (треугольников).
В этом случае даже сортировка уже может быть проблемой - поскольку std::vector столько элементов иногда не хочет в себя помещать...

Изображение Кто вас учил такие объёмы данных пихать в std::vector?

Ну есть всякие с#аные конторы, которые занимаются CFD и которые платят много денюх, из-за которых пришлось бросить любимое дело :-( :-( :-(
P.S: а куда надо пихать?

-- Ср июн 15, 2016 19:34:42 --

Мунин расскажите, я вас расцалую!
P.S: можем даже денюх заплатить за дельный совет :-) :-) :-)

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 20:42 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ну если достаточно памяти, то можно и в std::vector, оверхед над массивом там небольшой. А так надо пихать в файл, делить на куски, влезающие в память, сортировать все куски, а потом сливать их.
В Кнуте есть раздел про сортировку большого количества данных (external sorting).

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 20:49 
Модератор


19/10/15
1196
 !  DLL, предупреждение за нецензурную лексику

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:00 
Аватара пользователя


12/03/11
688
Ни один работодатель ни одобрит такой cross-check - писать на диск фи :-(

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:09 
Заслуженный участник
Аватара пользователя


15/10/08
11533
DLL, для любой вменяемой задачи с головой хватит пары сотен "треугольничков". А если не хватило, то задача невменяемая.

(Оффтоп)

...причём, основной вклад в невменяемость задачи вносит её решатель.

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:13 
Заслуженный участник


27/04/09
28128

(Оффтоп)

DLL в сообщении #1131847 писал(а):
Ни один работодатель ни одобрит такой cross-check - писать на диск фи :-(
А вы постарайтесь не работать с такими квадратными работодателями. :? (Если вы щас серьёзно это написали.)

[Сначала подумал, что есть файловая система, где диску можно присвоить имя $\Phi\colon$. :D ]

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:17 
Аватара пользователя


12/03/11
688
Утундрий
хз, если заказчики Audi, BMW, Boeing и т.д. не думаю, что мы вправе им требования выставлять...
тем более в CFD сетки в 10 миллиардов патчией - это стандарт :(

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:25 
Заслуженный участник
Аватара пользователя


15/10/08
11533

(Оффтоп)

DLL в сообщении #1131858 писал(а):
не думаю, что мы вправе им требования выставлять...

Да Тензор упаси! Раз так мощно послали, так и просто идите. Только постарайтесь всю вашу рефлексию отринуть решительнейшим образом. Зачем, мол, да почему "от забора и до обеда..." Сразу как увидите три зелёных свистка - копайте.

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:28 
Аватара пользователя


12/03/11
688
Чувак, ну это бизнес :shock:
Там иначе все работает :-)

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:31 
Заслуженный участник


08/04/08
8556
DLL в сообщении #1131812 писал(а):
Единственное, что когда мы работаем на практике - может оказаться что у нас 10 миллиардов патчей (треугольников).
DLL в сообщении #1131816 писал(а):
P.S: а куда надо пихать?
Вы прикиньте, сколько это жрет памяти. :shock: И сколько у Вас ее есть.
Пээээ...., я когда триангуляцию Делоне писал, у меня было 20000 вершин и примерно в 2 раза больше треугольников. И то было вполне реально (секунды работало). Но $10^{10}$ треугольников... Для этого нужны развитые специальные средства обработки - внешние сортировки, м.б. СУБД какие-нибудь, всякая машинная оптимизация, учет конкретики данных, параллелизм, м.б. какая-нибудь простая сжимающая предобработка... Жуть...

(Оффтоп)

DLL в сообщении #1131860 писал(а):
Чувак, ну это бизнес :shock:
Да, особенно если коммерческий и все жаждут бабла. Все правда, подтверждаю :-(


upd: Я пас. Вам нужен узкий специалист.

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:33 
Аватара пользователя


12/03/11
688
Именно - речь про то и идет - как это можно делать эффективно.
BMW хочет эффективных решений, дядям нужны новые большие коттеджи...
А в России могут и еще поужаться :mrgreen:

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 21:49 
Заслуженный участник


08/04/08
8556
Не, так чисто математика Вам здесь сильно не поможет. Если Вашу задачу правильно поняли, то набросок алгоритма Вам уже дали. Он, кажется, $O(n \ln n)$ + памяти еще может сожрать $O(n)$ (если все треугольники изолированные), а сильнее и не получится без дополнительных предположений. Быстрее чем $O(n)$ в принципе не получится.
А дальше придется смотреть конкретику, т.е. оптимизировать только коэффициент: смотреть какая структура данных, сколько она занимает места, сколько вообще памяти оперативной, выписать алгоритм конкретно, попытаться уменьшить число операций, оптимизировать типы и т.п.. Чисто математика без конкретики здесь просто не поможет.
М.б. venco Вам сможет помочь.

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 22:05 
Заслуженный участник
Аватара пользователя


06/10/08
6422
DLL в сообщении #1131847 писал(а):
Ни один работодатель ни одобрит такой cross-check - писать на диск фи :-(
Ну тогда поступите энтерпрайзно - пишите в базу данных. Она сама разберется, что на диск писать, что в памяти держать.

 Профиль  
                  
 
 Posted automatically
Сообщение15.06.2016, 22:07 
Модератор


19/10/15
1196
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

 Профиль  
                  
 
 Re: Вычислительная геометрия: обнаружение дыр
Сообщение15.06.2016, 22:11 
Заслуженный участник


08/04/08
8556
Xaositect в сообщении #1131874 писал(а):
Ну тогда поступите энтерпрайзно - пишите в базу данных. Она сама разберется, что на диск писать, что в памяти держать.
Я так пробовал. Время обработки сразу увеличивается в несколько порядков.
Если товарищ хочет эффективности - пусть пишет конкретику, чем больше, тем ему же лучше.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group