可憐的樹增加性能

Question

我正在寫一個樹容器（只是爲了理解和培訓），現在我得到了第一個和非常基本的方法來添加元素到樹中。

這是知道我的樹碼。現在沒有析構函數，沒有清理和元素訪問。

template <class T> class set 
    { 
    public: 
     struct Node 
     { 
      Node(const T& val) 
       : left(0), right(0), value(val) 
      {} 

      Node* left; 
      Node* right; 
      T  value; 
     }; 

     set() 
     {} 

     template <class T> void add(const T& value) 
     { 
      if (m_Root == nullptr) 
      { 
       m_Root = new Node(value); 
      } 

      Node* next = nullptr; 
      Node* current = m_Root; 

      do 
      { 
       if (next != nullptr) 
       { 
        current = next; 
       } 

       next = value >= current->value ? current->left : current->right; 
      } while (next != nullptr); 

      value >= current->value ? current->left = new Node(value) : current->right = new Node(value); 
     } 

    private: 
     Node* m_Root; 
    }; 

好了，現在我測試對一個std ::設置有獨特的平衡（高）值的插入性能的附加性能，得出的結論是，性能很簡單可怕。

是否有一個原因，爲什麼該集插入值快得多，以及什麼樣的方式來改善我的方法的插入性能？ （我知道可能有更好的樹模型，但據我所知，插入性能應該在大多數樹模型之間靠近）。

在i5 4570股票時鐘下， std :: set需要0.013s才能添加1000000個int16值。 我的設置需要4.5s來添加相同的值。

這個差別從哪裏來？

更新：

還好吧，這裏是我的testcode：

int main() 
{ 
    int n = 1000000; 
    test::set<test::int16> mset; //my set 
    std::set<test::int16> sset; //std set 
    std::timer  timer;   //simple wrapper for clock() 

    test::random_engine engine(0, 500000); //simple wrapper for rand() and yes, it's seeded, and yes I am aware that an int16 will overflow 

    std::set<test::int16> values; //Set of values to ensure unique values 

    bool flip = false; 
    for (int i = 0; n > i; ++i) 
    { 
     values.insert(flip ? engine.generate() : 0 - engine.generate()); 
     flip = !flip; //ensure that we get high and low values and no straight line, but at least 2 paths 
    } 

    timer.start(); 
    for (std::set<test::int16>::iterator it = values.begin(); values.end() != it; ++it) 
    { 
     mset.add(*it); 
    } 
    timer.stop(); 

    std::cout << timer.totalTime() << "s for mset\n"; 

    timer.reset(); 

    timer.start(); 
    for (std::set<test::int16>::iterator it = values.begin(); values.end() != it; ++it) 
    { 
     sset.insert(*it); 
    } 
    timer.stop(); 

    std::cout << timer.totalTime() << "s for std\n"; 
} 

設定就不會在每次值存儲由於dubicates但兩個容器會得到相同的高數量和相同的價值觀爲了確保代表性的結果。我知道測試可能會更準確，但它應該給出一些可比數字。

Answer 1

兩個明顯的區別是：

用於 std::set紅黑樹（可能）

1. 重新平衡自己穿上最壞情況下的行爲的上限，正是因爲戴爾說。

   如果出現這種問題，那麼在繪製N（插入節點的數量）和每次插入時間時應該會看到它。你也可以跟蹤樹的深度（至少出於調試的目的），並繪製即針對N.

2. 標準容器使用分配器這可能做一些事情比new單獨荷蘭國際集團的每個節點聰明。您可以嘗試在自己的容器中使用std::allocator以查看是否有重大改進。

---

編輯1，如果你實現了一個池分配器，這是本來應該在問題相關的信息。

編輯2現在你已經添加了你的測試代碼，這是一個明顯的問題，這意味着你的設置總會有最差的插入性能。 您對輸入值進行了預先排序！std::set是一個有序的容器，因此將在那裏先保證你總是在增加值順序插入，這樣你的樹你的價值（不自平衡）退化爲昂貴的鏈表，你的刀片是總是線性而而不是對數時間。

您可以通過在vector存儲你的價值觀，而不是（只使用set檢測碰撞），或者使用unordered_set無需預先排序刪除重複驗證這一點。

Answer 2

std::set執行通常使用red-black tree數據結構。這是一個自我平衡的二叉搜索樹，在最壞的情況下（這是標準要求的），操作保證爲O(log(n))時間複雜度。您使用簡單的二叉搜索樹和O(n)最壞情況插入操作。

如果插入唯一的隨機值，這種差異看起來很可疑。但是不要忘記，隨機性不會使你的平衡樹，樹的高度可能會遠大於log(n)

編輯

看來我發現你的代碼的主要問題。您存儲在std::set中的所有生成值。之後，您將按照升序將它們添加到集合中。這會降低您的設置到鏈接列表。