如何应对Follow up - 如果数据量很大，内存不够怎么办？

Google一下海量数据面试 有很多汇总的博客

存hard drive里面啊

或者做一个sampling，拿一部分data，不要全部。

sabre80 发表于 2022-5-27 10:49
存hard drive里面啊

或者做一个sampling，拿一部分data，不要全部。

单纯做样本，不做哈希桶的话肯定是不行的
用 Top K frequent words 为例，如果把word-frequency数据存硬盘的话，比如每次取1万个数字，怎么做到快速更新frequency？总不能每次都打开文件读+更新吧。

bbbbbk 发表于 2022-5-27 01:56
搜一下IO Efficient Merge Sort

感谢 你分享的这几个关键词 感觉很有帮助

阵雨 发表于 2022-5-27 01:09
比如有 1e12 个数字求 max
可以分成 1e9 个单独文件，然后内存实际上运算就是 1e3 的规模，找出 max，最 ...

嗯 你说的没错 这个角度看的话 divide & conquer 和 mapreduce基本指的是同一个意思，前提是都是在硬盘上实现的

bbbbbk 发表于 2022-5-27 01:57
Google一下海量数据面试 有很多汇总的博客

这个关键词确实很好 很多这方面的博客我之前也看过
从层主的角度看 侧重点应该是什么呢
解决问题的思路？算法（哈希桶/mapreduce/bitmap)？还是系统设计？
我个人似乎一直focus在算法上面，毕竟这些一般都是算法的follow-up

idontknoooo 发表于 2022-5-27 09:35
这个关键词确实很好 很多这方面的博客我之前也看过
从层主的角度看 侧重点应该是什么呢
解决问题的思 ...

侧重点自然就是
1. 是否有 hand on experience？有，看看怎么做的
2. 没有？是不是能想到一些可行性方案？ 有，有潜力，good signal
3. 没有？能不能去猜想，尝试，划归成有经验的问题。。。

说起来想到以前还真碰到过一个数据，没法全部放进 GPU training。。。

Top K frequent words follow up 恰好是我们组面试常问的，基本分为两种情况：
1. 有一个 node, limited memory，这样的情况可以 read chunk by chunk, 依次把每个 chunk 里的 words 排序。然后每个 chunk 分配一个指针，初始的时候指向每个 sorted chunk 里的第一个 word. 同时在内存里保留一个 size-k heap, 这样通过移动指针可以找到 total count of each word across all chunks. 然后把 (count, word) 放到 heap 里，同时保证 heap 的 size < k. 常见的错误方法是先在每个 chunk 里找 top K, 然后再找合并后的 top K，这样的话 local top K 会影响 global top K, 最后的结果可能会是错误的。
2. 有多个 node, 每个 node limited memory, 这样就是 map reduce, 重点在于如何 partition, 有很多人会考虑 range based partition, 比如以 A 开头的 word 分到一个 node, B 开头的到另一个... 但问题在于以有些字母开头的词会更常见，所以有可能导致 unbalanced loads. 更好的方法可以是 hashing.

求加米谢谢！

阵雨 发表于 2022-5-27 11:57
侧重点自然就是
1. 是否有 hand on experience？有，看看怎么做的
2. 没有？是不是能想到一些可行性方 ...

虽然你不是那个层主 但还是很感谢！
你这个思路挺有趣的 有点像BQ的tell me about a time you dive deep into a project 的简化版
看来我还得准备个故事 lol 谢谢

hxu 发表于 2022-5-27 12:17
Top K frequent words follow up 恰好是我们组面试常问的，基本分为两种情况：
1. 有一个 node, limited m ...

这个答案太牛逼了 读完第一句就想给米 今天米额度到了 只能给一个了 明天去你的文章里补米

这个真的cover到一些细节 我突然想起来我好像面试的时候就回答的在local里面找top k
竟然还自我感觉良好 我太蠢了

而且分单节点+多节点讨论这个思路也非常有用 还有如何处理切片分布不均这个也是个重要的细节

超级感谢！！！