c++ - std::unordered_set::find 和 std::find 之间奇怪的性能差异

Question

我尝试比较std::unordered_set::find和的性能std::find。与我的期望和规则相反，https://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-algorithm.html std::find明显更快

带有 unordered_set 的快速工作台

unorder_set包含ints 所以散列应该不是问题。std::set::find按预期运行并且比std::find.

带套装的快速板凳 谁能解释一下这种行为？谢谢

标签： c++performance

Answer 1

其中一些还取决于硬件和实现。但是为了更清楚地了解正在发生的事情，绘制不同尺寸的每个尺寸所花费的时间会很有用。

对于这个测试，我使用了微软的编译器，所以与 clang/llvm 的一些差异并不特别令人惊讶。只是为了笑，std::lower_bound除了find,set和unordered_set.

我也做了一些不同的测试，生成随机数来填充容器，并在容器中搜索一组 1000 个随机值。这（可能）是导致右端小于线性增长的原因std:find。Microsoft 的随机数生成器只有 15 位范围，因此对于 100,000 个元素，我们将在生成 100,000 个值之前命中它可以生成的每个值，因此在上次测试中，搜索受到范围的限制我们可以生成的值而不是数组的大小。

我想如果我有野心，我会使用更好的范围更大的随机数生成器来重写它，但我认为这足以确定趋势，并很好地了解该修改的预期结果。

编辑：更正了粘贴到电子表格中的数据的错位。