Как определить оптимальную мощность для подразделения Quadtree?

Я создал симуляцию стаи, используя алгоритм Боида, и интегрировал дерево квадрантов для оптимизации. Боиды вставляются в дерево квадрантов, если дерево квадрантов еще не достигло своей емкости boid. Если дерево квадрантов достигло своего предела, оно будет разделено на более мелкие деревья квадрантов, а оставшиеся boids попытаются снова вставить в это дерево, рекурсивно.

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

Вы можете просматривать сайт в реальном времени здесь или в исходном коде здесь, если это уместно.


optimization algorithm simulation big-o quadtree
person Michael Moreno    schedule 29.04.2021    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Реализация. Крайним случаем может быть использование обработки GPU для сравнения записей. Если вы поддерживаете это, наличие очень больших узлов, потенциально только одного узла, содержащего все записи, может быть быстрее, чем любое другое решение.

Аппаратное обеспечение. Размер кэша и скорость шины будут играть большую роль, а также в зависимости от того, сколько памяти потребляет каждый узел и каждая запись. Доступ к подузлу, который не кэшируется, очевидно, дорог, поэтому вы можете увеличить размер узлов, чтобы уменьшить обход подузла. -› Возвращаясь к реализации, хранение всего дерева квадрантов в непрерывном сегменте памяти может быть очень полезным.

Характеристики данных. Кластеризованные данные. Сильно кластеризованные данные могут отрицательно сказаться на производительности, поскольку дерево может стать очень глубоким. В этом случае может помочь увеличение размера узла. Большие объемы данных будут означать, что вы можете преодолеть порог, когда все помещается в кеш. В этом случае увеличение размера узлов сэкономит память, потому что у вас будет меньше узлов, и все может снова поместиться в кеш.

По моему опыту я обнаружил, что 10-50 записей на узел дают наилучшую производительность для разных наборов данных.

Если вы часто обновляете свое дерево, вы можете определить порог, чтобы избежать «мерцания» и частого слияния/разделения узлов. т.е. разделяйте узлы с ›25 записями, но объединяйте их только при получении менее 15 записей.

Если вас интересует структура, подобная дереву квадрантов, которая позволяет избежать вырожденных «глубоких» деревьев квадрантов, взгляните на мое PH-Tree. . Он структурирован как дерево квадрантов, но работает на уровне битов, поэтому максимальная глубина строго ограничена 64 или 32, в зависимости от того, сколько битов у ваших данных. На практике глубина редко превышает 10 уровней или около того, даже для очень плотных данных. Примечание. Простое PH-дерево представляет собой "карту" ключ-значение в том смысле, что каждая координата (=ключ) может иметь только одну запись (=значение). Это означает, что вам нужно хранить списки или наборы записей на случай, если вы ожидаете более одной записи для любой заданной координаты.

person TilmannZ    schedule 01.05.2021