Выбор кандидата для деления

[Igors]

Добрый день

Конкретно моя задача "адаптивная триангуляция", но нужный мне алгоритм наверняка более общий

Есть N полигонов, нужно выбирать из них самые крупные и разбивать на суб-полигоны. Разбитые полигоны могут быть опять разбиты. И так до тех пор пока все полигоны не станут достаточно малы или их число достигнет заданного.

Проблема в том как выбрать очередной полигон для деления. Сортировка ничего не дает, поскольку на каждом шаге образуются новые полигоны. А простой перебор = нестерпимые тормоза начиная примерно с миллиона полигонов.

Ваши соображения?

[Tonal]

Дерево, отсортированное по площади.
Алгоритма такой:
1. Проверяем нужно ли ещё делить.
2. Берём наибольший и удаляем из дерева.
3. Разбиваем.
4. Добавляем осколки в дерево
5 Идём в начало.

[spectre71]

Насколько я понял задача такова(если что не правильно поправь).
Исходные данные:
1) Есть множество однотипных объектов
2) Объекты данного множества могут быть полностью упорядочены!!!
2) Объекты данного множества можно сравнить с некоторой констатнтой того-же  или другого(например integer) типа
3) Объект данного множества может быть преобразован(разбит) в N объектов того же типа
Задача:
1) Изъять наибольший объект из множества
2) Разбить на объекты
3) Добавить полученные объекты во множество
4) Повторять операции 1-3 до тех пор пока максиамальный объект больше заданного и кол-во объектов во множестве меньше заданного числа.
 
Если все правильно, то;
1) Сортируем исходное множество.
2) Исходное множество разбиваем на 2 подмножества
  -  Max{}, некоторое заданное кол-во максимальных элементов или все элементы больше константы
  -  Min{}, все остальные
3) Выбираем максимальный из Max
4) Разбиваем его и получаем из него множество Cur{}
5) Сортируем Cur, вставляем (с учетом порядка) из Cur в Max все которые больше минимального в Max
6) Все остальные из Cur добавляем во множество Trash{}
7) Повторяем 3-6 до тех пор пока Max не опустеет
8.) Сортируем Trash и вставляем (с учетом порядка) все элементы из Trash в Min
9) Исходным множеством является множество Min. Возвращаемся к шагу 2.
Условие выхода сам обработаешь где надо.
Важно правильно подобрать условие разбивки на Max и Min.

[Igors]

Дерево, отсортированное по площади.
Алгоритма такой:
1. Проверяем нужно ли ещё делить.
2. Берём наибольший и удаляем из дерева.
3. Разбиваем.
4. Добавляем осколки в дерево
5 Идём в начало.

Tonal, извините, не очень понял. Если "просто дерево" - то я с этого ничего не имею. Если "какое-то особое" - то добавление в такое будет совсем недешево.

[Igors]

Если все правильно, то;
1) Сортируем исходное множество.
2) Исходное множество разбиваем на 2 подмножества
  -  Max{}, некоторое заданное кол-во максимальных элементов или все элементы больше константы
  -  Min{}, все остальные
3) Выбираем максимальный из Max
4) Разбиваем его и получаем из него множество Cur{}
5) Сортируем Cur, вставляем (с учетом порядка) из Cur в Max все которые больше минимального в Max
6) Все остальные из Cur добавляем во множество Trash{}
7) Повторяем 3-6 до тех пор пока Max не опустеет
8.) Сортируем Trash и вставляем (с учетом порядка) все элементы из Trash в Min
9) Исходным множеством является множество Min. Возвращаемся к шагу 2.
Условие выхода сам обработаешь где надо.
Важно правильно подобрать условие разбивки на Max и Min.

Это близко к тому что я нагородил  Постараюсь объяснить (наверное то же самое) попроще

1) Мы можем брать кандидатов подряд из сортированного массива и добавлять новые полигоны в хвост. Но только до тех пор пока площадь кандидата > S_new_max (максимальная площадь нового полигона). Если это условие не выполняется - снова сортируем.

2) Если площадь нового полигона > площади следующего кандидата, то имеет смысл добавить его в кэш прямой вставкой. Небольшой кэш (100 элементов) помогает сократить число сортировок. Теперь сначала берем из кэша и только если он пуст - из сортированного массива.

