はじめに
ランダムにデータを並び替えたい、ランダムな順番でアクセスしたい…
そんな時に役立つのが「重複しないランダムなインデックス列」です。
この記事では「一様分布かつ重複しないランダムなインデックス列」を生成するプログラムをJavaとMATLABで実装しましたので紹介します。
シャッフルやサンプリング、データ分割など、さまざまな場面で使えるテクニックです。
重複しないランダムなインデックス列の作成
アルゴリズムについて
有名なアルゴリズムとして、Fisher-Yatesのシャッフルというのがあり、1938年のオリジナルの考え方を実装しています。
全体的な流れは以下のような動作です。
0〜(length-1)の数字をbuffer配列に格納- ランダムで1つ選び、出力配列
outに入れる - 選んだ要素を
bufferから取り除く（配列を詰め直す） - これを
length回繰り返す
このアルゴリズムは O(n2) ですが、1964年に発表された改良版のダステンフェルドのアルゴリズムは「取り除く」といった操作がなく O(n) というのもあります。気になる方は Wikipedia を参照ください。
Javaでの実装例
Javaの実装例です。指定したlengthだけ、0～length-1の値がすべて1回ずつ、ランダムな順番で出現します。
/**
* 指定した長さの一様分布な重複しないランダムな添え字を作成します。
* @param length
* @param seed
* @return
*/
public static int[] getRandomIndex(int length, long seed) {
Random random = new Random(seed);
int[] buffer = new int[length];
for (int i = 0; i < length; i++) {
buffer[i] = i;
}
int[] out = new int[length];
int n, rest;
for (int i = 0; i < length; i++) {
rest = length – i;
n = (random.nextInt() & 0x7FFFFFFF) % rest;
out[i] = buffer[n];
if (1 != rest – n) {
for (int j = 1; j < rest – n; j++) {
buffer[n + j - 1] = buffer[n + j];
}
}
}
return (out);
}
MATLABでの実装例
MATLABの実装例です。dataベクトルから1つランダムに値を選び、選んだらdataから削除していきます。R2011a以降ならrandperm(length)が標準で使えますが、古いバージョンや手動で実装したい時にも使えます。
function [ out ] = getRandomIndex( length, seed )
%[ out ] = getRandomIndex( length, seed )
%指定した長さの一様分布な重複しないランダムな添え字を作成します。
if nargin==2
s = RandStream.create('mt19937ar','seed',seed);
RandStream.setDefaultStream(s);
end
data = 1:1:length;
out = zeros(1,length);
rest = length;
%重複しないランダムな値を作成
for j=1:length
n = 1 + fix(rest * rand(1,1));
out(j) = data(n);
if 0~=rest-n
for k=1:rest-n
data(n+k-1) = data(n+k);
end
end
rest = rest – 1;
end
おわりに
最後まで読んでいただき有難うございます。
重複しないランダムなインデックス列（シャッフル配列）は、データのランダム抽出や検証のサンプリング、順番をランダムにしたいタスクに幅広く応用できます。応用次第で様々なシーンに使えるので、ぜひ自分の用途に合わせて活用してみてください。
コメント