关于一个经典海量数据的问题

13次阅读

共计 760 个字符,预计需要花费 2 分钟才能阅读完成。

2 个 G 的字符串,找出出现次数最多的 100 个。感觉对搜索到的答案倒不是很理解。
比如

把 2G 的文件进行分割成大小为 512KB 小文件,总共得到 2048 个小文件,避免一次性读入整个文件造成内存不足。
定义一个长度为 2048 的 hash 表数组,用来统计每个小文件中单词出现的频率。
使用多线程并行遍历 2048 个小文件,针对每个单词进行 hash 取模运算分别存储到长度为 2048 的 hash 表数组中 inthash=Math.abs(word.hashCode() %hashTableSize);hashTables[hash].merge(word, 1, Integer::sum);
接着再遍历这 2048 个 hash 表,把频率前 100 的单词存入小顶堆中
最后,小顶堆中最终得到的 100 个单词,就是 top 100 了。
这种解决方案的核心思想是将大文件分割为多个小文件,然后采用分治和堆的算法,来解决这个问题。

如果是多线程使用 hashmap,内存中仅仅去除了重复字符串吧。

还有一种使用字典树的,但出现频次很低的时候内存占用也不小。

还有一种是按照 hash(word)%2048 来保存小文件,但不适用于单词频次高使得小文件变大。

还有一种是把大文件直接拆分成小文件,然后对每个文件求 topK,最后求整个的 topK。这个思路虽然时间没问题,但能保证 topK 的正确性吗。如果按照普通的小顶堆 topk 算法,使用的是出现次数,但这里因为没用 hash 分组,的一个字符的出现次数是分开的,并不准确吧,只能保证大概率正确。

我的想法是要想保证强正确性且不能保证数据安全,按照 hash(word)%2048 保存文件,小文件使用 hashmap,大文件使用字典树。最后对所有文件的频次使用 topk 算法。

问过别人但交流了半天他没懂,想问一下我对这个问题的理解对吗,或者有什么好的解决方案。

正文完
 0