1

我正在解决一个我试图联合并尝试使用非常简单的基准测试代码来查看效率的问题。

代码非常简单（插入）几百万个元素到一个集合中。为了简单起见，让 set_union 远离讨论。

测试代码：

int main() {
  // Setting up
    int num = 40000000;
  auto it = v.begin();
  std::vector<int> a;
  a.reserve(num);
  for (int i =0;i < num ; ++i) {
    a.push_back(i);
  }

  // Method 1
  { 
    std::set<int> v;    
    for (int i= 0 ; i< num ; ++i) {
       v.insert(a[i]);
    }
  }

  // Method 2
  { 
    std::set<int> v;
    auto it = v.begin();
    for (int i= 0 ; i< num ; ++i) {
       it = v.insert(it,a[i]);
    }
  }  

  // Method 3
  { 
    std::set<int> v;
    auto it = v.begin();
    for (int i= 0 ; i< num ; ++i) {
       it = std::next(v.insert(it,a[i]));
    }
  }

  // Method 4
  { 
    std::set<int> v;
    auto it = v.begin();
    for (int i= 0 ; i< num ; ++i) {
       it = v.insert(it,i); ++it;
    }
  }    

  // Method 5 : idiomatic
  {
    std::set<int> v;
    std::copy(a.begin(), a.end(), std::inserter(v,v.end()));
  }
 return 0;
}

方法 1：最慢（如预期）：~38 秒 方法 2：最快（如预期）：~8 秒 方法 3：~20 秒 方法 4：~20 秒 方法 5：~20 秒

结果有意义，方法 3 和 4 是相同的，在深入研究方法 5 时，我发现 std::inserter 创建了一个输出迭代器，它在分配时与方法 3/4 完全相同（或转换为相同）。

这是故意的吗？为什么不能以最有效的插入方式来编写算法？方法 2 给出了准确的提示，而 3,4,5 将迭代器增加到 set.end() （在这种情况下，当我插入排序范围时，std::next(insert(pos,new_max_element)) == set::end()) 并始终将其作为插入提示。

如果我使用 std::inserter 将迭代器传递给此类有序容器，这会使使用 stl 算法效率低下。附带说明：如果对另一组的插入操作是对数的，我不明白 set_union 如何在线性时间内工作。例如 set_union(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(output_set, output_set.end()) 。已排序的向量很好，但设置了？可以任何人都放了一些链接或参考复杂性分析？

此外，如果有人可以解释或提供一些复杂性分析的参考，以证明插入具有正确提示的集合（例如下一个数字总是小于或大于当前插入的数字）会给您的算法带来一个平均的常数复杂性，那将是很棒的而不是登录。

4

0 回答 0