清除高效范围树实现 [英] Clear And Efficient Range Tree Implementation

问题描述

我在做这个项目，我必须寻找在三维空间中的物体，而且效率是一个巨大的关注，我觉得范围树是完美的我想要做的，区间树也将工作，但我不打算从树中删除任何东西，有一次我在三维空间中添加的每个对象，我将只使用结构做搜索。

I'm working on this project where I have to search for objects in 3d space, and efficiency is a huge concern, I think Range Tree is perfect for what I'm trying to do, Interval Tree would also work but I'm not going to delete anything from the tree, once I add every object in 3D space, I'll only use the structure to do a search.

下面是如何，我将使用结构：

Here's how I'm going to use the structure:

让说，我有一个数组（姑且称之为 queryArr ）对象（〜10,000个对象），每​​个对象有3个参数（X，Y，Z）我还有一个非常大阵（让我们称之为 totalArr ）对象（> 500万对象）。

Let say that I have an array(let's call it queryArr) of objects (~ 10,000 objects) each objects have 3 parameter (x,y,z) I have another very large array(let's call it totalArr) of objects ( > 5,000,000 objects).

我试图在这里做的是给定的元素 queryArr ，找到最相似的（或 totalArr 相同的元素），在某些情况下会出现一个与在相同的参数对象的 totalArr ，但在大多数情况下，不会有一个对象相同的参数。

What I'm trying to do here is given element of queryArr, find the most similar(or the same element in totalArr) In some cases there will be an object with the same parameters in totalArr, but in most cases, there won't be an object with same parameters.

因此​​，我将在间搜索所有值（x + 10，Y + 10，Z + 10）和（x-10，Y-10，Z-10）。如果它不产生任何结果，我会用x，y，z 2，然后再试一次，直到它产生了一定的成效。

So, I'll search all the values in between (x+10,y+10,z+10) and (x-10,y-10,z-10). If it doesn't yield any result, I'll multiply x,y,z by 2 and try again until it yields some results.

这样做的最简单的方法是一种天真的搜索方法，这将有复杂性为O（N * M）（N = queryArr，M = SIE totalArr的大小），但这种方法是非常缓慢和愚蠢的。

The simplest way of doing this is a naive search method, which will have complexity of O(N*M) (N = size of queryArr, M = sie of totalArr) but this method is incredibly slow and dumb.

我觉得范围树的是要走的路，但我从来没有实现一个自己，我不太明白是怎么范围树适用于尺寸大于2，因此，没有人知道一个良好的执行范围内的树木？我相信，如果我能有一个源$ C ​​$ C，我能够理解他们真正是如何工作的。

I think Range Tree's is the way to go, but I have never implemented one myself and I don't quite understand how the range tree works on dimensions bigger than 2. So does anyone know a good implementation of the range trees? I believe if I can have a source code, I'll be able to understand how they really work.

顺便说一句，如果你想，有一个比范围树好结构完成这个任务，让我知道我很开放的建议。 （我已经考虑KD树和区间树）

By the way if you think, there is a better structure than Range Tree for this task, let me know I'm open to suggestions. (I have already considered kd-Trees and Interval trees)

谢谢

推荐答案

我刚才读维基百科的文章。让我们看看我是否可以写一个n维的范围树。因为任何值得做的3个维度是值得做的N。

I just read the wikipedia article. Lets see if I can write an n dimensional range tree. Because anything worth doing in 3 dimensions is worth doing in n.

所以n维范围树的基本部分是，它可以在低维范围树的角度来递归定义

So the basic part of an n-dimensional range tree is that it can be recursively defined in terms of lower dimensional range trees.

某些属性类与相对通用的值类型的工作。专门 element_properties＆LT; T＆GT; 设置标量类型无论你的N维值，并专注获取LT; I＆GT;（T常量和放大器;）获得我您第n维价值维度。

Some property classes to work with relatively generic value types. Specialize element_properties<T> to set the scalar type of whatever your n-dimensional value is, and specialize get<i>(T const&) to get the ith dimension of your n-dimensional value.

#include <memory>
#include <cstddef>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>

