可怜的树增加性能

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中的所有生成值。之后，您将按照升序将它们添加到集合中。这会降低您的设置到链接列表。