标准容器中 std::find() 的时间

Question

我正在尝试为 std::unordered_set、std::set 和 std::vector 计时 std::find() 函数。但是结果对我来说很奇怪。

在 unordered_set 中查找元素比在 vector 中查找元素花费的时间更多。

理论上，unordered_set搜索的时间复杂度应该是O(1)，vector搜索的时间复杂度应该是O(n)。

那么，在 unordered_set 中查找元素是否应该比 vector 更快？我是不是做错了什么？

这是我的代码：

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <random>
#include <numeric>
#include <chrono>

using namespace std;

int main(int argc, char** argv)
{
  int size = 10000;
  vector<int> items(size);
  iota(items.begin(), items.end(), 0);
  auto rng = default_random_engine {};
  shuffle(items.begin(), items.end(), rng);
  
  chrono::steady_clock::time_point begin, end;  
  unordered_set<int> unsetInt;
  set<int> setInt;
  vector<int> vecInt;

  // add element
  for(auto it = items.begin(); it != items.end(); it++)
  {
    unsetInt.insert(*it);
    setInt.insert(*it);
    vecInt.push_back(*it);
  }
  
  // lookup time for unordered_set<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(unsetInt.begin(), unsetInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for unordered_set<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;
  
  // lookup time for set<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(setInt.begin(), setInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for set<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;
  
  // lookup time for vector<int>
  begin = chrono::steady_clock::now();
  for(int i = 0; i < size; i++)
  {
    find(vecInt.begin(), vecInt.end(), i);
  }
  end = chrono::steady_clock::now();
  cout << "lookup time for vector<int>: " << 
  chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;

  return 0;
}

这是我的结果：

lookup time for unordered_set<int>: 2293ms
lookup time for set<int>: 3080ms
lookup time for vector<int>: 1311ms

Answer 1

Did I do something wrong?

你做到了。

std::find 通过遍历所有元素来执行搜索。它对 std::[unordered_]set 和其他容器没有任何特殊知识。

要在集合中正确搜索，您需要使用它自己的 .find() 成员函数。

Answer 2

作为 HolyBlackCat 的（正确）回答的后续，这里有一些更正的代码来显示差异：

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <random>
#include <numeric>
#include <chrono>

using namespace std;

int main(int argc, char** argv)
{
  int size = 10000;
  vector<int> items(size);
  iota(items.begin(), items.end(), 0);
  auto rng = default_random_engine {};
  shuffle(items.begin(), items.end(), rng);

  using clock = std::chrono::high_resolution_clock;

  clock::time_point begin, end;
  unordered_set<int> unsetInt;
  set<int> setInt;
  vector<int> vecInt;

  // add element
  for(auto it = items.begin(); it != items.end(); it++)
  {
    unsetInt.insert(*it);
    setInt.insert(*it);
    vecInt.push_back(*it);
  }

  int suma = 0, sumb = 0, sumc = 0;
  // lookup time for unordered_set<int>
  begin = clock::now();
  for(int i = 0; i < size; i++)
  {
        suma += *unsetInt.find(i);
    // find(unsetInt.begin(), unsetInt.end(), i);
  }
  end = clock::now();
  cout << "lookup time for unordered_set<int>: " <<
  chrono::duration_cast<chrono::microseconds>(end-begin).count() << "us" << endl;

  // lookup time for set<int>
  begin = clock::now();
  for(int i = 0; i < size; i++)
  {
    // find(setInt.begin(), setInt.end(), i);
    sumb += *setInt.find(i);
  }
  end = clock::now();
  cout << "lookup time for set<int>: " <<
  chrono::duration_cast<chrono::microseconds>(end-begin).count() << "us" << endl;

  // lookup time for vector<int>
  begin = clock::now();
  for(int i = 0; i < size; i++)
  {
    sumc += *find(vecInt.begin(), vecInt.end(), i);
  }
  end = clock::now();
  cout << "lookup time for vector<int>: " <<
      chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;

  cout << "\nIgnore:" << suma << "," << sumb << "," << sumc << '\n';

  return 0;
}

我把它改为显示我们的时间而不是毫秒，因为结果是这样的：

lookup time for unordered_set<int>: 216us
lookup time for set<int>: 889us
lookup time for vector<int>: 21916us

Ignore:49995000,49995000,49995000

我添加了代码来对搜索结果求和，因为没有它，编译器“注意到”循环没有可观察到的行为，并简单地完全优化它们（它们都在 0 毫秒内运行）。我猜你是在关闭优化的情况下进行测试，但在关闭优化的情况下测量代码速度通常不是一件有用的事情。

标准容器中 std::find() 的时间

Timing of std::find() in standard containers

c++

big-o

stl