问处理巨大的文本文件

EN

你需要看看克尼汉和派克的“编程实践”，特别是第三章。

在C++中，使用基于字符串和计数的映射(std::map<string,size_t>，IIRC)。读取文件(一次--它太大了，不能读取不止一次)，一边读一边把它分割成单词(对于“word”的某些定义)，并在地图条目中增加您找到的每个单词的计数。

在C中，您必须自己创建映射。(或者找到大卫·汉森的“C接口和实现”。)

或者您可以使用Perl、Python或Awk (它们都有关联数组，相当于一个映射)。

我不认为使用并行读取文件部分的多线程会有多大帮助。我希望这个应用程序绑定到硬盘的带宽和延迟，而不是实际的单词计数。这样的多线程版本执行起来可能会更糟，因为“准随机”文件访问通常比“线性文件”访问慢。

如果CPU在单线程版本中真的很忙，可能会加快速度。一个线程可以读取大量数据，并将它们放入容量有限的队列中。一组其他的工作线程可以在各自的块上操作并计算单词。计数工作线程完成后，您必须合并单词计数器。

首先-决定保存单词的数据结构。

最明显的选择是地图。但是也许一个特瑞会更好地服务于你。在每个节点中，保存单词的计数。意思是，它只是一个单词的一部分。您可以使用流插入trie并读取基于字符的文件。

第二次多线程是还是不是？这个问题不容易回答。根据数据结构的大小以及并行化的方式，答案可能会有所不同。

1. 单线程-前向和易于实现。
2. 具有多个读取器线程和一个数据结构的多线程。然后您必须同步对数据结构的访问。在Trie中，您只需要锁定实际所在的节点，这样多个读取器就可以访问数据结构，而不受太多干扰。自平衡树可能有所不同，特别是当再平衡时。
3. 多线程由多个读取器线程组成，每个线程都有自己的数据结构。每个线程在读取文件的一部分时都会构建自己的数据结构。每次完成后，结果必须合并(这应该是容易的)。

有一件事你必须考虑--你必须为每个线程找到一个单词边界来启动，但这不会造成很大的问题(例如，每个线程一直走到第一个单词边界，然后在那里开始，每个线程在结束时完成它正在处理的单词)。