m*****n
发帖数: 2152 | 1 N个clusters，每个memory 10M， 现在有1000 billion的string，要统计每个词出现
的次数。问题是，在极端条件下，分成若干个小job，分别处理，然后合并，(其实就是
map reduce)，这种方法不work。比如，1000 billion的词可能完全不同，处理完一个
小job，输出的大小不会比输入小。 要求精确计算所有词的count。
已经说了，hash，rehash之类方法，可能产生collision，不够精确，面试官说不行。
已经说了，按字母排序或者分组，面试官说了太慢，不行。
已经说了，trie tree，随便几个长的string就把内存暴掉了，被面试官鄙视了。
请问，还有什么方法？ |
p*****9
发帖数: 273 | |
s***5
发帖数: 2136 | 3 Is each string a single word?
Hash different strings into different slave nodes according to the first 1-2
characters so that the same words are mostly in the same machine. |
l*******0
发帖数: 95 | 4 这个题就是你要想办法尽量均匀的把1000 billion 字符串“尽量均匀地“分片，每台
机器上面有 1000 billion / N 个字符串。
如果1000 billion / N 可以完全装在10M内存里，那就用HashMap保存结果。
如果10 M 内存太小装不下，那么真正的计数结果应该也只能存在磁盘上，可以用来建
一个索引，用来指向string在磁盘文件以及在文件中的偏移。你也可以根据字符串内容
将结果存在多个文件里。 |
m*****n
发帖数: 2152 | 5 我也说了类似的方法，比如用map把string 搞成 Axxx, Bxxxx, Cxxx，...，然后用
reduce，shuffle 所有的 server。第二轮AAxxx，ABxxx，....，如此循环，总有小于
10M的时候，但面试官不满意，说太慢了。
我估计，他是嫌我浪费了memory。要是第一轮就AAAAxxx, ..., ZZZZxxx。最大要的
memory (假设string只有26个大写字母)是26^4*(4+8) ～ 5M.
然后第二次，再搞下面4个，这样速度可以提高不少。
【在 l*******0 的大作中提到】
: 这个题就是你要想办法尽量均匀的把1000 billion 字符串“尽量均匀地“分片，每台
: 机器上面有 1000 billion / N 个字符串。
: 如果1000 billion / N 可以完全装在10M内存里，那就用HashMap保存结果。
: 如果10 M 内存太小装不下，那么真正的计数结果应该也只能存在磁盘上，可以用来建
: 一个索引，用来指向string在磁盘文件以及在文件中的偏移。你也可以根据字符串内容
: 将结果存在多个文件里。
|
v***o
发帖数: 287 | 6 “已经说了，hash，rehash之类方法，可能产生collision，不够精确，面试官说不行
。”
可以用128 bit MD5 hash, 2^128, collision几率在1000billion 中还是很小的。你用
hashmap,一样也依赖于hash function.
【在 m*****n 的大作中提到】
: N个clusters，每个memory 10M， 现在有1000 billion的string，要统计每个词出现
: 的次数。问题是，在极端条件下，分成若干个小job，分别处理，然后合并，(其实就是
: map reduce)，这种方法不work。比如，1000 billion的词可能完全不同，处理完一个
: 小job，输出的大小不会比输入小。 要求精确计算所有词的count。
: 已经说了，hash，rehash之类方法，可能产生collision，不够精确，面试官说不行。
: 已经说了，按字母排序或者分组，面试官说了太慢，不行。
: 已经说了，trie tree，随便几个长的string就把内存暴掉了，被面试官鄙视了。
: 请问，还有什么方法？
|
h**********c
发帖数: 4120 | |
M**********7
发帖数: 378 | 8 感觉hash是对的。hash只是用来定位机器，或是本机上辅助定位内存或如果内存实在不
足时候的外部文件的，而实际统计的时候还是要看原字串，应该没有不够精确的问题。
【在 v***o 的大作中提到】
: “已经说了，hash，rehash之类方法，可能产生collision，不够精确，面试官说不行
: 。”
: 可以用128 bit MD5 hash, 2^128, collision几率在1000billion 中还是很小的。你用
: hashmap,一样也依赖于hash function.
|
s******7
发帖数: 1758 | 9 这种题，只有hash， map reduce一条路，没别的法子，估计故意刁难，欺负你外国人,
大数据都是这样做，他牛逼自己开一个公司跟google对着干 |
