t********y
发帖数: 14 | 1 有100台computer。每一台computer的disk capacity 是 1TB 并且满了，里面的数据是
sorted。computer 和 computer 之间的也是sorted （just like a 2D array sorted
by both row and column) 现在加一台新的computer，1TB disk。 要求把数据平均放
在这101台computer中， 并且数据仍sorted within each disk and between each
disk. 如何在disk之间copy 数据可minimize network traffic. (move data within a
disk is every low cost can be ignored.) |
j*****y
发帖数: 1071 | 2 computer 和 computer之间也是 sorted， 意思是说一台机器上的所有数据都要比另
外一台机器上的任意数据要小吧？
sorted
a
【在 t********y 的大作中提到】
: 有100台computer。每一台computer的disk capacity 是 1TB 并且满了，里面的数据是
: sorted。computer 和 computer 之间的也是sorted （just like a 2D array sorted
: by both row and column) 现在加一台新的computer，1TB disk。 要求把数据平均放
: 在这101台computer中， 并且数据仍sorted within each disk and between each
: disk. 如何在disk之间copy 数据可minimize network traffic. (move data within a
: disk is every low cost can be ignored.)
|
t********y
发帖数: 14 | 3 yes.
【在 j*****y 的大作中提到】
: computer 和 computer之间也是 sorted， 意思是说一台机器上的所有数据都要比另
: 外一台机器上的任意数据要小吧？
:
: sorted
: a
|
j*****y
发帖数: 1071 | 4 感觉新加的机器应该排在中间
【在 t********y 的大作中提到】
: yes.
|
b*****u
发帖数: 648 | 5 make sense,
(1+2+...+50)*2 < (1+...+100)
【在 j*****y 的大作中提到】
: 感觉新加的机器应该排在中间
|
f*****e
发帖数: 2992 | |
f*****e
发帖数: 2992 | 7 第101th machine to 1-101 slice。
【在 f*****e 的大作中提到】
: 用O(N)也可以。
|
w**********o
发帖数: 140 | |
c********t
发帖数: 5706 | 9 求详细解释。
我和楼上几位想的一样，把101th 放在中间，然后所有的machine都往中间移数据
【在 f*****e 的大作中提到】
: 第101th machine to 1-101 slice。
|
f*****e
发帖数: 2992 | 10 我也这么想的。
【在 c********t 的大作中提到】
: 求详细解释。
: 我和楼上几位想的一样，把101th 放在中间，然后所有的machine都往中间移数据
|
b****g
发帖数: 192 | 11 我也是这么想的，但是还是感觉这么做比较原始，不知道有没有更好的方法
【在 f*****e 的大作中提到】
: 我也这么想的。
|
w**********o
发帖数: 140 | 12 抛个砖头吧，别笑话我啊。
我把101th放在最后。
比如说，1T可以分成10disks，假设每个电脑都有10disks。
Total disks(before): 100*10= 1000 disks，分100份,
Total disks(After) : 1000+1*10 = 1010disks， 分101份
1000/101 = 9.9 d
101给100要9.9d, 100给99要9.9d, ....2给1要9.9d.
因为101给100要的同时，100也给99要，以此类推，2跟1要。
假如disk copy的速度都是一摸一样的话， 应该可以达到linear
我猜测的优化，可以优化 每个TB里面拥有disk的数目， 比如1000Disks/T。
PS: 可以把最新的，放在100位置，让原来的100变成101.
谢谢各位。 |
