c – 为什么std :: find(s.begin(),s.end(),val)对于一个s来说比

发布时间：2020-12-16 10:37:56 所属栏目：百科来源：网络整理

导读：我最近开始重新学习C,因为我已经十多年没有用C编码了.我很少使用STL,即使我在SGI工作,我也想掌握它.我订购了一本书,目前正在运行不同的在线教程. 一个教程介绍了std :: find(begin(),end(),value),我对我写的测试代码有多慢感到震惊.在做了一些试验和错误之

我最近开始重新学习C,因为我已经十多年没有用C编码了.我很少使用STL,即使我在SGI工作,我也想掌握它.我订购了一本书,目前正在运行不同的在线教程.

一个教程介绍了std :: find(begin(),end(),value),我对我写的测试代码有多慢感到震惊.在做了一些试验和错误之后,我发现s.find(value)显然是我应该使用的.

为什么代码中的第一个查找速度如此之慢？

set<int> s;

for (int i = 0; i < 100000; i++)
    s.insert(rand());

for (int i = 0; i < 10000; i++) {
    int r = rand();

    //first find is about 1000x slower than the next one
    auto iter1 = std::find(s.begin(),s.end(),r);
    auto iter2 = s.find(r);
}

编辑：添加计时实验结果

@juanchopanza在评论中询问时间,所以我在Set,List,Vector和set.find()上定时std :: find()
(我只测量了发现 – 运行之间的差异低于10％)

Vector比List或Set执行得更好,但是set中的专门查找会获得大数据集.

Elements  Vector     List      Set    | Set.Find()
      10   0.0017    0.0017    0.0020  |  0.0017
     100   0.0028    0.0051    0.0120  |  0.0019
    1000   0.0105    0.0808    0.1495  |  0.0035
   10000   0.0767    0.7486    2.7009  |  0.0068
  100000   0.2572    2.4700    6.9636  |  0.0080
 1000000   0.2674    2.5922    7.0149  |  0.0082
10000000   0.2728    2.6485    7.0833  |  0.0082

解决方法

std :: find是一个通用算法,给定一对迭代器可以找到一个值.如果所有它都是一对迭代器,那么找到一个值的最好方法就是线性搜索它,即O(n).

set :: find是std :: set的成员函数,因此它知道它搜索的数据结构,因此可以优化搜索.排序,平衡的树具有出色的搜索行为O(log(n))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!