logo标签列表

KD树，缓慢的树构建

c++nearest-neighborkdtree
3
我正在尝试构建KD树（静态情况）。我们假设点在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; 
 }
}
KDList类型如何定义？ - Björn Pollex
@Space: typedef std::vector<Point2D> KDList; @空间：typedef std::vector<Point2D> KDList; - Ian
Points2DList 是如何定义的？ - Björn Pollex
@Space类似于KDList，但它存储一些拓扑关系。因此，项目在KDList上移动。 - Ian
4个回答
5
寻找中位数的排序可能是最糟糕的罪魁祸首，因为它的时间复杂度是O(nlogn)，而这个问题可以在O(n)的时间内解决。您应该使用nth_element来代替：http://www.cplusplus.com/reference/algorithm/nth_element/。这将平均线性时间找到中位数，之后您可以在线性时间内拆分向量。
向量的内存管理也可能需要很长时间，特别是对于大型向量，因为每次向量的大小加倍时，所有元素都必须移动。您可以使用向量的reserve方法来为新创建的节点中的向量保留恰好足够的空间，因此它们不需要随着push_back添加新内容而动态增加。
如果您绝对需要最佳性能，则应使用较低级别的代码，放弃向量并代之以保留普通数组。Nth element或“选择”算法是readily available的，而且自己编写也不太难：http://en.wikipedia.org/wiki/Selection_algorithm。
3

优化kd-tree的一些提示：

  • 使用线性时间中位数查找算法，如QuickSelect。
  • 避免实际使用“节点”对象。您可以仅使用点存储整个树，不添加任何其他信息。基本上只是通过对对象数组进行排序来完成。然后根节点将在中间。将根节点放在首位，然后使用堆布局可能更适合CPU内存缓存查询时间，但更加棘手。
3
并不是对你的问题回答，但我强烈推荐去看看 http://ompf.org/forum/ 这个论坛。他们在各种情况下都有很好的快速kd-tree构建讨论。也许你会在那里找到一些灵感。 编辑：
OMPF论坛已经关闭，不过目前有一个直接的替代品可用于http://ompf2.com/。
1
就像我说的那样，你也许不会直接在那里找到答案。但是如果你积极参与论坛并在那里提出问题，很可能会得到帮助你解决问题的回复。如果有一个论坛详细讨论KD树或其他层次结构、它们的属性、快速构建方法等等，那就是那个论坛。 - Bart
@mkb 确实如此。我已经更新了答案，并提供了 Jacco Bikker 在 NHVT 上的替代论坛。 - Bart
1
你的第一个问题是为了找到中位数而进行排序。这几乎总是K-d树构建的瓶颈，并且在这里使用更有效的算法将带来真正的收益。
然而，您每次拆分时也会构造一对可变大小的向量并转移元素。
在这里，我建议使用好老式的单链表。链表之美在于，您可以通过仅更改next指针以指向子节点的根指针而不是父节点的指针，将元素从父节点传输到子节点。
这意味着在构建过程中没有堆开销用于将元素从父节点传输到子节点，仅用于聚合要插入到根的初始元素列表。这也应该起到奇效，但如果您想更快，可以使用固定的分配器为链表（以及树）有效地分配节点并提高连续性/缓存命中率。
最后但同样重要的是，如果您参与需要使用K-d树的密集计算任务，则需要启用性能分析器。测量您的代码，您将看到导致问题的原因以及确切的时间分布。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接