c – 为什么boost.geometry.index.rtree比superliminal慢.RTree

我只能猜测你使用的是Superliminar R-tree,就像它在附加的测试文件中使用的那样,所以你将回调函数传递给搜索成员函数.我猜你正在使用Boost.Geometry R-tree,就像它在“快速入门”部分的文档中所示的那样,所以你将std :: back_insert_iterator的对象传递给查询成员函数.那么我们来看看吧.

#include "RTree.h"

#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <boost/timer.hpp>

struct Rect
{
  Rect()  {}

  Rect(int a_minX,int a_minY,int a_maxX,int a_maxY)
  {
    min[0] = a_minX;
    min[1] = a_minY;

    max[0] = a_maxX;
    max[1] = a_maxY;
  }

  int min[2];
  int max[2];
};

// used with Superliminar R-tree
std::vector<uint64_t> res;
bool MySearchCallback(uint64_t id,void* arg)
{
    res.push_back(id);
    return true;
}

int main()
{
    // randomize rectangles
    std::vector<Rect> rects;
    for (size_t i = 0 ; i < 300000 ; ++i)
    {
        int min_x = rand() % 10000;
        int min_y = rand() % 10000;
        int w = 1 + rand() % 100;
        int h = 1 + rand() % 100;
        rects.push_back(Rect(min_x,min_y,min_x+w,min_y+h));
    }

    // create the rectangle passed into the query
    Rect search_rect(4000,4000,6000,6000);

    // create the Superliminar R-tree
    RTree<uint64_t,int64_t> tree;

    // create the Boost.Geometry R-tree
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<int,bg::cs::cartesian> point_t;
    typedef bg::model::box<point_t> box_t;
    typedef std::pair<box_t,uint64_t> value_t;
    bgi::rtree<value_t,bgi::quadratic<8,4> > bg_tree;

    // Insert values
    for(size_t i = 0; i < rects.size(); i++)
    {
        Rect const& r = rects[i];
        tree.Insert(r.min,r.max,i);

        box_t b(point_t(r.min[0],r.min[1]),point_t(r.max[0],r.max[1]));
        bg_tree.insert(value_t(b,i));
    }

    // test Rtree
    {
        int sum = 0;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            res.clear();
            sum += tree.Search(search_rect.min,search_rect.max,MySearchCallback,NULL);
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }

    // test BG Rtree
    {
        box_t search_box(
            point_t(search_rect.min[0],search_rect.min[1]),point_t(search_rect.max[0],search_rect.max[1]));
        size_t sum = 0;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            std::vector<value_t> res;
            sum += bg_tree.query(bgi::intersects(search_box),std::back_inserter(res));
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }
}

结果(使用GCC 4.8 -O2 -finline-functions)是：

0.014s for Superliminar R-tree
0.072s for Boost.Geometry R-tree

所以它们与你的相似,即一个快5倍.请注意,在这两种情况下,我都创建了一个存储结果的容器(Superliminar的ID和Boost.Geometry的整个值).问题是R树的使用方式不同.

优化1

让我们试着通过以相同的方式存储相同的结果来消除两个R树的使用差异.为了做到这一点,删除临时std :: vector< value_t>.要实现回调,请将std :: back_insert_iterator替换为名为boost :: function_output_iterator的函数对象.在这两种情况下,只存储std :: vector< uint64_t>中的ID.并希望编译器优化代码.

#include "RTree.h"

#include <vector>

#include <boost/function_output_iterator.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

#include <boost/timer.hpp>

struct Rect
{
  Rect()  {}

  Rect(int a_minX,int a_maxY)
  {
    min[0] = a_minX;
    min[1] = a_minY;

    max[0] = a_maxX;
    max[1] = a_maxY;
  }

  int min[2];
  int max[2];
};

std::vector<uint64_t> res;

// used with Superliminar R-tree
bool MySearchCallback(uint64_t id,void* arg)
{
    res.push_back(id);
    return true;
}

// used with Boost.Geometry R-tree
struct MySearchCallback2
{
    template <typename Value>
    void operator()(Value const& v)
    {
        res.push_back(v.second);
    }
};

int main()
{
    // randomize rectangles
    std::vector<Rect> rects;
    for (size_t i = 0 ; i < 300000 ; ++i)
    {
        int min_x = rand() % 10000;
        int min_y = rand() % 10000;
        int w = 1 + rand() % 100;
        int h = 1 + rand() % 100;
        rects.push_back(Rect(min_x,search_rect.max[1]));
        size_t sum = 0;
        MySearchCallback2 callback;
        boost::timer t;
        for (size_t i = 0 ; i < 100 ; ++i)
        {
            res.clear();
            sum += bg_tree.query(bgi::intersects(search_box),boost::make_function_output_iterator(callback));
        }
        double s = t.elapsed();
        std::cout << s << " " << sum << std::endl;
    }
}

在这种情况下,结果是：

0.014s for Superliminar R-tree
0.033s for Boost.Geometry R-tree

优化2

可以做的另一件事是禁用断言. Boost.Geometry R-tree中有一些.用-DNDEBUG编译代码后,结果更接近：

0.014s for Superliminar R-tree
0.015s for Boost.Geometry R-tree

结论

在该综合测试案例中,对于随机数据等,结果或多或少相同.再说一次,对你来说,他们可能会有所不同,我不知道你在做什么,所以我无法告诉你这是什么问题.

这是一个非常简单的用例,如果测试更复杂的用例,结果可能会有所不同.换句话说,应该分析一个真实的应用程序,看看是否存在一些瓶颈.

此外,Boost.Geometry R-tree的代码要复杂得多.两个R树实现的接口是不同的,特别是搜索/查询功能都需要不同的参数,并且大多数肯定以不同的方式处理它们.编译器可以选择以不同方式优化代码.

附：

使用Boost.Geometry R-tree,可以使用不同的分割算法和打包算法,以便您可以尝试哪种方法最适合您的情况.要使用打包算法,您必须将一系列值传递给rtree构造函数.对于相同的数据和元素的数量以及使用打包算法创建的rtree,查询时间对我来说是0.005秒.