Более быстрые вложенные циклы для десятков тысяч частиц

Question

Я провожу небольшое исследование изобразительного искусства в среде Unity. Я пытаюсь добиться чего-то очень похожего на рост дифференциальной линии , как описано здесь , но меня больше всего беспокоит то, что где-то в алгоритме каждый узел должен проверять каждый другой узел, чтобы увидеть, насколько он близок, и построить массив сил отталкивания от всех этих близких частиц. 1010 * Как только я запускаю игру, все падает до менее 1 кадра в секунду, и я понимаю, что вложенный l oop - это то место, откуда оно исходит из-за сложности n ^ n. Я изучал реализации Octree / KdTree, но не могу найти объясненный код. Есть ли другие маршруты? Больше, чем один ? Можно ли комбинировать? Большое спасибо

Answer 1

Вычисление точек на расстоянии для каждой точки составляет O (n ^ 2), поэтому не так уж странно, что производительность падает, если количество частиц велико. Но это довольно легко можно улучшить. Есть несколько вариантов структур поиска, которые можно использовать:

• 3D сетка. Это должно быть просто реализовать, просто создайте трехмерный массив списков. Выберите подходящий размер ящика, чтобы у вас было фиксированное количество ячеек для перебора. Основным недостатком этого является использование памяти, оно будет более значительным, если в вашей симуляции есть большие пустоты без частиц.
• Редкое октодерево. Основным преимуществом перед сеткой будет лучшее использование памяти, если точки расположены неравномерно. Также было бы лучше масштабироваться, если вам нужно искать произвольное расстояние. Обратной стороной будет более сложная реализация.
• KdTree. Это довольно хорошая структура данных, поскольку она использует довольно мало памяти, может быть реализована с непрерывной памятью и хорошо масштабируется. Одним из недостатков является то, что трудно справиться со сменой позиций. Реализация также более сложна, чем сетка.

Для сетки или Octree можно было бы перемещать точки между ячейками. Для kd-дерева, вероятно, было бы лучше перестроить дерево. Любой из вариантов должен сократить время поиска с O (N ^ 2) до O (n log n).

Учитывая контекст вашего вопроса, я бы рекомендовал начать с простой 3D-сетки. Если этого недостаточно, я бы подумал об использовании дерева kd. Я бы избегал комбинирования структур данных, если для этого нет какой-либо конкретной c причины. Octrees и kdtrees должны достаточно хорошо масштабироваться.

Я бы рекомендовал попробовать некоторые инструменты профилирования , чтобы проверить, что на самом деле требует времени. Я также рекомендовал бы настроить некоторую контролируемую среду для запуска алгоритма на известном наборе данных и измерения времени. Бенчмарк. Net - золотой стандарт, но простой секундомер должен быть достаточно хорош при измерении больших изменений.

Также должна быть некоторая возможность для микрооптимизации. Избегайте создания списков в жестком l oop, при необходимости создайте список, который будет использоваться повторно. Избегайте повторных операций. Избегайте дорогостоящих операций. Предпочитайте массивы и списки другим коллекциям, поскольку среда выполнения имеет для них особую оптимизацию. Предпочитайте for вместо foreach, поскольку первое может избежать создания объекта итератора.

Answer 2

Вам следует подумать об использовании for вместо foreach для списков, как объяснено, например, здесь при кодировании для повышения производительности. Тем не менее, я думаю, что ваша проблема является скорее структурной, чем связанной с такими деталями.

Я бы посоветовал вам взглянуть на Quadtrees , например, на эту реализацию чтобы разделить общую площадь на сегменты и связать каждую частицу с сегментом. Чтобы найти соседей, вам достаточно пройти через дерево.