h*****g
发帖数: 312 | 1 Let’s called array1 as A and array2 as B, each with size m and n.
正常的话，O(m+n)应该可以搞定，但是。。。
if n is very very large, the memory can not hold it.
i) What if elements of array B is stored on disk, and the memory is limited
such that you cannot load all elements into the memory at once?
ii) How will the complexity change in this case? Are there any factors you
need to consider?
iii) How do you change your solution to adapt to this situation?
如果用external sort类似的方法，该咋做呢？ | f***g
发帖数: 214 | 2 External 是k-way，这里只有2个。
不是已经有序了吗，每次都load一部分到内存。
然后merge，不够了再load一部分。
要不就binary search，如果m小的话。 | h*****g
发帖数: 312 | 3 如果2-way merge，时间复杂度是多少？还是O（m+n）吧
【在 f***g 的大作中提到】
: External 是k-way，这里只有2个。
: 不是已经有序了吗，每次都load一部分到内存。
: 然后merge，不够了再load一部分。
: 要不就binary search，如果m小的话。
| m**q
发帖数: 189 | 4 How about using B+ tree?
The tree itself will reside in memory, and you can do
a search in the tree for each element in A, locate the
appropriate block range and lock it into memory. That
way you don't need to traverse the whole B array and
thus should be faster, assuming m is relatively small.
limited
【在 h*****g 的大作中提到】
: Let’s called array1 as A and array2 as B, each with size m and n.
: 正常的话，O(m+n)应该可以搞定，但是。。。
: if n is very very large, the memory can not hold it.
: i) What if elements of array B is stored on disk, and the memory is limited
: such that you cannot load all elements into the memory at once?
: ii) How will the complexity change in this case? Are there any factors you
: need to consider?
: iii) How do you change your solution to adapt to this situation?
: 如果用external sort类似的方法，该咋做呢？
|
|
