はじめに
（コメントで指摘頂いたように、若干効率改善の余地があります。）
ホクホクのイモのコメントに書いた「ガチなやつ」のために考えた方法です。
リストから複数の要素をランダムに重複なく効率よく取り出す方法について述べます。
ここでいう「リスト」は可変長のランダムアクセス可能なリスト1です。
説明は Java で行いますが、再利用可能なように関数化した最終的なコードは Java, JavaScript, Kotlin で用意しています。
Java のコード例では、ファイルの先頭に次の import 文が宣言されているとします。
Java
import java.util.*;
リストから要素をランダムに取り出す
1つだけ
リストから要素を1つだけランダムに取り出すのは簡単です。
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C, D の4つの要素を持つリスト
int index = new Random().nextInt(list.size()); // ランダムに選択された 0 以上 4 未満の整数
Character result = list.get(index); // ランダムに選択された要素
System.out.println(result); // 出力例 > B
全て
全ての要素をランダムな順番で取り出すのも、標準ライブラリーにそのような関数が用意されていれば簡単です。
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C, D の4つの要素を持つリスト
List<Character> shuffled = new ArrayList<>(list); // この後ランダムに並べ替えられる、list のコピー
Collections.shuffle(shuffled); // shuffled の要素をランダムに並び替える。
System.out.println(shuffled); // 出力例 > [C, A, D, B]
全てではない複数
では、全要素ではない複数の要素をランダムな順番で取り出すのはどうでしょう。
Java（注意：効率が悪い）
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C, D の4つの要素を持つリスト
List<Character> shuffled = new ArrayList<>(list); // この後ランダムに並べ替えられる、list のコピー
Collections.shuffle(shuffled); // shuffled の要素をランダムに並び替える。
List result = shuffled.subList(0, 2); // shuffled の前から2つの要素を持つ新しいリスト
System.out.println(result); // 出力例 > [C, B]
いやいや、これだと書くのは楽ですが、
全要素をシャッフルしているので無駄が多いです。
要素数が1万のリストから100要素を取り出すときに、1万要素をシャッフルしたら、9900要素分は無駄になります。
じゃあどうするか。
無駄なシャッフルを避ける
要素を1つだけランダムに選択し、選択した要素はリストから削除する、というのを繰り返しましょう。
Java（注意：効率が悪い）
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C, D の4つの要素を持つリスト
List<Character> result = new ArrayList<>(); // ランダムに選択された要素を持たせるリスト
List<Character> remaining = new ArrayList<>(list); // 残っている要素のリスト
Random random = new Random(); // 乱数生成器
for (int i = 0; i < 2; i++) { // 2回繰り返す。
int remainingCount = remaining.size(); // 残っている要素の数
int index = random.nextInt(remainingCount); // ランダムに選択されたインデックス
Character element = remaining.remove(index); // ランダムに選択された要素を取り出す。
result.add(element); // ランダムに選択された要素を持たせるリストの末尾に、ランダムに選択された要素を追加する。
}
System.out.println(result); // 出力例 > [B, D]
無駄なシャッフルはなくなりましたね。
しかし実はこれも効率が悪いです。
ランダムアクセス可能なリストは内部では配列を使って要素を保持しており、
途中の要素を削除するとそれ以降の要素を前に詰める処理が行われます。
|A|B|C|D| | | | |
↓Bを削除
|A|C|D| | | | | |
そのため削除する要素が前の方であるほど処理時間がかかるのです。
ではどうればよいのか。
途中の要素を削除するのを避ける
途中の要素を削除するから遅いのです。
削除するのは末尾だけにしましょう。
途中の要素は削除せずに入れ替えましょう。
Bを削除する場合
|A|B|C|D| | | | |
↓末尾のDを削除し、
|A|B|C| | | | | |
↓BをDに置き換える。
|A|D|C| | | | | |
コードにすると次のようになります。
Java
List<Character> list = Arrays.asList('A', 'B', 'C', 'D'); // A, B, C, D の4つの要素を持つリスト
List<Character> result = new ArrayList<>(); // ランダムに選択された要素を持たせるリスト
List<Character> remaining = new ArrayList<>(list); // 残っている要素のリスト
Random random = new Random(); // 乱数生成器
for (int i = 0; i < 2; i++) { // 2回繰り返す。
int remainingCount = remaining.size(); // 残っている要素の数
int index = random.nextInt(remainingCount); // ランダムに選択されたインデックス
Character element = remaining.get(index); // ランダムに選択された要素
result.add(element); // ランダムに選択された要素を持たせるリストの末尾に、ランダムに選択された要素を追加する。
int lastIndex = remainingCount - 1; // 残っている要素のリストの末尾のインデックス
Character lastElement = remaining.remove(lastIndex); // 残っている要素のリストから末尾を削除する。
if (index < lastIndex) { // ランダムに選択された要素が末尾以外なら…
remaining.set(index, lastElement); // それを末尾の要素で置換する。
}
}
System.out.println(result); // 出力例 > [D, A]
計測
処理速度の違いを簡単に計測してみましょう。
全ての要素をシャッフルして先頭の部分リストを取得するものと、最後の最も無駄がないものを比較します。
リストの要素数を10万とし、そこから5万をランダムに取得させると、
全要素シャッフルではおよそ590ms、
無駄がないものだとおよそ370msとなりました。
計測に使用したコードと出力例
Java
public class TakeAtRandom {
public static void main(String... args) {
// リストのサイズ
final int LIST_SIZE = 10_000_000;
// リストから取得する要素の数
final int N = 5_000_000;
// くり返し回数
final int REPETITION = 100;
final List<Integer> list = new ArrayList<>(LIST_SIZE);
for (int i = 0; i < LIST_SIZE; i++) {
list.add(i);
}
final Random random = new Random();
for (int i = 0; i < REPETITION; i++) {
{
final long startAt = System.currentTimeMillis();
takeFromShuffled(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format(" 全要素シャッフル: %,d ms", finishedAt - startAt));
}
{
final long startAt = System.currentTimeMillis();
takeAtRandom(list, N, random);
final long finishedAt = System.currentTimeMillis();
System.out.print(String.format(" 無駄なし: %,d ms", finishedAt - startAt));
}
System.out.println();
}
}
public static <T> List<T> takeFromShuffled(List<T> list, int n, Random random) {
final List<T> workList = new ArrayList<>(list);
Collections.shuffle(workList);
return workList.subList(0, n);
}
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
final List<T> taken = new ArrayList<>(n); // ランダムに選択された要素を持たせるリスト
final List<T> remaining = new ArrayList<>(list); // 残っている要素のリスト
for (int i = 0; i < n; i++) { // n 回繰り返す。
final int remainingCount = remaining.size(); // 残っている要素の数
final int index = random.nextInt(remainingCount); // ランダムに選択されたインデックス
final T element = remaining.get(index); // ランダムに選択された要素
taken.add(element); // ランダムに選択された要素のリストの末尾にランダムに選択された要素を追加する。
final int lastIndex = remainingCount - 1; // 残っている要素のリストの末尾のインデックス
final T lastElement = remaining.remove(lastIndex); // 残っている要素のリストから末尾を削除する。
if (index < lastIndex) { // ランダムに選択された要素が末尾以外なら…
remaining.set(index, lastElement); // それを末尾の要素で置換する。
}
}
return taken;
}
}
出力例
全要素シャッフル: 608 ms 無駄なし: 705 ms
全要素シャッフル: 659 ms 無駄なし: 1,985 ms
全要素シャッフル: 585 ms 無駄なし: 372 ms
全要素シャッフル: 598 ms 無駄なし: 378 ms
全要素シャッフル: 598 ms 無駄なし: 397 ms
全要素シャッフル: 586 ms 無駄なし: 451 ms
全要素シャッフル: 583 ms 無駄なし: 381 ms
全要素シャッフル: 584 ms 無駄なし: 391 ms
全要素シャッフル: 580 ms 無駄なし: 383 ms
全要素シャッフル: 578 ms 無駄なし: 383 ms
全要素シャッフル: 584 ms 無駄なし: 377 ms
全要素シャッフル: 585 ms 無駄なし: 378 ms
全要素シャッフル: 598 ms 無駄なし: 381 ms
全要素シャッフル: 591 ms 無駄なし: 359 ms
全要素シャッフル: 605 ms 無駄なし: 354 ms
全要素シャッフル: 590 ms 無駄なし: 373 ms
全要素シャッフル: 584 ms 無駄なし: 379 ms
全要素シャッフル: 586 ms 無駄なし: 359 ms
全要素シャッフル: 603 ms 無駄なし: 357 ms
全要素シャッフル: 589 ms 無駄なし: 376 ms
全要素シャッフル: 579 ms 無駄なし: 385 ms
全要素シャッフル: 581 ms 無駄なし: 352 ms
全要素シャッフル: 610 ms 無駄なし: 350 ms
全要素シャッフル: 587 ms 無駄なし: 372 ms
全要素シャッフル: 603 ms 無駄なし: 381 ms
全要素シャッフル: 595 ms 無駄なし: 353 ms
全要素シャッフル: 606 ms 無駄なし: 348 ms
全要素シャッフル: 579 ms 無駄なし: 376 ms
全要素シャッフル: 576 ms 無駄なし: 390 ms
全要素シャッフル: 582 ms 無駄なし: 359 ms
全要素シャッフル: 602 ms 無駄なし: 357 ms
全要素シャッフル: 583 ms 無駄なし: 375 ms
全要素シャッフル: 585 ms 無駄なし: 379 ms
全要素シャッフル: 586 ms 無駄なし: 353 ms
全要素シャッフル: 603 ms 無駄なし: 350 ms
全要素シャッフル: 590 ms 無駄なし: 370 ms
全要素シャッフル: 587 ms 無駄なし: 376 ms
全要素シャッフル: 586 ms 無駄なし: 351 ms
全要素シャッフル: 600 ms 無駄なし: 359 ms
全要素シャッフル: 585 ms 無駄なし: 379 ms
全要素シャッフル: 579 ms 無駄なし: 382 ms
全要素シャッフル: 580 ms 無駄なし: 352 ms
全要素シャッフル: 605 ms 無駄なし: 349 ms
全要素シャッフル: 588 ms 無駄なし: 372 ms
全要素シャッフル: 586 ms 無駄なし: 375 ms
全要素シャッフル: 584 ms 無駄なし: 351 ms
全要素シャッフル: 598 ms 無駄なし: 358 ms
全要素シャッフル: 579 ms 無駄なし: 376 ms
全要素シャッフル: 579 ms 無駄なし: 381 ms
全要素シャッフル: 578 ms 無駄なし: 357 ms
全要素シャッフル: 601 ms 無駄なし: 348 ms
全要素シャッフル: 593 ms 無駄なし: 371 ms
全要素シャッフル: 585 ms 無駄なし: 376 ms
全要素シャッフル: 584 ms 無駄なし: 352 ms
全要素シャッフル: 602 ms 無駄なし: 349 ms
全要素シャッフル: 586 ms 無駄なし: 372 ms
全要素シャッフル: 586 ms 無駄なし: 376 ms
全要素シャッフル: 578 ms 無駄なし: 359 ms
全要素シャッフル: 598 ms 無駄なし: 357 ms
全要素シャッフル: 583 ms 無駄なし: 379 ms
全要素シャッフル: 578 ms 無駄なし: 382 ms
全要素シャッフル: 592 ms 無駄なし: 356 ms
全要素シャッフル: 605 ms 無駄なし: 350 ms
全要素シャッフル: 587 ms 無駄なし: 374 ms
全要素シャッフル: 586 ms 無駄なし: 377 ms
全要素シャッフル: 586 ms 無駄なし: 353 ms
全要素シャッフル: 600 ms 無駄なし: 357 ms
全要素シャッフル: 581 ms 無駄なし: 380 ms
全要素シャッフル: 580 ms 無駄なし: 380 ms
全要素シャッフル: 580 ms 無駄なし: 352 ms
全要素シャッフル: 605 ms 無駄なし: 349 ms
全要素シャッフル: 592 ms 無駄なし: 373 ms
全要素シャッフル: 585 ms 無駄なし: 374 ms
全要素シャッフル: 585 ms 無駄なし: 352 ms
全要素シャッフル: 598 ms 無駄なし: 357 ms
全要素シャッフル: 580 ms 無駄なし: 377 ms
全要素シャッフル: 582 ms 無駄なし: 383 ms
全要素シャッフル: 578 ms 無駄なし: 362 ms
全要素シャッフル: 611 ms 無駄なし: 358 ms
全要素シャッフル: 581 ms 無駄なし: 375 ms
全要素シャッフル: 594 ms 無駄なし: 377 ms
全要素シャッフル: 587 ms 無駄なし: 362 ms
全要素シャッフル: 603 ms 無駄なし: 350 ms
全要素シャッフル: 587 ms 無駄なし: 373 ms
全要素シャッフル: 585 ms 無駄なし: 376 ms
全要素シャッフル: 586 ms 無駄なし: 353 ms
全要素シャッフル: 601 ms 無駄なし: 358 ms
全要素シャッフル: 593 ms 無駄なし: 378 ms
全要素シャッフル: 580 ms 無駄なし: 384 ms
全要素シャッフル: 577 ms 無駄なし: 351 ms
全要素シャッフル: 606 ms 無駄なし: 349 ms
全要素シャッフル: 589 ms 無駄なし: 380 ms
全要素シャッフル: 590 ms 無駄なし: 352 ms
全要素シャッフル: 605 ms 無駄なし: 348 ms
全要素シャッフル: 590 ms 無駄なし: 375 ms
全要素シャッフル: 581 ms 無駄なし: 359 ms
全要素シャッフル: 599 ms 無駄なし: 357 ms
全要素シャッフル: 581 ms 無駄なし: 381 ms
全要素シャッフル: 579 ms 無駄なし: 353 ms
全要素シャッフル: 607 ms 無駄なし: 349 ms
関数化
再利用できるように関数化しました。
Java
Java
import java.util.*;
public class TakeAtRandom {
/**
* リストから指定された数の要素をランダムに重複なく取り出す。
*
* @param list このリストから要素を取り出す。このリストは変更されない。
* @param n 取り出す要素の数。
* @param <T> 要素の型。
* @return 取得された要素を持つリスト。
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n) {
return takeAtRandom(list, n, new Random());
}
/**
* リストから指定された数の要素をランダムに重複なく取り出す。
*
* @param list このリストから要素を取り出す。このリストは変更されない。
* @param n 取り出す要素の数。
* @param random 使用する乱数生成器。
* @param <T> 要素の型。
* @return 取得された要素を持つリスト。
*/
public static <T> List<T> takeAtRandom(Collection<T> list, int n, Random random) {
if (list == null) {
throw new IllegalArgumentException("引数 list の値が null です。");
}
if (n > list.size()) {
throw new IllegalArgumentException(
String.format("引数 n の値 %d が引数 list のサイズ %d より大きいです。",
n, list.size()));
}
if (random == null) {
throw new IllegalArgumentException("引数 random の値が null です。");
}
final List<T> taken = new ArrayList<>(n); // ランダムに選択された要素を持たせるリスト
final List<T> remaining = new ArrayList<>(list); // 残っている要素のリスト
for (int i = 0; i < n; i++) { // n 回繰り返す。
final int remainingCount = remaining.size(); // 残っている要素の数
final int index = random.nextInt(remainingCount); // ランダムに選択されたインデックス
final T element = remaining.get(index); // ランダムに選択された要素
taken.add(element); // ランダムに選択された要素のリストの末尾にランダムに選択された要素を追加する。
final int lastIndex = remainingCount - 1; // 残っている要素のリストの末尾のインデックス
final T lastElement = remaining.remove(lastIndex); // 残っている要素のリストから末尾を削除する。
if (index < lastIndex) { // ランダムに選択された要素が末尾以外なら…
remaining.set(index, lastElement); // それを末尾の要素で置換する。
}
}
return taken;
}
}
JavaScript
JavaScript
/**
* 配列から指定された数の要素をランダムに重複なく取り出す。
*
* @param {Array} array この配列から要素を取り出す。この配列は変更されない。
* @param {number} n 取り出す要素の数。
* @return {Array} 取得された要素を持つ配列。
*/
function takeAtRandom(array, n) {
if (array == null) {
throw new Error("引数 array の値が null もしくは undefined です。");
}
if (n > array.length) {
throw new Error(`引数 n の値 ${n} が引数 array のサイズ ${array.length} より大きいです。`);
}
const taken = [];
const remaining = array.concat();
for (let i = 0; i < n; i++) {
const remainingCount = remaining.length;
const index = Math.floor(Math.random() * remainingCount);
const element = remaining[index];
taken.push(element);
const lastIndex = remainingCount - 1;
const lastElement = remaining.pop(lastIndex);
if (index < lastIndex) {
remaining[index] = lastElement;
}
}
return taken;
}
ジェネレーター版
JavaScript
/**
* 配列から要素をランダムに重複なく取り出すジェネレーターを返す。
*
* @param {Array} array この配列から要素を取り出す。この配列は変更されない。
*/
function* takeAtRandom(array) {
if (array == null) {
throw new Error("引数 array の値が null もしくは undefined です。");
}
const remaining = array.concat();
while(true) {
const remainingCount = remaining.length;
if (remainingCount === 0) {
break;
}
const index = Math.floor(Math.random() * remainingCount);
yield remaining[index];
const lastIndex = remainingCount - 1;
const lastElement = remaining.pop();
if (index < lastIndex) {
remaining[index] = lastElement;
}
}
}
Kotlin
Kotlin
import kotlin.random.Random
/**
* リストから指定された数の要素をランダムに重複なく取り出す。
*
* @receiver このリストから要素を取り出す。
* @param n 取り出す要素の数。
* @param random 使用する乱数生成器。
* @param <T> 要素の型。
* @return 取得された要素を持つリスト。
*/
fun <T> Collection<T>.takeAtRandom(n: Int, random: Random = Random): List<T> {
require(n <= size) { "引数 n の値 $n がレシーバーのサイズ ${size} より大きいです。" }
val taken = mutableListOf<T>() // ランダムに選択された要素を持たせるリスト
val remaining = toMutableList() // 残っている要素のリスト
// n 回繰り返す。
repeat(n) {
val remainingCount = remaining.size // 残っている要素の数
val index = random.nextInt(remainingCount) // ランダムに選択されたインデックス
taken += remaining[index] // ランダムに選択された要素
val lastIndex = remainingCount - 1 // 残っている要素のリストの末尾のインデックス
val lastElement = remaining.removeAt(lastIndex) // 残っている要素のリストから末尾を削除する。
if (index < lastIndex) { // ランダムに選択された要素が末尾以外なら…
remaining[index] = lastElement // それを末尾の要素で置換する。
}
}
return taken
}
Sequence 版
Kotlin
import kotlin.random.Random
/**
* リストから指定された数の要素をランダムに重複なく取り出すシーケンスを返す。
*
* @receiver このリストから要素を取り出す。
* @param random 使用する乱数生成器。
* @param <T> 要素の型。
* @return シーケンス。
*/
fun <T> Collection<T>.toRandomSequence(random: Random = Random): Sequence<T> = sequence {
val remaining = toMutableList() // 残っている要素のリスト
while (true) {
val remainingCount = remaining.size // 残っている要素の数
.takeIf { it > 0 }
?: break
val index = random.nextInt(remainingCount) // ランダムに選択されたインデックス
remaining[index].also {
yield(it)
}
val lastIndex = remainingCount - 1 // 残っている要素のリストの末尾のインデックス
val lastElement = remaining.removeAt(lastIndex) // 残っている要素のリストから末尾を削除する。
if (index < lastIndex) { // ランダムに選択された要素が末尾以外なら…
remaining[index] = lastElement // それを末尾の要素で置換する。
}
}
}
／以上
-
Javaだと
java.util.ArrayList、JavaScriptだとArray、C++だとstd:vector↩