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

Question

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

首先，我没有优化做的，使用 “SET->插入（常量VALUE_TYPE & X）”

时间：〜5.5分钟

然后我试图使用插件的版本（ ），您在提示通为插入（）的位置：

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和一个字符。

我能想到的唯一的事情就是该套装不断重新平衡。

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

2.）有没有办法在加载设置时“暂停”重新平衡，然后在最后重新平衡一次？ （或者...甚至会有帮助吗？）

3.）有没有更明智的方法来加载排序后的数据，即不是简单地从最低到最高？也许交替我的插入，以便它不必经常平衡？ （例如：插入1，1000，2，999，3，998，...）

Answer 1

我们正在谈论多少元素？

我用10.000.000个整数（在向量中准备）做了一个简短的测试，并以三种不同的方式将它们插入到集合中。

准备输入：

推出：：2,4-秒/调试：110,8秒

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

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

---

与插入插入到集逐项

---

插入设置与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元素在调试模式下有一个错误的分配，所以我把我的文章更新为10.000.000个元素，并显示了发布和调试构建的时间。

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

此外，快速解决方案（insert(itBegin, itEnd)）似乎与元素数量成线性关系（使用预分类数据！）。 previus测试有五倍多的元素，插入时间从4,6减少到0.9 - 约五倍。

Answer 2

您是否尝试过范围构造函数？

#include <set> 
#include <fstream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    std::ifstream file("Plop"); 

    std::set<int> myset; 

    std::copy(std::istream_iterator<int>(file), 
       std::istream_iterator<int>(), 
       std::inserter(myset, myset.end())); 
} 

试过4项技术与[0 - > 10,000,000）项目（排序在文件）：

void t1(std::set<int>& data, std::istream& file) 
{ 
    int x; 
    while(file >> x) {data.insert(x); } 
} 

void t2(std::set<int>& data, std::istream& file) 
{ 
    int x; 
    while(file >> x) {data.insert(data.end(), x);} 
} 

void t3(std::set<int>& data, std::istream& file) 
{ 
    std::set<int>::iterator it = data.begin(); 
    int x; 
    while(file >> x) {it = data.insert(it, x);} 
} 

void t4(std::set<int>& data, std::istream& file) 
{ 
    std::copy(std::istream_iterator<int>(file), 
       std::istream_iterator<int>(), 
       std::inserter(data, data.end())); 
} 

次在时钟（）平均超过3个运行（正常）和3个运行（-O4）

    Plain Data 
      Normal    -O4 
      =========   ========= 
t1 Result: 21057300   6748061 
t2 Result: 6580081   4752549 
t3 Result: 6675929   4786003 
t4 Result: 8452749   6460603 

结论1：对于分类数据：

Best: data.insert(data.end(), <item>) // Hint end() 
Worst: data.insert(<item>);    // No Hint 

结论2：优化计数。

Answer 3

这是可能的设置是重新平衡。你有多少物品需要5.6分钟？如果你的项目足够大，你可能会遇到物理内存限制和抖动，或者只是有很糟糕的缓存未命中。

绝对没有办法禁用再平衡。如果可以的话，那么这个集合将能够打破它的不变性，这将是不好的。

• 获取一个分析器和剖析你的代码，而不是猜测什么是花时间。
• 您是否尝试使用end替代之前的迭代器作为另一个数据点的两个参数插入？
• 您是否尝试插入预保留的vector而不是比较时间？
• 你可以逃脱另一种容器类型，如堆或（排序）向量？
• 如果你可以快速加载到一个向量，那么，然后random_shuffle它，然后尝试再次插入到集合，看看会发生什么。