Все это работает, и гораздо быстрее чем прямой перебор. Однако я не удовлетворен. Во-первых, профайлер показывает что все равно "выбор кандидата" тянет больше чем само разбиение (сортировка на миллионах - удовольствие дорогое). Во-вторых, написано довольно много но как-то бестолково. Должен быть лучший способ.

Примечание: для этой конкретной задачи необязательно выбирать "самый-самый" лучший кандидат. Например, имеем такие
площади:

100, 99, 70, 20, 10

Наилучший 100, но не будет большого греха если сначала возьмем 99 (но, конечно, не 70)
 

[spectre71]

Не совсем понял 1 пукт.
1) Стоимость сортировки N*Log(N)
2) Стоимость объединения 2х сортированных массивов N+M
Поэтому необходимо как можно меньше сортировок больших массивов и меньше объединений с большим массивом, не надо добавлять в конец, а потом сортировать все вместе.
Лучше добавлять в другой массив, и потом в нужный момент сортировать его и объединять с основным.

Тот вариант который я привел можно оптимизировать дальше.
Можно кстати не использовать массив Max, а делать выборку из основного Cur{} и Add{} массива. В Add добавляются объекты разбиения выше определенного порога и до определенного колва(примерно как раньше в Max), а стальнные как и раньше  в несортированный Trash. Выборку делаешь так, смотришь наибольший в Cur и Add - выбираешь больший. Как только Add превысит определенное кол-во объединяешь его с Cur, как только максимальный элемент в Trash больше максимального в Cur, сортируешь Trash и объединяешь с Cur.
Отследить максимум в Trash легко при добавлении в него новых элементов.
Add нужен для того чтобы для частых объединений поступающих данных использовать маленький массив, но из-за него при выборке лучшего приходиться делать дополнительное сравнение(где лучший в Cur или Add)

[spectre71]

В предыдуще схеме мы имеем
1) Редкое объединение больших массивов Cur + Add, Cur + Trash
2) Редкую сортировку большого массива Trash
3) Очень частую сортировку маленького массива получаемого при разбиении объекта, необходима для разделения объектов в Add b Trash. Возможно самая накладная операция.
4) Очень частое объединение среднего массива Add + маленького после разбиения

Вопросы
1) Какое типичное и максимальное кол-во объектов получаемых при разбиении?
2) Ты упоминал про то, что необязательно выбирать максимальный. Как определяется допустимая D(дельта)?
От этого зависит как оптимизировать 3 и 4  пункт.

[Igors]

Поэтому необходимо как можно меньше сортировок больших массивов и меньше объединений с большим массивом, не надо добавлять в конец, а потом сортировать все вместе.
Лучше добавлять в другой массив, и потом в нужный момент сортировать его и объединять с основным.

Хммм.... в этом что-то есть. У меня появилась идейка, сделаю - расскажу 

[Winstrol]

Хммм.... в этом что-то есть. У меня появилась идейка, сделаю - расскажу 

Вновь полученные элементы разбиения логичней в очередь с приоритетами класть в таком случае.

[Tonal]

Дерево, отсортированное по площади.

Tonal, извините, не очень понял. Если "просто дерево" - то я с этого ничего не имею. Если "какое-то особое" - то добавление в такое будет совсем недешево.

Бинарное сбалансированное с сортировкой по площади. Тот же std::set.
Операции вставки и удаления не хуже чем log2 N.
Очередь  с приоритетами - тоже подойдёт - она, в сущности, тоже дерево.

Алгоритм гарантирует, что разбиваемый полигон будет всегда наибольший.

[Igors]

Бинарное сбалансированное с сортировкой по площади. Тот же std::set.
Операции вставки и удаления не хуже чем log2 N.
Очередь  с приоритетами - тоже подойдёт - она, в сущности, тоже дерево.

Алгоритм гарантирует, что разбиваемый полигон будет всегда наибольший.

Ну, лучше уж сказать "STL гарантирует"  Проверять не проверял но полагаю что по скорости он никак не лучше. С  log2 N все в порядке, но ведь он позовет malloc при каждом добавлении в дерево и free при каждом удалении. А по памяти памяти просто хуже потому что сожрет байт 20 на каждый нод. Конечно, для игровых моделей (до 50K полигонов) все будет работать прекрасно. Но не там где память используется "до упора". Тут даже new надо использовать аккуратно, например

