質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

  • Java

    15062questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

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

解決済

回答 7

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 5,391

luckyclock

score 54

リストをシャッフルする
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);

            //配列の入れ替え(乱数1と乱数2を入れ替え)
            buff = tor[ran1];
            tor[ran1] = tor[ran2];
            tor[ran2] = buff;
        }
    }
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • lib

    2016/03/18 20:23

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

    キャンセル

  • piyoon

    2016/03/18 20:25

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

    キャンセル

  • piyoon

    2016/03/18 20:26

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

    キャンセル

  • luckyclock

    2016/03/18 20:42

    記事修正しました

    キャンセル

回答 7

+2

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/18 22:00

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

    キャンセル

  • 2016/03/18 22:58

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

    ただ、処理量が(サンプリング数ではなく)要素数に比例するので、
    この条件を満たさないときは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

    キャンセル

  • 2016/03/18 23:09

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

    キャンセル

  • 2016/03/18 23:20

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

    キャンセル

  • 2016/03/18 23:53

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

    キャンセル

  • 2016/03/19 08:02

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

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

    キャンセル

  • 2016/03/19 09:27

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

    キャンセル

  • 2016/03/19 12:47

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

    キャンセル

checkベストアンサー

+1

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

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

    //配列の入れ替え(乱数1と乱数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]);
        }
    }
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/18 23:17

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

    キャンセル

0

速いシャッフルは、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も同じようなことをしています。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/18 21:17

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

    キャンセル

  • 2016/03/19 00:16

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/18 21:38

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

    中途半端に作ってみましたが、
    「配列から削除する」の部分うまいやり方ないでしょうか?
    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));
    }

    キャンセル

  • 2016/03/18 22:46 編集

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

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

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

    キャンセル

0

要するに乱数の最大値が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);

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/03/19 00:24 編集

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

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

    キャンセル

同じタグがついた質問を見る

  • Java

    15062questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。