算术

有一个非常大的文本文件，比如说300G，你无法读入内存再进行处理。文件中每一行包含一个单词或短语，但是长度不定。请设计一个算法，可以完全随机的从中选择一个单词或短语。选择每一个单词或短语的概率必须严格相同。

还没想出特别好的方案，先说几个思路来抛砖引玉。

第一个方案：如果单词重复的很厉害的话，可以用之前的《并行词频统计》的方法。空间O(M)，M是不同的单词数，时间O(log M)。

第二个方案，干脆什么也不作，你每个单词最少有一个字节吧，回车换行也至少一个字节吧，文件大小应该可以直接获得。于是生成一个0到文件大小之间的随机数， 如果刚好是某个单词的第一个字节或者对应的回车换行，就返回这个单词，否则再拿一个随机数来试，直到成功为止。只是当单词的平均长度很大时，需要时的次数可能很多。空间O(1)，时间O(log L/2)，L是单词的平均长度。

第叁个方案：建索引。如果硬盘中地方够的话，直接把文件中的每个单词的偏移量作为定长的字段，保存到另一个文件中。然后使用随机函数选择一个字段，就可以返回相对应的单词。空间O(N)，时间O(1)。