设计算法，寻找书中最常用的词

Question

一个面试问题：

找出一本书中使用频率最高的单词。

我的想法：

使用一个哈希表，遍历并标记这个哈希表。

如果知道书的大小，假如发现某个单词的使用频率超过50%，那么在接下来的遍历中就跳过新单词，只统计旧单词。如果不知道书的大小呢？

这个方法的时间和空间复杂度都是O(n)。

有没有更好的想法？

谢谢

Answer 1

这实际上是一个经典的 MapReduce 示例。

维基百科上的例子会告诉你每个独特单词的出现次数，但你可以在减少步骤中轻松添加一个环节，来记录当前最常见的单词（需要用某种方式来处理多个任务同时进行的问题）。

如果你有一组分布式的机器或者一台高度并行的计算机，这种方法的运行速度会比使用哈希表快得多。

Answer 2

要判断复杂度，我觉得需要考虑两个变量：n = 单词总数，m = 不同单词的数量。我想在最好的情况下，速度的复杂度大概会接近 O(n log(m))，而存储的复杂度则是 O(m)。这是基于你每次都要遍历 n 个单词，并且根据一个哈希表或其他类似的结构来构建和搜索，这个结构最终会包含 m 个元素。

Answer 3

通常情况下，堆是一种很适合用来判断某些东西，比如最常用或最少用的情况的数据结构。

即使是Python中的Counter.nlargest，它也是通过堆这种数据结构来实现的。

二叉堆这种数据结构有以下的复杂度：

CreateHeap - O(1)
FindMin - O(1)
deleteMin - O(logn)
Insert - O(logn)

我对哈希（使用Python中的默认字典）和堆（使用Python中的Collections.Counter.nlargest）进行了比较，发现哈希的表现稍微好于堆。

>>> stmt1="""
import collections, random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
somehash=collections.defaultdict(int)
for d in somedata:
    somehash[d]+=1
maxkey=0
for k,v in somehash.items():
    if somehash[maxkey] > v:
        maxkey=k
"""
>>> stmt2="""
import collections,random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
collections.Counter(somedata).most_common(1)
"""
>>> t1=timeit.Timer(stmt=stmt1)
>>> t2=timeit.Timer(stmt=stmt2)
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10)
38168.96 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10)
33600.80 usec/pass