爲什麼boost.geometry.index.rtree比superliminal更慢.RTree

Question

我測試了boost.geometry.index.rtree（boost 1.59 www.boost.org）和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 version 4.4.6 20110731（Red Hat 4.4.6-4）（GCC）」，使用「-g -o2 -Wall -finline-functions」編譯器標誌。
• 使用RTREE < uint64_t中，INT，2和int64_t>

• 使用升壓如下：

  命名空間BG =升壓::幾何形狀;

  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;

結果是： superliminal.RTree 0.029s boost.geometry.index.rtree 0.12S。

Answer 1

很難說出爲什麼它會比較慢，因爲您沒有共享代碼，也沒有告知如何使用兩種R樹實現。您還沒有提供任何有關您正在存儲的數據的信息。當你比較算法或數據結構時，這些事情非常重要。

我只能猜測你正在使用Superliminar R-tree，就像在附加的測試文件中使用的一樣，所以你需要將回調函數傳入Search成員函數。我猜你正在使用Boost.Geometry R-tree，其方法與快速入門部分中的文檔中顯示的方式相同，因此您將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函數）是：

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

所以他們類似於你的，即，一個是5倍〜更快。請注意，在這兩種情況下，我都會創建一個存儲結果的容器（Superliminar的ID和Boost.Geometry的整個值）。問題是R樹不會以相同的方式使用。

優化1

讓我們嘗試通過存儲相同的結果同樣的方式來擺脫在這兩個的R-tree的使用的差異。爲了做到這一點，刪除臨時std::vector<value_t>。要使用名爲boost::function_output_iterator的函數對象實現回調替換std::back_insert_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_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-tree中有一些。編譯代碼與-DNDEBUG後的結果甚至更接近：

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

結論

在這種合成的試驗情況下，隨機數據等的結果是或多或少是相同的。再一次，對你而言，他們可能會有所不同，我不知道你在做什麼，所以我無法告訴你這是什麼問題。

這是非常簡單的用例，如果測試更復雜的用例，結果可能會不同。換句話說，我們應該描述一個真實的應用程序，看看是否有一些瓶頸。

此外Boost.Geometry R-tree的代碼更加複雜。兩種R-tree實現的接口是不同的，特別是搜索/查詢功能都需要不同的參數，而且絕大多數都是以不同的方式處理它們。編譯器可能會選擇以不同的方式優化代碼。

P.S.

使用Boost.Geometry R-tree可以使用不同的分割算法和打包算法，因此您可以在您的情況下試驗哪一種最好。要使用包裝算法，您必須將一系列值傳入rtree構造函數。對於相同的數據和使用包裝算法創建的元素數量和rtree，對於我來說，查詢時間爲0.005s。