重複しない乱数の発生方法（Collections.shuffleの処理速度）

Question

リストをシャッフルする
Collections.shuffle
というメソッドがありますが、かなり大量のリスト(1000以上)をシャッフルするとなるとやはり処理時間がかかるでしょうか？
実際はリスト全部シャッフルする必要はなく、ランダムで重複しないリストの要素30個程度が取り出せればいいのですが、処理速度を短くしようとした場合いいやり方が思いつきません。
いいやり方はないでしょうか？

現在下記のようなコードでシャッフルしていますが、これだとbufnumが大きくなるほどループ数が大きくなり、
さらにbufnumが大きいほどshuffle回数も大きくしないとランダムになりません。

public class Shuffle {

    public int bufnum;          //用意するバッファ数（シャッフルする対象数）
    public int[] tor;           //シャッフル後の数値
    int shuffleNum = 0;  //シャッフル回数

    public Shuffle()
    {
    }

    public Shuffle(int num, int snum)
    {
        bufnum = num;
        tor = new int[num];
        shuffleNum = snum;
    }

    public void ShuffleNumber(){
        int buff;
        int ran1;
        int ran2;

        if(bufnum == 0)
            return;

        Random rnd1 = new Random();
        Random rnd2 = new Random();

        //数字を配置
        for(int i = 1; i <= bufnum; i++){
            tor[i - 1] = i - 1;
        }

        //シャッフル
        for(int i = 1;i <= shuffleNum;i++){

            //乱数を作成
            ran1 = rnd1.nextInt(bufnum);
            ran2 = rnd2.nextInt(bufnum);

            //配列の入れ替え(乱数１と乱数2を入れ替え)
            buff = tor[ran1];
            tor[ran1] = tor[ran2];
            tor[ran2] = buff;
        }
    }
}

Comments

[lib]

試しに短めのコードを書いてパターンで検証してみてはいかがでしょうか？もしくはすでに検証されたコードと結果をおもちでしたらその内容と開発環境も合わせてご提示いただけますか？

[piyoon]

現在どのように実装されているかを書いて下さい。
処理速度を短くしたいとのことですが、現在がどのように組んでいるかわからないので比較したものを応えることが出来ません（現在組まれているものがベストではないとも限りませんから）。

[piyoon]

あ、被ってしまいましたm(_@_)m

[luckyclock]

記事修正しました

Answer 1

質問文の情報から言えるのは、質問者さんが求めているのは「ランダムサンプリング」であって、「シャッフル」ではありません。「ランダムサンプリング」が高速にできればシャッフルだろうとワッフルだろうとどちらでもかまわないですよね？

Reservoir samplingを強くお勧めします。私が営業なら「お客さんにピッタリですよ」と言うでしょう。

Comments

[luckyclock]

まさにそのとおりのようですが、リンク先のプログラムを理解できませんでした。

[YsMana]

面白いアルゴリズムですね。
要素数が不明なときや、シャッフル対象へのランダムアクセスが高コストな時に有用そうです。

ただ、処理量が（サンプリング数ではなく）要素数に比例するので、
この条件を満たさないときはFisher–Yatesのシャッフルを途中で止めるやり方の方が良さそうですね。

フィッシャー - イェーツのシャッフル - Wikipedia
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%83%E3%82%B7%E3%83%A3%E3%83%BC_-_%E3%82%A4%E3%82%A7%E3%83%BC%E3%83%84%E3%81%AE%E3%82%B7%E3%83%A3%E3%83%83%E3%83%95%E3%83%AB

[ozwk]

フィッシャー - イェーツを途中で止めたら分布に偏り出ると思うんですが。

[YsMana]

途中で止めてシャッフルが終わった部分だけ使います。

[sharow]

そう言われるとReservoir samplingはオーバースペック(?)な気もしてきました。メモリに乗るならシャッフル(and途中で中断)しちゃった方が楽ですね。

[ozwk]

> 途中で止めてシャッフルが終わった部分だけ使います。

「シャッフルが終わった部分」とは何処のことですか？

[swordone]

「取り出し」アルゴリズムの場合、取り出した要素が配列の末尾に集まるのでそれを使うということでは？
仮にその後処理が続いたとしてもその部分は触れられないので、部分的にシャッフルが完了していることになります。

[ozwk]

そうですね
長々と失礼しました

Answer 2

//シャッフル
for(int i = 1;i <= shuffleNum;i++){

    //乱数を作成
    ran1 = rnd1.nextInt(bufnum);
    ran2 = rnd2.nextInt(bufnum);

    //配列の入れ替え(乱数１と乱数2を入れ替え)
    buff = tor[ran1];
    tor[ran1] = tor[ran2];
    tor[ran2] = buff;
}