void Assert(bool test) {
  if (!test)
  {
    std::cout << "Assert failed" << std::endl;
    exit(-1);
  }
}
template<typename... Args>
struct Print {
  static void Do(Args... args) {}
};
template<typename Arg, typename... Tail>
struct Print<Arg, Tail...> {
  static void Do(Arg arg, Tail... args) {
      std::cout << arg;
      Print<Tail...>::Do(args...);
  }
};
template<typename... Args>
void Debug(Args... args) {
    std::cout << "DEBUG:[";
    Print<Args...>::Do(args...);
    std::cout << "]\n";
}

template<typename T>
struct element_properties {
  typedef typename T::value_type value_type;
};
template<>
struct element_properties<int> {
  typedef int value_type;
};
template<size_t d, typename T>
typename element_properties<T>::value_type get( T const & t );

template<size_t d>
typename element_properties<int>::value_type get( int i ) { return i; }

template<size_t d, typename U, typename A>
typename element_properties<std::vector<U,A>>::value_type get( std::vector<U,A> const& v) {
  return v[d];
}

template<typename T, size_t dim, typename Order = std::less< typename element_properties<T>::value_type> >
struct range_tree {
  typedef typename element_properties<T>::value_type value_type;
  struct sorter {
    bool operator()( T const& left, T const& right ) const {
      return Order()( get<dim-1>(left), get<dim-1>(right) );
    }
  };
  struct printer {
    std::string operator()( T const& t ) const {
      std::string retval = "[ ";
      retval += print_elements( t );
      retval += "]";
      return retval;
    }
    std::string print_elements( T const& t ) const {
      std::stringstream ss;
      typedef typename range_tree<T, dim-1, Order>::printer next_printer;
      ss << next_printer().print_elements(t);
      ss << get<dim-1>(t) << " ";
      return ss.str();
    }
  };
  template<typename Iterator>
  range_tree( Iterator begin, Iterator end ) {
    std::sort( begin, end, sorter() );
    root.reset( new tree_node( begin, end ) );
  }

  template<size_t n, typename Func>
  void walk(Func f) const {
      if (root) root->walk<n>(f);
  }
  template<size_t n, typename Func>
  void walk(Func f) {
      if (root) root->walk<n>(f);
  }
  struct tree_node {
    std::unique_ptr< range_tree<T, dim-1, Order> > subtree;
    T value;
    template<size_t n, typename Func>
    void walk(Func f) const {
      if (n==dim && !left && !right)
        f(value);
      if (left)
        left->walk<n>(f);
      if (right)
        right->walk<n>(f);
      if (subtree)
        subtree->walk<n>(f);
    }
    template<size_t n, typename Func>
    void walk(Func f) {
      if (n==dim && !left && !right)
        f(value);
      if (left)
        left->walk<n>(f);
      if (right)
        right->walk<n>(f);
      if (subtree)
        subtree->walk<n>(f);
    }
    void find_path( T const& t, std::vector< tree_node const* >& vec ) {
      vec.push_back(this);
      if ( sorter()(t, value) ) {
        if (left)
          left->find_path(t, vec);
      } else if (sorter()(value, t)) {
        if (right)
          right->find_path(t, vec);
      } else {
        // found it!
        return;
      }
    }
    std::vector< tree_node const* > range_search( T const& left, T const& right )
    {
      std::vector<tree_node const*> left_path;
      std::vector<tree_node const*> right_path;
      find_path( left, left_path );
      find_path( right, right_path );
      // erase common path:
      {
        auto it1 = left_path.begin();
        auto it2 = right_path.begin();
        for( ; it1 != left_path.end() && it2 != right_path.end(); ++it1, ++it2) {
          if (*it1 != *it2)
          {
            Debug( "Different: ", printer()( (*it1)->value ), ", ", printer()( (*it2)->value ) );
            break;
          }

          Debug( "Identical: ", printer()( (*it1)->value ), ", ", printer()( (*it2)->value ) );
        }
        // remove identical prefixes:
        if (it2 == right_path.end() && it2 != right_path.begin())
            --it2;
        if (it1 == left_path.end() && it1 != left_path.begin())
            --it1;
        right_path.erase( right_path.begin(), it2 );
        left_path.erase( left_path.begin(), it1 );
      }
      for (auto it = left_path.begin(); it != left_path.end(); ++it) {
        if (*it && (*it)->right) {
          Debug( "Has right child: ", printer()( (*it)->value ) );
          *it = (*it)->right.get();
          Debug( "It is: ", printer()( (*it)->value ) );
        } else {
          Debug( "Has no right child: ", printer()( (*it)->value ) );
          if ( sorter()( (*it)->value, left) || sorter()( right, (*it)->value) ) {
            Debug( printer()( (*it)->value ), "<", printer()( left ), " so erased" );
            *it = 0;
          }
        }
      }
      for (auto it = right_path.begin(); it != right_path.end(); ++it) {
        if (*it && (*it)->left) {
          Debug( "Has left child: ", printer()( (*it)->value ) );
          *it = (*it)->left.get();
          Debug( "It is: ", printer()( (*it)->value ) );
        } else {
          Debug( "Has no left child: ", printer()( (*it)->value ) );
          if ( sorter()( (*it)->value, left) || sorter()( right, (*it)->value) ) {
            Debug( printer()( right ), "<", printer()( (*it)->value ), " so erased" );
            *it = 0;
          }
        }
      }
      left_path.insert( left_path.end(), right_path.begin(), right_path.end() );
      // remove duds and duplicates:
      auto highwater = std::remove_if( left_path.begin(), left_path.end(), []( tree_node const* n) { return n==0; } );
      std::sort( left_path.begin(), highwater );
      left_path.erase( std::unique( left_path.begin(), highwater ), left_path.end() );
      return left_path;
    }

