时间戳

首页 > 解决方案 > STL 容器以获得最佳性能？

c++ - STL 容器以获得最佳性能？

问题描述

我有一个项目，我需要读取一个文本文件并记录在 EoF 之前读取的每个字符串、字符或数字的出现次数。

然后我需要打印前 10 个最常用的单词。

例如，该文件将包含“这是此项目的测试”。我会阅读这个并将每个单词及其当前计数存储在一个容器中。

现在，随着输入的增长，我们根据时间复杂度的效率对我们进行评分。所以，我需要一些帮助来选择最有效的 STL 容器。

似乎顺序并不重要，我可以永远插入最后，而且我永远不必插入。但是，我必须在容器中搜索最常用的 10 个单词。对于这样的需求，哪个 STL 容器具有最佳的时间复杂度？

另外，如果你能解释你的推理，让我知道更多的未来，那就太好了！

标签： c++performancestlcontainerstime-complexity

解决方案

我使用了两个容器来完成这样的任务：std::unordered_map<std::string, int>存储单词频率，并std::map<int, std::string>跟踪最常用的单词。

在使用新词更新第一个地图的同时，您还更新了第二个地图。为了保持整洁，如果第二张地图的大小超过 10，请删除最不常用的单词。

更新

针对下面的评论，我做了一些基准测试。

首先，@PaulMcKenzie - 你是对的：为了保持联系，我需要std::map<int, std::set<std::string>>（这在我开始实施时就变得很明显）。

其次，@dratenik - 事实证明你也是正确的。虽然不断清理频率图使其保持较小，但开销并不能带来好处。此外，只有当客户想要查看“运行总数”时才需要这样做（正如我在项目中被要求的那样）。当加载所有单词时，在后处理中完全没有意义。

对于测试，我使用alice29.txt（可在线获得），预处理 - 我删除了所有标点符号并转换为大写。这是我的代码：

int main()
{
  auto t1 = std::chrono::high_resolution_clock::now();
  std::ifstream src("c:\\temp\\alice29-clean.txt");
  std::string str;
  std::unordered_map<std::string, int> words;
  std::map<int, std::set<std::string>> freq;
  int i(0);
  while (src >> str)
  {
    words[str]++;
    i++;
  }
  for (auto& w : words)
  {
    freq[w.second].insert(w.first);
  }
  int count(0);
  for (auto it = freq.rbegin(); it != freq.rend(); ++it)
  {
    for (auto& w : it->second)
    {
      std::cout << w << " - " << it->first << std::endl;
      ++count;
    }
    if (count >= 10)
      break;
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() << std::endl;
  return i;
}

推荐阅读