この入れ替え方では何度繰り返してもまともにシャッフルできません。

<MyData>moto = new ArrayList<MyData>(); //抽出元のデータ
<MyData>select = new ArrayList<MyData>(); //ランダム抽出したデータ格納先
for(int i = 0; i < 30; i++){
    int ran = rnd.nextInt(moto.size());
    select.add(moto.get(ran));
} 

こちらはgetした要素をちゃんと削除すれば大丈夫そうですね。

ランダムで欲しい要素数が、リストの一部と言うことなので
途中までシャッフルするコードを書いてみました。
（テストは20個中10個取得。）

import java.util.Random;

class Shuffle {

    private int   list_len; //listの長さ
    private int[] list; //シャッフル前

    public Shuffle()
    {
    }

    public void SetList(int num)
    {
        //数字を配置
        list = new int[num];
        list_len = num ;
        for(int i = 0; i < num; i++){
            list[i] = i;
        }
    }

    public int[] GetShuffleList(int snum){ //snum:シャッフルして得たい要素数
         int pick;
         int[] s_list;
         Random rnd = new Random();
         s_list = new int[snum];

        //エラーチェック省略
        for(int i = 0;i < snum;i++){
            pick = rnd.nextInt(list_len);
            s_list[i] = list[pick]; //ランダムで要素を取得、s_list[i]に格納
            list[pick] = list[list_len-1]; //最後尾の要素を長さを減らす前に持ってくる(list[pick]はもういらないので捨てる)
            //list[pick]を捨てたくない場合は、list[pick]とlist[list_len-1]を入れ替えば要素は消えない
            list_len--; //取り出したので長さを減らす（減らしたと見なす）
        }
        return s_list;
    }
}

class test {
    public static void main(String args[]){
        Shuffle s1 = new Shuffle();
        
        s1.SetList(20);
        int[] s_list = s1.GetShuffleList(10);
        for(int i = 0;i < s_list.length;i++){
            System.out.println(s_list[i]);
        }
    }
}

1億個から30個欲しい様な場合は連想配列（疎な配列が実現できるなら何でもいいです）を使って、
初期状態空、キーに対応する要素が存在しない場合はキーと同じ要素が入っていると見なして同じように部分シャッフルをかければできそうな気がします。

#追記
HashMapを使った広範囲からのランダム取得が可能なコードを書いてみました。
重複時のリトライがないので、1000個中1000個とかでもたぶん安定した性能になると思います。

import java.util.Random;
import java.util.HashMap;

class Shuffle {

    private int   list_len;
    private HashMap<Integer,Integer> list;

    public Shuffle()
    {
    }

    public void SetList(int num)
    {
        list = new HashMap<Integer,Integer>();
        list_len = num ;
    }

    public int[] GetShuffleList(int snum){
         int pick;
         int[] s_list;
         Random rnd = new Random();
         s_list = new int[snum];

        for(int i = 0;i < snum;i++){
            pick = rnd.nextInt(list_len);
            s_list[i] = list.containsKey(pick) ? list.get(pick) : pick; //ランダムで要素を取得
            list_len--; //取り出したので長さを減らす
            list.put(pick, list.containsKey(list_len) ? list.get(list_len) : list_len ); //最後尾の要素を持ってくる(list[pick]はもういらない)
        }
        return s_list;
    }
}

class test02 {
    public static void main(String args[]){
        Shuffle s1 = new Shuffle();
        
        s1.SetList(20);
        int[] s_list = s1.GetShuffleList(10);
        System.out.println("20 => 10");
        for(int i = 0;i < s_list.length;i++){
            System.out.println(s_list[i]);
        }

        s1.SetList(100000000);
        s_list = s1.GetShuffleList(10);
        System.out.println("100000000 => 10");
        for(int i = 0;i < s_list.length;i++){
            System.out.println(s_list[i]);
        }
    }
}

Comments

[luckyclock]

非常に参考になりました。
ありがとうございます。

Answer 3

速いシャッフルは、forループのカウンターをi(0はじまり)とすると、リストサイズ-i未満の整数の位置の要素と最後からi番目の要素を入れ換える、ということをしているだけです。30個しか要らないのなら、そこまででループをやめればいいでしょう。

// 単純に配列をnum個分だけシャッフルするメソッドにします。適宜工夫してください。
public int[] shuffle(int num) {
    int[] nums = new int[1000];
    int[] result = new int[num];
    for(int i = 0; i < nums.length; i++){
        // 配列に1-1000の数値を入れる
        nums[i] = i + 1;
    }

    for(int i = 0; i < num; i++){
        int pos = (int)(Math.random() * (nums.length - i))
        int temp = nums[pos];
        nums[pos] = nums[nums.length - i - 1];
        nums[nums.length - i - 1] = temp;
        result[i] = temp;
    }
    return result;
}

