Вычислительная геометрия: обнаружение дыр

[DLL]

Munin в сообщении #1131814 писал(а):

(Оффтоп)

DLL в сообщении #1131812 писал(а):

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

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

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

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

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

[Xaositect]

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

[Karan]

DLL, предупреждение за нецензурную лексику

[DLL]

Ни один работодатель ни одобрит такой cross-check - писать на диск фи

[Утундрий]

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

(Оффтоп)

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

[arseniiv]

(Оффтоп)

DLL в сообщении #1131847 писал(а):

Ни один работодатель ни одобрит такой cross-check - писать на диск фи

А вы постарайтесь не работать с такими квадратными работодателями. (Если вы щас серьёзно это написали.)

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

[DLL]

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

[Утундрий]

(Оффтоп)

DLL в сообщении #1131858 писал(а):

не думаю, что мы вправе им требования выставлять...

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

[DLL]

Чувак, ну это бизнес
Там иначе все работает

[Sonic86]

DLL в сообщении #1131812 писал(а):

Единственное, что когда мы работаем на практике - может оказаться что у нас 10 миллиардов патчей (треугольников).

DLL в сообщении #1131816 писал(а):

P.S: а куда надо пихать?

Вы прикиньте, сколько это жрет памяти. И сколько у Вас ее есть.
Пээээ...., я когда триангуляцию Делоне писал, у меня было 20000 вершин и примерно в 2 раза больше треугольников. И то было вполне реально (секунды работало). Но $10^{10}$ треугольников... Для этого нужны развитые специальные средства обработки - внешние сортировки, м.б. СУБД какие-нибудь, всякая машинная оптимизация, учет конкретики данных, параллелизм, м.б. какая-нибудь простая сжимающая предобработка... Жуть...

(Оффтоп)

DLL в сообщении #1131860 писал(а):

Чувак, ну это бизнес

Да, особенно если коммерческий и все жаждут бабла. Все правда, подтверждаю

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

[DLL]

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

[Sonic86]

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

[Xaositect]

DLL в сообщении #1131847 писал(а):

Ни один работодатель ни одобрит такой cross-check - писать на диск фи

Ну тогда поступите энтерпрайзно - пишите в базу данных. Она сама разберется, что на диск писать, что в памяти держать.

[Karan]

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

[Sonic86]

Xaositect в сообщении #1131874 писал(а):

Ну тогда поступите энтерпрайзно - пишите в базу данных. Она сама разберется, что на диск писать, что в памяти держать.

Я так пробовал. Время обработки сразу увеличивается в несколько порядков.
Если товарищ хочет эффективности - пусть пишет конкретику, чем больше, тем ему же лучше.