读一个大文件统计单词重复K次的次数

Question

问题

有一个巨大的文件（10GB），必须读取文件并打印出文件中重复 k 次的单词数

我的解决方案

1. 使用ifstream逐字读取文件；
2. 将单词插入地图std::map<std::string, long> mp; mp[word] += 1;
3. 读取文件后，找到地图中的所有单词以获得出现 k 次的单词

问题

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

文件信息

1. 每行最多 500 个字的长度
2. 每个单词最多 100 个字符长度

Answer 1

How can multi-thread is used to read the file effectively [read by chunk]? OR Any method to improve the read speed.

我一直在尝试实际结果，多线程是一件好事，这与我之前在这里的建议不同。无线程版本运行时间为 1m44,711s，4 线程版本（4 核）运行时间为 0m31,559s，8 线程版本（4 内核 + HT）运行时间为 0m23,435s。然后是重大改进 - 速度几乎提高了 5 倍。

那么，您是如何分配工作量的？将它分成 N 个块（n == 线程数）并让除第一个线程之外的每个线程首先查找第一个非单词字符。这是他们逻辑块的开始。他们的逻辑块在他们的结束边界处结束，向上舍入到该点之后的第一个非单词字符。

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

要提高阅读速度，您接下来可以做的最好的事情就是确保尽可能不复制数据。通读内存映射文件并通过保留指向开始和结束的指针或索引来查找字符串，而不是累积字节。

Is there any better data structure other than map can be employed to find the output effectively?

好吧，因为我认为您不会使用该命令，所以 unordered_map 是更好的选择。我也会使它成为 unordered_map<std::string_view, size_t> - string_view 复制它甚至比字符串更少。

在分析中，我发现 53% 的时间都花在了查找包含给定单词的确切存储桶上。

Answer 2

如果您有 64 位系统，那么您可以对文件进行内存映射，并使用例如this solution to read from memory.

结合 regarding std::unordered_map and std::string_view (if you have it), and you should be as fast as you can get in a single thread. You could use std::unordered_multiset而不是std::unordered_map，哪个是"faster"我不知道

使用线程很简单，做你知道的就行，但每个线程只处理文件的一部分。在所有线程完成后合并地图。 但是 当您将文件拆分为每个线程的块时，您就有在中间拆分单词的风险。处理这件事并不简单。