x*********w
发帖数: 533 | 1 Merge两个sorted array, 长度分别为m和n, array的特征如下:
a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
要再一个个的挪，可以做二分。(j到m-1做二分)
也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
, 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
问题是：
这里的x取什么值最好，一定是2吗？
什么情况下，比如取3比2要更优？ | l*****a
发帖数: 14598 | 2 报厂名
i]
【在 x*********w 的大作中提到】
: Merge两个sorted array, 长度分别为m和n, array的特征如下:
: a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
: b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
: 很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
: 要再一个个的挪，可以做二分。(j到m-1做二分)
: 也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
: , 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
: 问题是：
: 这里的x取什么值最好，一定是2吗？
: 什么情况下，比如取3比2要更优？
| x*********w
发帖数: 533 | 3
踢
【在 l*****a 的大作中提到】
: 报厂名
:
: i]
| s*****1
发帖数: 134 | | x*********w
发帖数: 533 | 5
啥意思，
以朋友说是固定跳sqrt(n)步，为什么？
【在 s*****1 的大作中提到】
: bucket sort?
| j******2
发帖数: 362 | | g**u
发帖数: 504 | 7 can we find these jump points efficiently, like log(n)?
i]
【在 x*********w 的大作中提到】
: Merge两个sorted array, 长度分别为m和n, array的特征如下:
: a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
: b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
: 很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
: 要再一个个的挪，可以做二分。(j到m-1做二分)
: 也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
: , 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
: 问题是：
: 这里的x取什么值最好，一定是2吗？
: 什么情况下，比如取3比2要更优？
| y****n
发帖数: 743 | 8 如果没理解错，既然是合并数组，那么每个元素都会被读取。
那么复杂度O(m+n)是跑不掉的。
除非想用memory copy拷贝某段数组数据，但这样做在某些情况可能得不偿失。 | j******2
发帖数: 362 | 9 我也是这么理解的。所以其实跟一般的merge并无二致。那如何利用这个数组的特点呢？
【在 y****n 的大作中提到】
: 如果没理解错，既然是合并数组，那么每个元素都会被读取。
: 那么复杂度O(m+n)是跑不掉的。
: 除非想用memory copy拷贝某段数组数据，但这样做在某些情况可能得不偿失。
| z**l
发帖数: 292 | 10 This is called "postings merge with skip pointer" in IR.
i]
【在 x*********w 的大作中提到】
: Merge两个sorted array, 长度分别为m和n, array的特征如下:
: a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
: b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
: 很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
: 要再一个个的挪，可以做二分。(j到m-1做二分)
: 也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
: , 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
: 问题是：
: 这里的x取什么值最好，一定是2吗？
: 什么情况下，比如取3比2要更优？
| c********t
发帖数: 5706 | 11 ~然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数
应该是b[j+2^(x-1), j+2^x]里做二分吧。
这里的x取什么值最好，那很难说了，感觉和a[i] b[j]value相关，与j,m大小也相关。
甚至先x=10,找到 b[j+10^(x-1), j+10^x]，再在这个区间 x=5来缩小范围也可以吧。
太复杂了。
i]
【在 x*********w 的大作中提到】
: Merge两个sorted array, 长度分别为m和n, array的特征如下:
: a => 1,2,3,4 ...1001, 9876283, 9876285, 9876293, 9876297, ...9993456, ....
: b => 7,10,13,14,... , 8873, 8875, 5678999871, 5678999873, 5678999874 ....
: 很显然sorted array会有一个big jump. 在发现一个big jump的时候对另一个数组不需
: 要再一个个的挪，可以做二分。(j到m-1做二分)
: 也可以这么做，看j+1, j+2, j+4, j+8, j+16 ..., 找到j + 2^x使得b[j+2^x] > a[i]
: , 然后再在b[j .. j+2^x]里做二分找到刚好大于a[i]的数。
: 问题是：
: 这里的x取什么值最好，一定是2吗？
: 什么情况下，比如取3比2要更优？
| c********t
发帖数: 5706 | 12 读取时间一样。应该是可以减少比较次数和时间
【在 y****n 的大作中提到】
: 如果没理解错，既然是合并数组，那么每个元素都会被读取。
: 那么复杂度O(m+n)是跑不掉的。
: 除非想用memory copy拷贝某段数组数据，但这样做在某些情况可能得不偿失。
|
|
