阅读一个大文件来计算单词的数量重复K次

Question

问题

有一个巨大的文件（10GB），一个具有读取文件和打印出来的单词数精确重复k倍在文件

我的解决方案

1. 使用ifstream读取由字的文件字;
2. 插入Word成图std::map<std::string, long> mp; mp[word] += 1;
3. 一旦文件被读取时，发现所有词语的地图，让字存在的k次

问题

1. 哪有多线程用于有效读取文件[按块读取]？ OR 任何提高读取速度的方法。
2. 有没有比地图更好的数据结构可以用来有效地找到输出？

文件信息

1. 每行可以最大500个字长度的
2. 每个字都可以最多100个字符长度的

Answer 1

怎样才能多线程用于有效读取文件[按块读取]？或任何提高读取速度的方法。

我一直在尝试实际的结果，这是一个多线程的好东西，不像我以前的建议。非线程变量运行在1m44,711s，4线程（在4个内核上）运行在0m31,559s，而8线程（在4个内核+ HT上）运行在0m23,435s。主要改进 - 几乎是加速的5倍。

那么，你如何分担工作量？将它拆分为N个块（n ==线程数），并且除了首先寻找第一个非单词字符之外的每个线程。这是他们的逻辑块的开始。他们的逻辑块结束于它们的结束边界，在该点之后被取整为第一个非单词字符。

并行处理这些块，将它们全部同步到一个线程，然后使该线程执行结果合并。

为了提高阅读速度，你可以做的最好的下一件事是确保你尽可能不复制数据。通过内存映射文件读取并通过将指针或索引保存到开始和结束来查找字符串，而不是累积字节。

有没有比地图更好的数据结构可以用来有效地找到输出？

嗯，因为我不认为你会使用该命令，unordered_map是一个更好的选择。我也将它作为unordered_map<std::string_view, size_t> - string_view将其复制到比字符串更小的位置。

在剖析中，我发现53％的时间花在寻找包含给定单词的确切桶上。

Answer 2

如果你有一个64位系统，那么你可以记忆映射文件，并使用例如this solution to read from memory。

结合the answer from dascandy关于std::unordered_map和std::string_view（如果有的话），并且您应该尽可能快地获得单个线程。您可以使用std::unordered_multiset而不是std::unordered_map，哪一个“更快”我不知道。

使用线程很简单，只要做你知道的事情，但每个线程只处理部分文件。所有线程完成后合并地图。 但是当您将文件拆分为每个线程的块时，则可能会在中间拆分单词。处理这不是微不足道的。