    std::unique_ptr<tree_node> left;
    std::unique_ptr<tree_node> right;
    // rounds down:
    template<typename Iterator>
    static Iterator middle( Iterator begin, Iterator end ) {
      return (end-begin-1)/2 + begin ;
    }
    template<typename Iterator>
    tree_node( Iterator begin, Iterator end ):value(*middle(begin,end)) {
      Debug( "Inserted ", get<dim-1>(value), " at level ", dim );
      Iterator mid = middle(begin,end);
      Assert( begin != end );
      if (begin +1 != end) { // not a leaf
        Debug( "Not a leaf at level ", dim );
        ++mid; // so *mid was the last element in the left sub tree 
        Assert(mid!=begin);
        Assert(mid!=end);
        left.reset( new tree_node( begin, mid ) );
        right.reset( new tree_node( mid, end ) );
      } else {
        Debug( "Leaf at level ", dim );
      }
      if (dim > 0) {
        subtree.reset( new range_tree<T, dim-1, Order>( begin, end ) );
      }
    }
  };
  std::unique_ptr<tree_node> root;
};
// makes the code above a tad easier:
template<typename T, typename Order >
struct range_tree< T, 0, Order > {
  typedef typename element_properties<T>::value_type value_type;
  struct printer { template<typename Unused>std::string print_elements(Unused const&) {return std::string();} };
  range_tree(...) {};
  struct tree_node {}; // maybe some stub functions in here
  template<size_t n, typename Func>
  void walk(Func f) {}
};

int main() {
  typedef std::vector<int> vector_type;
  std::vector<vector_type> test;
  test.push_back( vector_type{5,2} );
  test.push_back( vector_type{2,3} );
  range_tree< vector_type, 2 > tree( test.begin(), test.end() );
  std::cout << "Walking dim 2:";
  auto print_node = [](vector_type const& v){ std::cout << "(" << v[0] << "," << v[1] << ")"; };
  tree.walk<2>( print_node );
  std::cout << "\nWalking dim 1:";
  tree.walk<1>( print_node );
  std::cout << "\n";

  std::cout << "Range search from {3,3} to {10,10}\n";
  auto nodes = tree.root->range_search( vector_type{3,3}, vector_type{10,10} );
  for (auto it = nodes.begin(); it != nodes.end(); ++it)
  {
    (*it)->walk<2>( print_node );
  }
}

这是pretty的该死接近一个n维的范围树。在0维度树自然包含什么。

which is pretty damn close to an n-dimensional range tree. The 0 dimension tree naturally contains nothing.

基础设施（在时间一维）搜索现在已被添加。您可以手动执行递归到较低的层面，或者向上，以便在 range_search 总是返回级别1 tree_node * 取值

Basic facilities to search (in one dimension at a time) have been added now. You can manually do the recursions into lower dimensions, or it up so that the range_search always returns level 1 tree_node*s.

这篇关于清除高效范围树实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！