この方法のメリットは、1回これをやって一部ランダムなままの配列になっていても、そのままの状態で再び同じことをしても問題ないという点です。ちなみにCollections.shuffleも同じようなことをしています。

Comments

[piyoon]

全体のインデックス値の入れ替えを行っているため、最初の３０回でループをやめると入れ替えの行われていない先頭部分はほぼ通番のままのためランダムとしては使えないと思います。

[swordone]

先頭から順に見て、その見ている場所とそれ以降のランダムな位置と入れ替えているので、先頭にランダムな要素が集まります。

Answer 4

やりたいことは、「非復元抽出」と呼ばれるもので、
このワードで調べるとわかりやすいものから
変態的なものまで色々出てきます。

5つぐらい比較しているページ(C++)

Comments

[YsMana]

よくまとまっているページですね。
そのページでtest_knuthとされているのが、sharowさんの紹介されているReservoir samplingと同じようですね。

あと、アルゴリズムを見直していて思ったのですが、
・Reservoir samplingは、サンプリングされた集合内の順序は元のまま（組み合わせがランダムに出てくる）
・シャッフルを途中で止める方法は、サンプリングされた集合内の順序はシャッフルされる（順列がランダムに出てくる）
なので、目的（サンプリング結果のシャッフルが必要か不要か）によってはこの違いが重要になる可能性がありますね。

Answer 5

要するに乱数の最大値が100億とかになっても重複のない乱数列を作りたいというわけですよね。

C++だとSTLのset系を使って作るのですが、Javaだとこんな感じでしょうか。Javaは使ったことがないので正しいコードか自信がありませんが、やり方は伝わりますよね？

// 重複しない30個の乱数列を作成
Set<int> collection = new Set<int>();
while(collection.size() != 30)
{
	collection.add(rnd.nextInt(range));
}

// 配列に変換
int[] tor = new int[30];
collection.toArray(tor);

// その配列をシャッフル
……省略

Answer 6

要望は次のようなものであっていますか？
1.次のような事がしたい「1～1000の中から重複が無く予測不可能な30種類の数字を抽出」
2.自作のシャッフル関数があるが、効率が悪い気がする
3.Collections.shuffleが要求を満たす手段として有望か知りたい

極端に言うと、数百億から30個とかになった場合、その数百億をシャッフルするのは無駄じゃないの？
ということですよね？多分。

配列のシャッフルから離れて
「配列の要素数までの乱数を作成して、その添え字の数値を取得＆配列から削除する」
を30回繰り返したらどうでしょう？

Comments

[luckyclock]

そのとおりです。
たぶん先に回答をくれた方たちも同じようなことだと思うのですが、

中途半端に作ってみましたが、
「配列から削除する」の部分うまいやり方ないでしょうか？
2度目の抜き出しを考えると抽出元のデータから抽出したデータを削除してしまうのはうまくないです。
<MyData>moto = new ArrayList<MyData>(); //抽出元のデータ
<MyData>select = new ArrayList<MyData>(); //ランダム抽出したデータ格納先
for(int i = 0; i < 30; i++){
　　int ran = rnd.nextInt(moto.size());
select.add(moto.get(ran));
}

[hirohiro]

元のリストが作成困難でない場合。（例示のように1~1000など)
出力がほしいときに元配列も作って、抽出が終わったら破棄してしまうのが良いと思います。元のリストが巨大であればあるほど、それをプログラムの開始から終了まで保持するのはメモリの無駄になるためです。

抽出を連続して何回も行うのであれば、配列を複製してそれを使えば良いかも知れません。メモリを倍消費するわけですが、大抵の場合処理後に両方破棄してしまえば問題にならないと思います。
逆に複製して使うとメモリ不足を心配しなければいけないほど巨大な範囲を扱うのであれば、(それは配列1つ保持するだけでも相当な負荷なので)他のアルゴリズムを検討したほうが良いです。

元配列の規模はそうでも無いけど、その配列を作成するのに非常に処理負荷が掛かる場合は、やはり配列を複製して利用してはどうでしょうか？

Answer 7

０からリストのサイズ値の範囲から必要数分（３０個程度）の乱数配列作成し、その値をインデックスとして利用すると良いかと。
１０００以上のリストの中からで３０個程度の作成であれば重複チェックを行ってもループから抜けださなくなるほど重複することはないと思います。