读一个大文件来计算重复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

如何使用多线程有效地读取文件[由块读取]？或任何提高读取速度的方法.

我一直在尝试实际的结果,多线程是一件好事,不像我之前的建议.非线程变体运行1m44,711s,4线程(4核)运行0m31,559s,8线程(4核+ HT)运行0m23,435s.那么重大改进 - 加速几乎是5倍.

那么,你如何分配工作量？将其拆分为N个块(n ==线程计数)并使每个线程除了第一个寻找第一个非单词字符之外.这是他们逻辑块的开始.它们的逻辑块在它们的结束边界处结束,在该点之后向上舍入到第一个非单词字符.

并行处理这些块,将它们全部同步到一个线程,然后使该线程完成结果的合并.

为提高阅读速度,您可以做的最好的事情是确保尽可能不复制数据.读取内存映射文件并通过将指针或索引保持在开头和结尾来查找字符串,而不是累积字节.

除了map之外是否有更好的数据结构可以有效地找到输出？

好吧,因为我认为你不会使用订单,所以unordered_map是更好的选择.我也会把它变成一个unordered_map<std::string_view, size_t>- string_view复制它甚至比字符串更少.

在分析时,我发现53%的时间用于查找包含给定单词的确切存储桶.