使用预排序数据加载STL集,C++

Question

我在Visual Studio 2010中使用C++.我有一个STL集,当我的程序关闭时,我将其保存到文件中.下次程序启动时,我将(已排序的)数据加载回集合中.我正在尝试优化加载过程,我遇到了麻烦.我怀疑问题是频繁的重新平衡,我正在寻找一种方法来避免这种情况.

首先,我没有进行优化,使用"set-> insert(const value_type&x)"

时间:约5.5分钟

然后我尝试使用insert()的版本,在其中传递insert()的位置提示:

iterator insert ( iterator position, const value_type& x );

粗略地说,我这样做了:

set<int> My_Set;
set<int>::iterator It;
It = My_Set.insert (0);
for (int I=1; I<1000; I++) {
   It = My_Set.insert (It, I);  //Remember the previous insertion's iterator
   }

时间:约5.4分钟

几乎没有任何进步!我不认为问题是从文件读取开销 - 注释掉insert()会将时间减少到2秒.我认为问题不在于复制对象的开销 - 它是一个带有int和char的Plain Old Data对象.

我唯一能想到的是该套装不断重新平衡.

1.)你同意我的猜测吗？

2.)有没有办法在我加载集合时"暂停"重新平衡,然后在结束时重新平衡一次？(或者......那会有帮助吗？)

3.)是否有更智能的方法来加载已排序的数据,即不是简单地从最低到最高？也许交替我的插入,以便它不必经常平衡？(示例:插入1,1000,2,999,3,998 ......)

Answer 1

关于我们谈论了多少元素？

我用10.000.000个整数(在向量中准备)进行了一个简短的测试,并以三种不同的方式将它们插入到集合中.

准备输入:

  std::vector<int> input;
  for(int i = 0; i < 10*1000*1000; ++i) {
     input.push_back(i);
  }

使用insert插入逐项设置:

发布:2,4秒/调试:110,8秒

  std::set<int> mySet;
  std::for_each(input.cbegin(), input.cend(), [&mySet] (int value) {
     mySet.insert(value);
  });

插入集合insert(itBegin, itEnd):

发布:0,9秒/调试:47,5秒

  std::set<int> mySet;
  mySet.insert(input.cbegin(), input.cend());

  // this is also possible - same execution time:
  std::set<int> mySet(input.cbegin(), input.cend());

因此插入可能会大幅加速,但即使是缓慢的方式也应该远离几分钟.

编辑:

我同时用调试模式进行了测试 - 哇 - 我知道调试成本的性能,但它比我想象的要多.使用50.000.000元素在调试模式下有一个错误的alloc,所以我将我的帖子更新为10.000.000元素,并显示了发布和调试版本的时间.

您可以在这里看到巨大的差异 - 使用更快的解决方案50次.

此外,快速解决方案(insert(itBegin, itEnd))似乎与元素数量呈线性关系(使用预先分类的数据!).普通测试的元素数量增加了5倍,插入时间从4,6减少到0.9,大约是5倍.