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

Question

问题

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

我的解决方案

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

问题

1. 如何使用多线程有效地读取文件[按 block 读取]？或者 任何提高阅读速度的方法。
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 个 block (n == 线程数)并让除第一个线程之外的每个线程首先查找第一个非单词字符。这是他们逻辑 block 的开始。它们的逻辑 block 在它们的结束边界结束，向上舍入到该点之后的第一个非单词字符。

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

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

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 复制它的次数甚至比 string 少。

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