KD дерево, медленное дерево
Я пытаюсь построить KD Tree (статический случай). Мы предполагаем, что точки отсортированы по координатам x и y.
Для равномерной глубины рекурсии набор разделяется на два подмножества с вертикальной линией, проходящей через медианную координату x.
Для нечетной глубины рекурсии набор разбивается на два подмножества с горизонтальной линией, проходящей через медиану y координату.
Медиана может быть определена из отсортированного набора по координате x / y. Этот шаг я делаю перед каждым разбиением набора. И я думаю, что это вызывает медленное строительство дерева.
- Пожалуйста, не могли бы вы помочь мне проверить и оптимизировать код?
- Я не могу найти k-го ближайшего соседа, кто-нибудь может мне помочь с кодом?
Большое спасибо за вашу помощь и терпение...
Пожалуйста, посмотрите пример кода:
class KDNode
{
private:
Point2D *data;
KDNode *left;
KDNode *right;
....
};
void KDTree::createKDTree(Points2DList *pl)
{
//Create list
KDList kd_list;
//Create KD list (all input points)
for (unsigned int i = 0; i < pl->size(); i++)
{
kd_list.push_back((*pl)[i]);
}
//Sort points by x
std::sort(kd_list.begin(), kd_list.end(), sortPoints2DByY());
//Build KD Tree
root = buildKDTree(&kd_list, 1);
}
KDNode * KDTree::buildKDTree(KDList *kd_list, const unsigned int depth)
{
//Build KD tree
const unsigned int n = kd_list->size();
//No leaf will be built
if (n == 0)
{
return NULL;
}
//Only one point: create leaf of KD Tree
else if (n == 1)
{
//Create one leaft
return new KDNode(new Point2D ((*kd_list)[0]));
}
//At least 2 points: create one leaf, split tree into left and right subtree
else
{
//New KD node
KDNode *node = NULL;
//Get median index
const unsigned int median_index = n/2;
//Create new KD Lists
KDList kd_list1, kd_list2;
//The depth is even, process by x coordinate
if (depth%2 == 0)
{
//Create new median node
node = new KDNode(new Point2D( (*kd_list)[median_index]));
//Split list
for (unsigned int i = 0; i < n; i++)
{
//Geta actual point
Point2D *p = &(*kd_list)[i];
//Add point to the first list: x < median.x
if (p->getX() < (*kd_list)[median_index].getX())
{
kd_list1.push_back(*p);
}
//Add point to the second list: x > median.x
else if (p->getX() > (*kd_list)[median_index].getX())
{
kd_list2.push_back(*p);
}
}
//Sort points by y for the next recursion step: slow construction of the tree???
std::sort(kd_list1.begin(), kd_list1.end(), sortPoints2DByY());
std::sort(kd_list2.begin(), kd_list2.end(), sortPoints2DByY());
}
//The depth is odd, process by y coordinates
else
{
//Create new median node
node = new KDNode(new Point2D((*kd_list)[median_index]));
//Split list
for (unsigned int i = 0; i < n; i++)
{
//Geta actual point
Point2D *p = &(*kd_list)[i];
//Add point to the first list: y < median.y
if (p->getY() < (*kd_list)[median_index].getY())
{
kd_list1.push_back(*p);
}
//Add point to the second list: y < median.y
else if (p->getY() >(*kd_list)[median_index].getY())
{
kd_list2.push_back(*p);
}
}
//Sort points by x for the next recursion step: slow construction of the tree???
std::sort(kd_list1.begin(), kd_list1.end(), sortPoints2DByX());
std::sort(kd_list2.begin(), kd_list2.end(), sortPoints2DByX());
}
//Build left subtree
node->setLeft( buildKDTree(&kd_list1, depth +1 ) );
//Build right subtree
node->setRight( buildKDTree(&kd_list2, depth + 1 ) );
//Return new node
return node;
}
}
4 ответа
Сортировка по медиане, вероятно, является наихудшим виновником здесь, поскольку это O(nlogn), в то время как проблема разрешима за O(n) времени. Вместо этого вы должны использовать nth_element: http://www.cplusplus.com/reference/algorithm/nth_element/. Это позволит найти медиану в среднем по линейному времени, после чего вы можете разделить вектор по линейному времени.
Управление памятью в векторе также может занимать много времени, особенно с большими векторами, поскольку каждый раз, когда размер вектора удваивается, все элементы необходимо перемещать. Вы можете использовать резервный метод vector, чтобы зарезервировать достаточно места для векторов во вновь создаваемых узлах, поэтому они не должны увеличиваться динамически, так как новые вещи добавляются с помощью push_back.
И если вам абсолютно необходима лучшая производительность, вы должны использовать код более низкого уровня, покончив с вектором и зарезервировав вместо него простые массивы. Алгоритм N-го элемента или "выбора" легко доступны, и их не сложно написать самостоятельно: http://en.wikipedia.org/wiki/Selection_algorithm
На самом деле это не ответ на ваши вопросы, но я очень рекомендую форум по адресу http://ompf.org/forum/ У них есть отличные обсуждения быстрых конструкций kd-дерева в различных контекстах. Возможно, вы найдете там вдохновение.
Редактировать:
С тех пор форумы OMPF прекратили работу, хотя прямая замена в настоящее время доступна по адресу http://ompf2.com/
Некоторые советы по оптимизации дерева kd:
- Используйте алгоритм поиска медианы линейного времени, такой как QuickSelect.
- Избегайте использования объектов типа "узел". Вы можете хранить все дерево, используя только точки, с нулевой дополнительной информацией. По сути, просто сортировка массива объектов. Корневой узел будет тогда посередине. Перестановка, которая ставит корень первым, а затем использует компоновку кучи, вероятно, будет лучше для кэш-памяти ЦП во время запроса, но сложнее построить.
Ваш первый преступник сортирует, чтобы найти медиану. Это почти всегда является узким местом для построения дерева Kd, и использование здесь более эффективных алгоритмов действительно окупится.
Однако вы также создаете пару векторов переменного размера каждый раз, когда разбиваете и переносите в них элементы.
Здесь я рекомендую хороший старый односвязный список. Прелесть связанного списка в том, что вы можете передавать элементы от родителя к потомку, просто изменяя next
указатели, указывающие на корневой указатель дочернего элемента вместо родительского.
Это означает, что во время построения вообще не нужно загружать кучу ресурсов для передачи элементов из родительских узлов в дочерние узлы, а только для агрегирования начального списка элементов для вставки в корень. Это также должно творить чудеса, но если вы хотите еще быстрее, вы можете использовать фиксированный распределитель, чтобы эффективно распределять узлы для связанного списка (а также для дерева) и с лучшими совпадениями / попаданиями в кэш.
И последнее, но не менее важное: если вы участвуете в интенсивных вычислительных задачах, требующих деревьев Kd, вам нужен профилировщик. Измерьте свой код, и вы увидите, что именно лежит у виновника, и с точным распределением времени.