j******2
发帖数: 362 | 1 巨大的数组，不能放进内存的，怎么shuffle？ |
c****9
发帖数: 164 | |
j******2
发帖数: 362 | 3 "shuffle id段"，是说组与组shuffle吗？这样不均匀吧？
【在 c****9 的大作中提到】
: 分段shuffle，然后shuffle id段
|
j******2
发帖数: 362 | 4 大概可以这样：
分n段shuffle后存到n个小文件里，每个文件里m个数。然后generate m次shuffle了的1
到n，再m次读不同文件里的头，写回原大文件。 |
n******e
发帖数: 957 | 5 可不可以像external sort那样，每次shuffle一下每个chunk的头？然后下次shuffle下
个？ |
r*****s
发帖数: 74 | 6 有个想法，不知道对不对
假设共有n个数，要分到m个文件里面去。
A[] 有n个数需要shuffle
先随机分到m个文件中去
for int i : A
int d = random(1 to m)
put A[i] to file[d]
end
for i = 0: m - 1
shuffle file[i]
end
for i = 0:A.length - 1
int d = random(1 to m)
A[i] = pop the first number from file[m]
end
某个数分配到某一个文件的概率是1/m，它出现在这个文件某一个位置的概率是m/n，然
后大数列里某个位置抽到这个数的概率是大约是1/n？没具体算，拍脑袋乱算的概率…… |
b******7
发帖数: 92 | 7 不能先分段shuffle，再shuffle段id，这样不均匀。比如考虑数组为aaaaabcdef，若按
照这个思路，则无论怎么shuffle，这5个a都会在一起。
我的考虑和racolas一样，先将N个元素shuffle到M个文件中，再在M个文件内shuffle，
最后合并。
定义每个文件当前可容纳元素个数r[i],i=0...M-1,初始时所有r[i]都为N/M
从磁盘上读取N个元素，设当前为第k个元素，则根据rand[1,N-k]落入{r[0],r[0]+r[1]
,r[0]+r[1]+r[2],...}中的哪一个决定第k个元素写入哪个文件，并且相应的文件可容
纳个数减1。 |
