0

有一个文本文件（大约300M），我需要计算最常出现的十个单词（不包括一些停用词）。测试机有8核Linux系统，欢迎任何编程语言，只能使用开源框架（hadoop不是选项），我没有任何多线程编程经验，我可以从哪里开始以及如何给出一个解决方案花费尽可能少的时间？

4

4 回答 4

0

300M 不是什么大问题，对你的任务来说只是几秒钟的事情，如果你做得对的话，即使是在像 python 这样的高级解释语言中的单核处理。与许多低级语言相比，Python 的优势在于它可以使您的字数统计编程非常容易编码和调试。如果您仍然想要并行化（即使在 python 中运行单核只需几秒钟），我相信有人可以发布一个快速简便的方法来做到这一点。

于 2013-08-12T14:07:41.987 回答
0

假设您每行有 1 个单词，您可以在python中执行以下操作

from collections import Counter

FILE = 'test.txt'
count = Counter()

with open(FILE) as f:
    for w in f.readlines():
        count[w.rstrip()] += 1

print count.most_common()[0:10]
于 2013-08-12T14:17:58.757 回答
0

读取文件并创建所有出现的单词的映射 [Word, count]作为键，值是您阅读时单词出现的次数。

任何语言都应该完成这项工作。

阅读文件一次后，您就有了地图。

然后遍历map，记住count值最高的十个词

于 2013-08-12T14:19:06.280 回答
0

如何以良好的可扩展性解决此问题：

该问题可以通过 2 个map-reduce步骤来解决：

步骤1：

map(word):
   emit(word,1)
Combine + Reduce(word,list<k>):
   emit(word,sum(list))

在这一步之后，你有一个列表(word,#occurances)

第2步：

map(word,k):
   emit(word,k):
Combine + Reduce(word,k): //not a list, because each word has only 1 entry.
   find top 10 and yield (word,k) for the top 10. //see appendix1 for details

在第 2 步中，您必须使用单个减速器，该问题仍然是可扩展的，因为它（单个减速器）只有10*#mappers条目作为输入。

300 MB 文件的解决方案：

实际上，300MB 并不是一个大文件，因此您可以创建一个直方图（在内存上，使用基于树/散列的映射），然后从中输出前 k 个值。

使用支持并发的映射，您可以将文件拆分为多个部分，并让每个线程在需要时进行修改。请注意，如果它实际上被有效分割是依赖于 FS 的，有时一个线程的线性扫描是强制性的。

附录1：
如何获得top k：

使用最小堆并迭代元素，最小堆将始终包含最高 K 个元素。

Fill the heap with first k elements.
For each element e:
     If e > min.heap():
         remove the smallest element from the heap, and add e instead.

此外，此线程中的更多详细信息

于 2013-08-12T14:21:31.327 回答