回答編集履歴

HashMapを使った部分シャッフル追加

2016/03/18 13:40

投稿

YsMana

スコア257

test CHANGED Viewed

@@ -169,3 +169,127 @@
 1億個から30個欲しい様な場合は連想配列（疎な配列が実現できるなら何でもいいです）を使って、
 初期状態空、キーに対応する要素が存在しない場合はキーと同じ要素が入っていると見なして同じように部分シャッフルをかければできそうな気がします。
+#追記
+HashMapを使った広範囲からのランダム取得が可能なコードを書いてみました。
+重複時のリトライがないので、1000個中1000個とかでもたぶん安定した性能になると思います。
+```Java
+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]);
+        }
+    }
+}
+```