r*****9
发帖数: 75 | 1 There are two integer arrays ,each in very large files (size of each is
larger than RAM). How would you find the common elements in the arrays in
linear time. |
s******y
发帖数: 936 | |
l*********8
发帖数: 4642 | 3 把大文件按int value range分成若干小文件
【在 r*****9 的大作中提到】
: There are two integer arrays ,each in very large files (size of each is
: larger than RAM). How would you find the common elements in the arrays in
: linear time.
|
h*******0
发帖数: 270 | 4 好方法
【在 l*********8 的大作中提到】
: 把大文件按int value range分成若干小文件
|
m*****n
发帖数: 2152 | 5 这要看具体RAM多大，数组多大了。
可以用bit 代表数字，INT级的数字 2^32，只要~1GB的内存就能全hash。如果内存还不
足，可以分区读入。
【在 r*****9 的大作中提到】
: There are two integer arrays ,each in very large files (size of each is
: larger than RAM). How would you find the common elements in the arrays in
: linear time.
|
r****s
发帖数: 1025 | 6 option 1:
int array这个应该是比较明显的提示，用bitmap sort类似的方法。
用一个2^32长度的array，每个element保存一个1/2值(short),那么总共需要的内存是2
^32=1k*1k*1k*4=4g。开个6g的java process就可以了。
然后把两个file读一遍就可以了。
option 2:
如果内存不够，就把array分成几次，每次都读一遍file。这样的好处是避免写硬盘。
option 3；
先把file分成小文件，然后再读入。这样的问题是写硬盘。
这样解题比较balanced，不偏向任何一方。 |
