ComplexPug

不过看你评测，实际跑起来这个算法还是很不错的嘛。

看不懂 lua😵，尤其是那个 while 。不过看着像是没按照 hash 分，是直接读取，hash 里面的<K,V>太多就保存起来。那你怎么合并的不同组的相同的 K 的，比如一组里面有<K,2>，另外一组有<K,3>，怎么合并到一起。

明天看看

@wxf666
伪代码，不是 python
```code
BLOCK_SIZE = 2048
TOP_N = 100
def fun(goal_file):
files f[BLOCK_SIZE] = empty;
for str in goal_file:
f[str.hash()%BLOCK_SIZE].append(str)

heap<(value,count)> q = empty;# (ordered by count,top is smallest)
for i in range(BLOCK_SIZE):
hashmap mp = empty
for str in f[i]:
mp[str] += 1
for value,count in mp:
if q.size() > TOP_N:
if q.top().count > count:
q.pop()
q.push((value,count))
else:
q.push((value,count))
mp.clear()
return q.key()
```

@wxf666 我回答你比如后面的两个例子吧，第一个例子，按照 hash%2048 之后，一组一组的统计频率（单线程的），当前这组统计完后遍历一下，放到小顶堆（只有一个，不是一组一个）里面，堆大小不超过 100 ，最后答案就是堆里面的 100 个串。一组做完之后释放内存，所以同时只有一个组和小顶堆的内存。对于第二个例子，恶意 hash 吗，我觉得卡 hash 还是比较难的，hash 保证了每组分到的串的种类一样多，是种类不是频率，所以有的组会比较大（就是因为某些个串出现的次数太多了），但是你保存的是文件，文件大一点没关系，内存不是很大就可以了，内存和 map 有关，map 存的是 kv 对，频率很大也是一样的内存。

等我有空下午写个伪代码。


感觉确实我确实对帖子正文理解的有问题。直接 hash%2048 分组按照我这个评论就是对的，内存占用比较小的解法。

@wxf666 没太懂你说的“2048 长度的哈希表”是什么，2048 应该是小文件个数，2048 长度是什么。还有你这个分组是直接切分的吗。首先你的 1 肯定是不对的，其次你的 2 可能是这个意思，感觉领悟到你的意思了。

你是觉得 2 这个做法是有问题的吗，我知道你这种构造方法不对。我发这个帖子就是询问这个问题。而且你这个做法我在贴里说明了，是有正确率问题的。不知道你懂我意思了吗感觉（感觉确实是我的表达能力的问题🥲）。

我在原文里对这种做法的评价是：并不准确吧，只能保证大概率正确。

@wxf666 1.因为这个问题本质是按照出现次数排序，出现次数都一样，那肯定还要制定进一步的规则（比如出现次数相同的优先保留字典序小的），如果不特意指定规则，只能随便取 100 个吧。不过这个问题暂且不用考虑。保证出现多的严格在小的前面即可。2.每组 hashmap 统计出现次数保留前 100 大的。保留 KV 对，而不是 10 个字符串保留十个

@wxf666 第一个问题，没有特别长的字符串，问题里串长度不会很长（确实没说清楚），第二个问题的话直接按照 hash 分组就好了，然后每组 map 统计次数之后进行 topk 算法，因为 hash 映射的很均匀，每组基本都一样大

@misdake 那确实肯定速度快，但可能面试的时候限制你内存大小，或者让你筛选 1000G 的 top100 ，不过分布式肯定还能处理。