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

我测试boost.geometry.index.rtree(在www.boost.org上提升1.59)和superliminal.RTree(http://superliminal.com/sources/sources.htm#C_Code)。

令我惊讶的是，superliminal.RTree比boost.geometry.index.rtree更快。

环境设定

将相同的空间索引数据添加到superliminal.RTree和
boost.geometry.index.rtree对象。

测试相同的空间索引查询100次并获得消耗的时间。

GCC版本是“gcc版本4.4.6 20110731(Red Hat 4.4.6-4)(GCC)”，请使用“-g -o2 -Wall -finline-functions”编译器标志。

使用RTree

升压代码

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point < int, 2, bg::cs::cartesian > point_t;
typedef bg::model::box < point_t > box_t;
typedef std::pair < box_t, uint64_t > value_t;
typedef bgi::rtree < value_t, bgi::quadratic < 8, 4 > > rtree_t;

结果是:

最佳答案

很难说出为什么它变慢了，因为您既没有共享代码，也没有告诉我们两个R-tree实现是如何使用的。您还没有提供有关要存储的数据的任何信息。当您比较算法或数据结构时，这些事情非常重要。

我只能猜测，您使用Superliminar R树的方式与附加测试文件中使用的方式相同，因此您要将回调函数传递给Search成员函数。而且我猜您正在使用Boost.Geometry R树，方法与“快速入门”部分的文档中所示的方法相同，因此您要将std::back_insert_iterator对象传递给query成员函数。因此，让我们检查一下。

#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, int, 2, int64_t> tree;

    // create the Boost.Geometry R-tree
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<int, 2, 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。在这两种情况下，都仅将ID存储在std::vector<uint64_t>中，并希望编译器将优化代码。

#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_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];
};

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, 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, int, 2, int64_t> tree;

    // create the Boost.Geometry R-tree
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;
    typedef bg::model::point<int, 2, 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;
        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树中有一些。用-DNDEBUG编译代码后，结果更加接近:

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

结论

在这种综合测试用例中，对于随机数据等，结果大致相同。同样，对于您来说，它们可能有所不同，我不知道您在做什么，所以我无法告诉您问题出在哪里。

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

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

P.S.

使用Boost.Geometry R树，可以使用不同的拆分算法和打包算法，因此您可以尝试哪种方法最适合您的情况。要使用打包算法，您必须将一系列值传递到rtree构造函数中。对于相同的数据，元素数量以及使用打包算法创建的rtree，查询时间对我来说是0.005s。

关于c++ - 为什么boost.geometry.index.rtree比superliminal.RTree慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33005712/