x*****g
发帖数: 3463 | 1 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
有没有更好的办法？
谢谢！ |
q****x
发帖数: 7404 | 2 heap
的。
【在 x*****g 的大作中提到】
: 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
: 就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
: 另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
: 有没有更好的办法？
: 谢谢！
|
P********e
发帖数: 2610 | 3 看你最终有另外output数组还是没有？
有就 正序，否则反序。区别不大。然后，每2个数组合。
多属性没什么不同，就是自建struct, 多个比较函数。
不想写，就用stl的pair.反正都是唯一。
的。
【在 x*****g 的大作中提到】
: 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
: 就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
: 另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
: 有没有更好的办法？
: 谢谢！
|
g*****g
发帖数: 34805 | 4 Merge sort, to be exact, the merge step of it.
的。
【在 x*****g 的大作中提到】
: 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
: 就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
: 另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
: 有没有更好的办法？
: 谢谢！
|
f*******a
发帖数: 663 | 5 一点思路，抛砖引玉
对于N个有序数组，建立一个临时的大小为N的数组，从每个数组里取第一个元素，排序
后放入。
如下循环：
从临时数组中pop第一个元素输出，同时从原所属数组中取下一个元素，排序后放
入临时数组 |
f*******a
发帖数: 663 | 6 不矛盾啊，呵呵。
临时数组的变化如下：
[1 6 11]
[2 6 11]
...
[5 6 11]
刚才数组长度不一致忘说了，结束了就置一个NULL或者减少临时数组长度都可以
[6 11]
[7 11]
...
[10 11]
只剩一个的时候直接导入即可
[11]
基本思路而已，运算量不大。欢迎讨论 |
a***y
发帖数: 2803 | 7 恩.不错.
【在 f*******a 的大作中提到】
: 不矛盾啊，呵呵。
: 临时数组的变化如下：
: [1 6 11]
: [2 6 11]
: ...
: [5 6 11]
: 刚才数组长度不一致忘说了，结束了就置一个NULL或者减少临时数组长度都可以
: [6 11]
: [7 11]
: ...
|
f*******a
发帖数: 663 | 8 整体型的处理思路，很有意思。简而言之，不断的把单个数组插入至待输出的数组中。
个人感觉：随着数组数量的增加，这种算法的效率会随着长度的增加而降低。
另：关于我的算法的比较次数，好像有点问题。满打满算，15个元素，每次进入临时数
组，比较的就3个元素，只要比两次，最大15×2+第一次排序时的比较，不会超过40.如
果考虑数组被清空以及最后一个数组的情况，比较次数会更少。大致估计，这个算法的
运算量是O(logN * 总元素量)
~~~~有序插入
比较;
【在 a***y 的大作中提到】
: 恩.不错.
|
f*******a
发帖数: 663 | 9 我理解你的想法，但反之未必
我的算法很简单，你把那个例子的过程全列一遍也不用2分钟。做算法，思维要开放和
大气一些 |
a******8
发帖数: 660 | 10 goodbug 不是已经说了用 merge sort 的 merging step 了么?
复杂度对已经有序的数组是各数组长度之和 |
|
|
f*******a
发帖数: 663 | 11 看来偶这样的非专业人士还是对related work不了解啊，呵呵
看了一下，受教了，thanks
【在 a******8 的大作中提到】
: goodbug 不是已经说了用 merge sort 的 merging step 了么?
: 复杂度对已经有序的数组是各数组长度之和
|
p***o
发帖数: 1252 | 12 其实你的想法是对的，结合一下2楼提到的heap就好，更多的讨论找Knuth的第二本书看，
比bbs上的讨论靠谱多了 ...
【在 f*******a 的大作中提到】
: 看来偶这样的非专业人士还是对related work不了解啊，呵呵
: 看了一下，受教了，thanks
|
M**u
发帖数: 10158 | 13 Knuth的书。。。真不是人看的。。。
看，
【在 p***o 的大作中提到】
: 其实你的想法是对的，结合一下2楼提到的heap就好，更多的讨论找Knuth的第二本书看，
: 比bbs上的讨论靠谱多了 ...
|
p***o
发帖数: 1252 | 14 用heap，每个数组顺序读一遍，结果写一遍，从I/O上讲效率已经不错了。
再想提高的话花点时间读文献也是值得的。
【在 M**u 的大作中提到】
: Knuth的书。。。真不是人看的。。。
:
: 看，
|
g*****g
发帖数: 34805 | 15 应该说是O(M LogN)，M是所有数组长度之和，N是数组的个数。
如果数据在某个已知范围，可以用radix sort进行优化。
【在 a******8 的大作中提到】
: goodbug 不是已经说了用 merge sort 的 merging step 了么?
: 复杂度对已经有序的数组是各数组长度之和
|
r****o
发帖数: 1950 | 16 Merge+binary search
【在 g*****g 的大作中提到】
: 应该说是O(M LogN)，M是所有数组长度之和，N是数组的个数。
: 如果数据在某个已知范围，可以用radix sort进行优化。
|
c****p
发帖数: 6474 | 17 把每个数组的第一个元素放进一个heap，每次heap弹出一个元素就把该元素所在的数组
的第一个元素压入heap
的。
【在 x*****g 的大作中提到】
: 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
: 就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
: 另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
: 有没有更好的办法？
: 谢谢！
|
I******c
发帖数: 163 | 18 两两合并应该比所有数列一起合并要好。合并的时候只要比较就可以了。另外一种思路
是用求rank来合并。看楼上有人提出heap. 我的另外一个想法就是分别建heap, 然后合
并heap. 这里的heap可能用Fibonacci Heaps比较好。
以上的想法是基于顺序的算法。 如果考虑到并行算法可能还有些小技巧可以使用，比
如先分小区间再合并，或者多路查找。 |
g*****g
发帖数: 34805 | 19 两两合并是O(NM）的算法，基于堆的合并是O(logN*M)的算法
【在 I******c 的大作中提到】
: 两两合并应该比所有数列一起合并要好。合并的时候只要比较就可以了。另外一种思路
: 是用求rank来合并。看楼上有人提出heap. 我的另外一个想法就是分别建heap, 然后合
: 并heap. 这里的heap可能用Fibonacci Heaps比较好。
: 以上的想法是基于顺序的算法。 如果考虑到并行算法可能还有些小技巧可以使用，比
: 如先分小区间再合并，或者多路查找。
|
P********e
发帖数: 2610 | 20 我没看错把。
【在 g*****g 的大作中提到】
: 两两合并是O(NM）的算法，基于堆的合并是O(logN*M)的算法
|
|
|
I******c
发帖数: 163 | 21 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
的时间复杂度是O(MN)
如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
使用Binomial heap和fibonacci heap实现的话可能需要额外空间。
【在 g*****g 的大作中提到】
: 两两合并是O(NM）的算法，基于堆的合并是O(logN*M)的算法
|
t****t
发帖数: 6806 | 22 ft, you both counted wrong.
if you do pair-wise merge, suppose every vector has M elements, then first
level you have N/2*M*2=NM. then each level the vector length doubles while
the number of vector halves. so it's still NM. Now you have to merge logN
levels. so it's NMlogN.
if you merge N vectors with a heap of N, then you need to do re-adjust the
help for NM times, each time the complexity is logN. So it's still NMlogN.
goodbug used a different notation: the total number of elements is N and M
vectors. but the complexity calculation remains the same.
【在 I******c 的大作中提到】
: 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
: 种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
: 对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
: 的时间复杂度是O(MN)
: 如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
: 还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
: 使用Binomial heap和fibonacci heap实现的话可能需要额外空间。
|
P********e
发帖数: 2610 | 23 每个数列元素个数不确定。题目没说。
按照好虫虫的m, n表示方法一共有logM层合并,每层合并都是N次comparison.
所以，两两合应该是O ( N * logM )
heap的话。每次push, pop都是logM的复杂度，一共需要N次，所以是
O ( N * logM ).
他们都只是在说worst case running time。空间是另外的话题。
【在 I******c 的大作中提到】
: 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
: 种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
: 对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
: 的时间复杂度是O(MN)
: 如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
: 还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
: 使用Binomial heap和fibonacci heap实现的话可能需要额外空间。
|
g*****g
发帖数: 34805 | 24 错了，你的数列后面越来越大，不是M个数，而是O(MN)个数，最后是O(N^2 M)
如果所有数列所有元素的总数是M。那么是O(NM)，而基于堆是O(logN M)
【在 I******c 的大作中提到】
: 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
: 种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
: 对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
: 的时间复杂度是O(MN)
: 如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
: 还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
: 使用Binomial heap和fibonacci heap实现的话可能需要额外空间。
|
i**********e
发帖数: 1145 | 25 写了一个，如果是 k 个数组，每个数组长度最多是 N 的话，那么时间复杂度就是 O(
kN Log (k) )。需要空间复杂度 O(k) 来暂时储存暂时的 indices，来记录每个数组已
经进行到哪里了。
这个也可以用 divide and conquer，每次分半合并，递归解决。虽然时间复杂度是一
样的，但实际上肯定没有用 heap 快，因为递归的关系。
另一个变种就是 merge k sorted linked list，返回一个新的链表。这个就不需要额
外空间，可以每个 list 直接 advanced，指向每个链表进行的位置。但是编写起来很
麻烦，如果你不懂得点技巧的话。这个在 C++ 里用 double dereferencing pointer
代码可以写得相当简洁。
typedef pair Pair;
vector mergeKSortedArrays(vector > A) {
int k = A.size();
priority_queue, greater > q;
vector ret;
int *index = new int[k];
for (int i = 0; i < k; i++) {
q.push(Pair(A[i][0], i));
index[i] = 1;
}
while (!q.empty()) {
Pair p = q.top();
q.pop();
ret.push_back(p.first);
if (index[p.second] < A[p.second].size()) {
q.push(Pair(A[p.second][index[p.second]], p.second));
index[p.second]++;
}
}
delete[] index;
return ret;
} |
t****t
发帖数: 6806 | 26 我说了你们俩都没算对...
【在 g*****g 的大作中提到】
: 错了，你的数列后面越来越大，不是M个数，而是O(MN)个数，最后是O(N^2 M)
: 如果所有数列所有元素的总数是M。那么是O(NM)，而基于堆是O(logN M)
|
g*****g
发帖数: 34805 | 27 haha, 你说的对。不过用头顶的堆是经典的外排算法，按你那么做
要倒磁带。
【在 t****t 的大作中提到】
: 我说了你们俩都没算对...
|
t****t
发帖数: 6806 | 28 我什么也没做...他两两合并的算法虽然IO比较多, 但胜在可并行. 这就比较强大了.
【在 g*****g 的大作中提到】
: haha, 你说的对。不过用头顶的堆是经典的外排算法，按你那么做
: 要倒磁带。
|
g*****g
发帖数: 34805 | 29 如果外排的话，假定速度由IO而不是比较决定。一个IO是MN一个是
LogN * MN，就算你上N/2个机器也就能达到LogN的并行度，也只能达到
一个机器的速度而已。必须内排才有用。
【在 t****t 的大作中提到】
: 我什么也没做...他两两合并的算法虽然IO比较多, 但胜在可并行. 这就比较强大了.
|
I******c
发帖数: 163 | 30 IO的读取是以块为单位，这个对于堆会有影响。除非在堆里每个节点包含多个数据。
【在 g*****g 的大作中提到】
: 如果外排的话，假定速度由IO而不是比较决定。一个IO是MN一个是
: LogN * MN，就算你上N/2个机器也就能达到LogN的并行度，也只能达到
: 一个机器的速度而已。必须内排才有用。
|
|
|
w***g
发帖数: 5958 | 31 楼上说的都好，我来总结以下吧。
1. 如果每个数组只允许顺序操作的话，那用heap在复杂度上来说是最低的。
2. 如果是面试题，显然要考虑外排序的情况。这时候就要考虑block size和K的优化。
在外拍情况下每次需要从数组读取一整个block, 用完了再读一整个。 这样内存中最多
可能同时存在K个block。 block size = mem size / K。这个如果太小了就不能发挥顺
序读取的优势。 这时候就得merge sort了。 比如有8GB内存，K = 10000，那么每个
block也就0.8MB。这样显然不能发挥顺序读取的优势。这时候就可以进行100路merge排
序。这样虽然每块数据要多读写一次，但是block size变成了80MB，throughput会比0.
8MB多不止两倍。当然区别也不大，但K更大时merge就是必须的了。(100路merge还是用
heap实现）。
3. N 路merge的话每个数据需要被读写logK/logN次。N大约等于内存大小/100MB，然后
视具数值调整。
4. 一个罗嗦的情况是各个数组不是random的。比如说一个数组整个都比另一个数组要
大。heap可以部分解决这种情况，但是不知道是不是最优的。大家再讨论一下。
的。
【在 x*****g 的大作中提到】
: 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
: 就是说，任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
: 另外，如果每个元素还带有一个属性，要随着元素移动，怎么办？建个结构？
: 有没有更好的办法？
: 谢谢！
|