polygon * p = new Polygon();  // нехорошо если полигонов действительно МНОГО
polygon * p = new Polygon[POLY_CHUNK_SIZE];  // так лучше хотя потом прийдется написать немного больше

[Winstrol]

Ну, лучше уж сказать "STL гарантирует"   Проверять не проверял но полагаю что по скорости он никак не лучше. С  log2 N все в порядке, но ведь он позовет malloc при каждом добавлении в дерево и free при каждом удалении. А по памяти памяти просто хуже потому что сожрет байт 20 на каждый нод. Конечно, для игровых моделей (до 50K полигонов) все будет работать прекрасно. Но не там где память используется "до упора". Тут даже new надо использовать аккуратно, например

priority_queue в stl по умолчанию на основа вектора сделана. Можно также пользоваться напрямую алгоритмами make_heap/push_heap/pop_heap/sort_heap поверх вектора. И, наконец, объекты с тяжелым копированием (например std::string с размером в 32 байта) в массивах хранить нецелесообразно, если предполагается тасовать элементы. Хранят указатели или умные указатели.

[Igors]

Сделал, рассказываю  

1) Данные: из стандартной библиотеки используем только функцию qsort. Работаем только списками.

struct Polygon {
  Polygon * mNext;
 .....
};

Банальное добавление в список:

p->mNext = listHead;
listHead = p;

2) Алгоритм: на каждом шаге имеется селектор - N списков, каждый из которых сортирован по убыванию. Выбор кандидата осуществляется прямым перебором (на максимум) всех "голов" N списков. После выбора голова одного из списков продвигается, если NULL - пустой список удаляется из селектора. Разбитые полигоны линкуются в выходной список outList. Если выбранный кандитат имеет меньшую площадь чем максимальный в outList, то тогда сортируем outList,  добавляем его в селектор, обнуляем outList и повторяем выбор кандидата.

3) Детали:

а) сортировка списка

- выделяем память под массив указателей
- проходим по списку и заполняем массив указателей
- сортируем массив указателей (qsort)
- проходим по массиву и заполняем mNext
- удаляем массив указателей

б) Селектор: здесь можно использовать все что угодно, на мой вкус тоже список

struct Selector {
 Selector * mPrev;
 Selector * mNext;
 Polygon * mHead;
};

4) Ну а не получится ли что N (число списков для выбора) будет расти и расти? Нет, практически N очень мало (я не смог достичь даже 10  ) Если площади всех полигонов одинаковы - то вообще 1 список который затем замещается новым. Если есть большие полигоны - то они быстро породят новые списки, но эти же списки первыми попадут под деление и будут быстро исчерпаны.

[Tonal]

Если заменить селектор на массив и отсортировать его то получим одноуровневое Б+ дерево.
Поздравляю с велосипедиком.

C std::set ты можешь определить свой аллокатор (советую Boost.Pool) и не возится руками с управлением памяти.
Ну а ежели память таки жмёт, то в priority_queue или make_heap/push_heap/pop_heap никаких лишних данных.
Кстати твой алгоритм на них элементарно переписывается.

Ну и если таки нравится всё самому, то я бы таки держал отсортированным и селектор и outList.
Тогда их не нужно на каждом цикле проходить полностью.

[Igors]

Если заменить селектор на массив и отсортировать его то получим одноуровневое Б+ дерево.
Поздравляю с велосипедиком.

C std::set ты можешь определить свой аллокатор (советую Boost.Pool) и не возится руками с управлением памяти.
Ну а ежели память таки жмёт, то в priority_queue или make_heap/push_heap/pop_heap никаких лишних данных.
Кстати твой алгоритм на них элементарно переписывается.

Ну и если таки нравится всё самому, то я бы таки держал отсортированным и селектор и outList.
Тогда их не нужно на каждом цикле проходить полностью.

Ну, в знании стандартной библиотеки мне в Вами не тягаться  Понимаю, что Вы бы сделали за час (если не меньше) то над чем я сидел несколько дней. Но зато я свой алгоритм знаю досконально, могу поручиться за скорость и не завишу от всяких has_iterator_debugging, _SECURE_SCL  и т.п. На мой взгляд "изобретать велосипед" значит "думать своей головой" и ничего плохого в этом нет