ComplexPug 最近的时间轴更新
ComplexPug

ComplexPug

V2EX 第 675359 号会员,加入于 2024-02-10 11:55:06 +08:00
今日活跃度排名 4221
ComplexPug 最近回复了
yuque chrome 插件,OneNote chrome 插件,开源社区也有类似的产品
我跟楼上某个老哥差不多,竞赛学数据结构,操作系统是找工作加感兴趣,计组上课学了就没看了,计网是实习要用。csapp 也可以看。坚持做吧,至少装装样子,每次学一点也有进步。
236 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
不过看你评测,实际跑起来这个算法还是很不错的嘛。
236 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
看不懂 lua😵,尤其是那个 while 。不过看着像是没按照 hash 分,是直接读取,hash 里面的<K,V>太多就保存起来。那你怎么合并的不同组的相同的 K 的,比如一组里面有<K,2>,另外一组有<K,3>,怎么合并到一起。
237 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
明天看看
242 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
@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()
```
242 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
@wxf666 我回答你比如后面的两个例子吧,第一个例子,按照 hash%2048 之后,一组一组的统计频率(单线程的),当前这组统计完后遍历一下,放到小顶堆(只有一个,不是一组一个)里面,堆大小不超过 100 ,最后答案就是堆里面的 100 个串。一组做完之后释放内存,所以同时只有一个组和小顶堆的内存。对于第二个例子,恶意 hash 吗,我觉得卡 hash 还是比较难的,hash 保证了每组分到的串的种类一样多,是种类不是频率,所以有的组会比较大(就是因为某些个串出现的次数太多了),但是你保存的是文件,文件大一点没关系,内存不是很大就可以了,内存和 map 有关,map 存的是 kv 对,频率很大也是一样的内存。

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


感觉确实我确实对帖子正文理解的有问题。直接 hash%2048 分组按照我这个评论就是对的,内存占用比较小的解法。
243 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
@wxf666 没太懂你说的“2048 长度的哈希表”是什么,2048 应该是小文件个数,2048 长度是什么。还有你这个分组是直接切分的吗。首先你的 1 肯定是不对的,其次你的 2 可能是这个意思,感觉领悟到你的意思了。

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

我在原文里对这种做法的评价是:并不准确吧,只能保证大概率正确。
243 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
@wxf666 1.因为这个问题本质是按照出现次数排序,出现次数都一样,那肯定还要制定进一步的规则(比如出现次数相同的优先保留字典序小的),如果不特意指定规则,只能随便取 100 个吧。不过这个问题暂且不用考虑。保证出现多的严格在小的前面即可。2.每组 hashmap 统计出现次数保留前 100 大的。保留 KV 对,而不是 10 个字符串保留十个
244 天前
回复了 ComplexPug 创建的主题 程序员 关于一个经典海量数据的问题
@wxf666 第一个问题,没有特别长的字符串,问题里串长度不会很长(确实没说清楚),第二个问题的话直接按照 hash 分组就好了,然后每组 map 统计次数之后进行 topk 算法,因为 hash 映射的很均匀,每组基本都一样大
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   851 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 15ms · UTC 22:09 · PVG 06:09 · LAX 14:09 · JFK 17:09
Developed with CodeLauncher
♥ Do have faith in what you're doing.