j******2 发帖数: 362 | 1 You are given two very large files of unsigned 64
bit integers. Write to an output file all the numbers
that appear in both files, but there should be no
duplicates in the output file (like an intersection).
思路是不是先分别external sort,再求交集啊? |
d**********x 发帖数: 4083 | 2 1.txt map时 emit , 2.txt map时emit
reduce的时候用bitwise-or,然后输出所有标记为3的?
刚学这个。。瞎扯的。。。
要是一台机器,应该是hash吧
【在 j******2 的大作中提到】 : You are given two very large files of unsigned 64 : bit integers. Write to an output file all the numbers : that appear in both files, but there should be no : duplicates in the output file (like an intersection). : 思路是不是先分别external sort,再求交集啊?
|
j******2 发帖数: 362 | 3 想起来了,傻逼了。
【在 d**********x 的大作中提到】 : 1.txt map时 emit , 2.txt map时emit : reduce的时候用bitwise-or,然后输出所有标记为3的? : 刚学这个。。瞎扯的。。。 : 要是一台机器,应该是hash吧
|
j******2 发帖数: 362 | 4 又想了下,好象还是sort先比较好。mapreduce不会也,要学吗??
bit vector反正是不行,太大了。
下面两个地方都有讨论,大家也讨论下如何?
http://stackoverflow.com/questions/6520954/produce-a-file-that-
http://www.careercup.com/question?id=13869712
【在 j******2 的大作中提到】 : 想起来了,傻逼了。
|
d**********x 发帖数: 4083 | 5 先sort就是归并的时候不用太大消耗。。不过sort的过程会很痛苦吧。
我能想到的另一个办法就是hash到机器,然后在各个机器上再建hash表。
不过我对分布式没什么经验,都是蒙的,希望有经验的来给讲讲。
【在 j******2 的大作中提到】 : 又想了下,好象还是sort先比较好。mapreduce不会也,要学吗?? : bit vector反正是不行,太大了。 : 下面两个地方都有讨论,大家也讨论下如何? : http://stackoverflow.com/questions/6520954/produce-a-file-that- : http://www.careercup.com/question?id=13869712
|
j******2 发帖数: 362 | 6 大侠能不能介绍下mapreduce入门怎么学,只需要很简单的,网上有什么好的资料推荐
吗?不胜感激
【在 d**********x 的大作中提到】 : 先sort就是归并的时候不用太大消耗。。不过sort的过程会很痛苦吧。 : 我能想到的另一个办法就是hash到机器,然后在各个机器上再建hash表。 : 不过我对分布式没什么经验,都是蒙的,希望有经验的来给讲讲。
|
d**********x 发帖数: 4083 | 7 版面搜索hadoop,第一篇
【在 j******2 的大作中提到】 : 大侠能不能介绍下mapreduce入门怎么学,只需要很简单的,网上有什么好的资料推荐 : 吗?不胜感激
|
j******2 发帖数: 362 | 8 谢谢!!
懂hadoop是不是必须呀?我已经为leetcode和150的算法题耗尽了体力,不想学新的了
,能否直接说:不懂hadoop!
【在 d**********x 的大作中提到】 : 版面搜索hadoop,第一篇
|
j******2 发帖数: 362 | 9 再想想这题,0~2^64的范围内,一个reasonable的file size,肯定不会是full range
上很密集的都有(如果整个范围每个数出现一次,文件大小就是2^64个64-bit,也就是
2^67byte,也就是2^37个G,那是什么概念?在两个文件大小正常的情况下,external
sort应该是可行的,因为
sort的复杂度取决于的是文件里数的个数,而非数值的范围。更进一步,如果文件很小
,只
是数的范围大,那用hash就可以解决了。
【在 d**********x 的大作中提到】 : 先sort就是归并的时候不用太大消耗。。不过sort的过程会很痛苦吧。 : 我能想到的另一个办法就是hash到机器,然后在各个机器上再建hash表。 : 不过我对分布式没什么经验,都是蒙的,希望有经验的来给讲讲。
|
d**********x 发帖数: 4083 | 10 所以就看文件到底有多大。。
range
external
【在 j******2 的大作中提到】 : 再想想这题,0~2^64的范围内,一个reasonable的file size,肯定不会是full range : 上很密集的都有(如果整个范围每个数出现一次,文件大小就是2^64个64-bit,也就是 : 2^67byte,也就是2^37个G,那是什么概念?在两个文件大小正常的情况下,external : sort应该是可行的,因为 : sort的复杂度取决于的是文件里数的个数,而非数值的范围。更进一步,如果文件很小 : ,只 : 是数的范围大,那用hash就可以解决了。
|
j******2 发帖数: 362 | 11 他的disk装得下多大的file,external sort就可以sort多大的file,是这个理儿吧? |
j******2 发帖数: 362 | 12 他的disk装得下多大的file,external sort就可以sort多大的file,是这个理儿吧? |
c********t 发帖数: 5706 | 13 en, 如果两个1TB的文件,在4gb rem机器上external sort也是很痛苦的。
我觉得hadoop不一定要懂(我不懂),但mapreduce过程还是要能说出来吧。这道题估
计面试官会引导,最后还是要用mapreduce.
【在 d**********x 的大作中提到】 : 所以就看文件到底有多大。。 : : range : external
|
j******2 发帖数: 362 | 14 谢谢指引,我觉得你说的有理。
【在 c********t 的大作中提到】 : en, 如果两个1TB的文件,在4gb rem机器上external sort也是很痛苦的。 : 我觉得hadoop不一定要懂(我不懂),但mapreduce过程还是要能说出来吧。这道题估 : 计面试官会引导,最后还是要用mapreduce.
|