生成するたびに、その値が異なるような乱数を得る方法の中から、ダステンフェルドのアルゴリズムを使った方法と、もっと簡単だが速度面では不利な方法を紹介する。
重複のない乱数とは、例えば乱数を2つ生成したときに必ず異なる値が得られるということだ。そのようなアルゴリズムには生成され得る乱数が有限個に限定されるものとされないものとが考えられるが、本稿では限定した場合を扱う。例えば、1から10の整数の中から乱数を3つ生成するような場合である(生成され得る乱数は10個)。あるいは、トランプを使ったカードゲームでシャッフルするというのは、1から52(ジョーカーを含めるなら53)までの整数の範囲で重複しない乱数を52回(あるいは53回)生成することだと考えられるので、本稿のロジックで扱える。
2通りの方法を紹介するので、特定の方法をすぐに知りたいという方は以下のリンクを活用してほしい。
なお、ダステンフェルドのアルゴリズムは.NET Frameworkのバージョンによらず利用できるが、本稿に掲載したサンプルコードをそのまま試すにはVisual Studio 2015以降が必要である。
ダステンフェルドのアルゴリズムは、フィッシャー/イェーツのアルゴリズムを改良して1964年に公表されたものだ(Wikipedia参照)。ダステンフェルドのアルゴリズムを使って指定した整数の範囲で重複しない乱数を生成するメソッドは、次のコードのようになる。
static void Swap(ref int m, ref int n)
{
int work = m;
m = n;
n = work;
}
static IEnumerable<int> GetUniqRandomNumbers(int rangeBegin, int rangeEnd, int count)
{
// 指定された範囲の整数を格納できる配列を用意する
int[] work = new int[rangeEnd - rangeBegin + 1];
// 配列を初期化する
for (int n = rangeBegin, i = 0; n <= rangeEnd; n++, i++)
work[i] = n;
// ランダムに取り出しては先頭から順に置いていく(count回繰り返す)
var rnd = new Random();
for (int resultPos = 0; resultPos < count; resultPos++)
{
// (resultPosを含めて)resultPosの後ろからランダムに1つ選ぶ
int nextResultPos = rnd.Next(resultPos, work.Length);
// nextResultPosの値をresultPosと入れ替える
Swap(ref work[resultPos], ref work[nextResultPos]);
}
return work.Take(count); // workの先頭からcount個を返す
}
Sub Swap(ByRef m As Integer, ByRef n As Integer)
Dim work As Integer = m
m = n
n = work
End Sub
Function GetUniqRandomNumbers(rangeBegin As Integer, rangeEnd As Integer, count As Integer) As IEnumerable(Of Integer)
' 指定された範囲の整数を格納できる配列を用意する
Dim work(rangeEnd - rangeBegin) As Integer
' 配列を初期化する
Dim i As Integer = 0
For n As Integer = rangeBegin To rangeEnd
work(i) = n
i += 1
Next
' ランダムに取り出しては先頭から順に置いていく(count回繰り返す)
Dim rnd = New Random()
For resultPos As Integer = 0 To count - 1
' (resultPosを含めて)resultPosの後ろからランダムに1つ選ぶ
Dim nextResultPos As Integer = rnd.Next(resultPos, work.Length)
' nextResultPosの値をresultPosと入れ替える
Swap(work(resultPos), work(nextResultPos))
Next
Return work.Take(count) ' workの先頭からcount個を返す
End Function
ダステンフェルドのアルゴリズムは、配列中のランダムな位置を選び、その値を先頭から(あるいは、末尾から)再配置していくというものだ(Wikipedia日本語版では末尾から配置していく方法だけが記載されているが、上のコードは先頭から配置していく方法だ)。配列を全て並べ替える必要がないときは(例えば1から10の範囲で3個だけ生成するときなど)、必要な数が(先頭または末尾に)集まった時点で打ち切ればよい。上のコードでは、ループ回数をcount回に制限している。
なお、Randomクラス(System名前空間)はインスタンスを作るたびに異なる乱数系列を発生するようになっている。それは望ましい性質なのだが、デバッグ時には毎回同じ系列の乱数を生成してほしいこともある。そのようなときには、乱数のシードとして固定値を渡すようにするとよい(次のコード)。Randomクラスの詳細や、より偏りの少ない乱数を得る方法については、「.NET TIPS:乱数を生成するには?」を参照していただきたい。
#if DEBUG
var rnd = new Random(0); // デバッグでは、毎回同じ乱数列を生成させる
#else
var rnd = new Random();
#endif
#If DEBUG Then
Dim rnd = New Random(0) ' デバッグでは、毎回同じ乱数列を生成させる
#Else
Dim rnd = New Random()
#End If
上に掲載したダステンフェルドのアルゴリズムを使ったメソッドを実際に呼び出すコードは次のようになる。
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class Program
{
……省略(前述のメソッド)……
static void WriteNumbers(IEnumerable<int> numbers)
=> WriteLine(string.Join(", ", numbers));
static void Main(string[] args)
{
WriteLine("1〜10の整数から3個");
WriteNumbers(GetUniqRandomNumbers(1, 10, 3));
// 出力例: 8, 9, 2
WriteLine("-5〜5の整数から11個");
WriteNumbers(GetUniqRandomNumbers(-5, 5, 11));
// 出力例: 2, 4, 3, -5, 0, -3, 5, -1, 1, -4, -2
WriteLine("1〜52の整数から10個");
WriteNumbers(GetUniqRandomNumbers(1, 52, 10));
// 出力例: 38, 43, 41, 31, 14, 32, 48, 27, 52, 21
#if DEBUG
ReadKey();
#endif
}
}
Imports System.Console
Module Module1
……省略(前述のメソッド)……
Sub WriteNumbers(numbers As IEnumerable(Of Integer))
WriteLine(String.Join(", ", numbers))
End Sub
Sub Main()
WriteLine("1〜10の整数から3個")
WriteNumbers(GetUniqRandomNumbers(1, 10, 3))
' 出力例: 8, 9, 2
WriteLine("-5〜5の整数から11個")
WriteNumbers(GetUniqRandomNumbers(-5, 5, 11))
' 出力例: 2, 4, 3, -5, 0, -3, 5, -1, 1, -4, -2
WriteLine("1〜52の整数から10個")
WriteNumbers(GetUniqRandomNumbers(1, 52, 10))
' 出力例: 38, 43, 41, 31, 14, 32, 48, 27, 52, 21
#If DEBUG Then
ReadKey()
#End If
End Sub
End Module
なお、ここでは整数を扱ったが、どんなオブジェクトでも構わない。例えば、トランプのカードを表すオブジェクトを配列に入れておけば、ランダムにシャッフルされたカードオブジェクトのコレクションが得られるというわけだ。
ダステンフェルドのアルゴリズムはちょっと難解なので、分かりやすいロジックも紹介しておこう。処理速度は遅いが、実用上はこれでも十分なことが多いだろう。
重複しないようにするには、1回取り出した値を取り除いてしまえばよい。指定された範囲の整数を格納したコレクションを作っておき、そこからランダムに1つ選んで値を取り出すとともにその値をコレクションから削除していけばよいのだ(次のコード)。
static IEnumerable<int> GetUniqRandomNumbersEasy(int rangeBegin, int rangeEnd, int count)
{
// 指定された範囲の整数で埋めたリストを用意する
List<int> work
= Enumerable.Range(rangeBegin, rangeEnd - rangeBegin + 1).ToList();
// workからランダムに取り出して、順に返していく(count回繰り返す)
var rnd = new Random();
for (int i = 0; i < count; i++)
{
// workからランダムに1つ選んで値を取り出す
int pos = rnd.Next(0, work.Count);
int value = work[pos];
work.RemoveAt(pos); // 取り出した値はリストから取り去る
// 取り出した値を順に返す
yield return value;
}
}
Iterator Function GetUniqRandomNumbersEasy(rangeBegin As Integer, _
rangeEnd As Integer, count As Integer) As IEnumerable(Of Integer)
' 指定された範囲の整数で埋めたリストを用意する
Dim work As List(Of Integer) _
= Enumerable.Range(rangeBegin, rangeEnd - rangeBegin + 1).ToList()
' workからランダムに取り出して、順に返していく(count回繰り返す)
Dim rnd = New Random()
For i As Integer = 0 To count - 1
' workからランダムに1つ選んで値を取り出す
Dim pos As Integer = rnd.Next(0, work.Count)
Dim value As Integer = work(pos)
work.RemoveAt(pos) ' 取り出した値はリストから取り去る
' 取り出した値を順に返す
Yield value
Next
End Function
上のメソッドをコンソールアプリから呼び出す例を示す(次のコード)。ダステンフェルドのアルゴリズムに掲載したコードと重複する部分は省略している。
WriteLine("1〜10の整数から3個");
WriteNumbers(GetUniqRandomNumbersEasy(1, 10, 3));
// 出力例: 8, 9, 7
WriteLine("-5〜5の整数から11個");
WriteNumbers(GetUniqRandomNumbersEasy(-5, 5, 11));
// 出力例: 2, 4, 1, -1, -4, 0, 5, -3, 3, -5, -2
WriteLine("1〜52の整数から10個");
WriteNumbers(GetUniqRandomNumbersEasy(1, 52, 10));
// 出力例: 38, 43, 40, 28, 10, 29, 48, 21, 52, 13
WriteLine("1〜10の整数から3個")
WriteNumbers(GetUniqRandomNumbersEasy(1, 10, 3))
' 出力例: 8, 9, 7
WriteLine("-5〜5の整数から11個")
WriteNumbers(GetUniqRandomNumbersEasy(-5, 5, 11))
' 出力例: 2, 4, 1, -1, -4, 0, 5, -3, 3, -5, -2
WriteLine("1〜52の整数から10個")
WriteNumbers(GetUniqRandomNumbersEasy(1, 52, 10))
' 出力例: 38, 43, 40, 28, 10, 29, 48, 21, 52, 13
気になるのは処理速度の違いだろう。コレクションから要素を取り去る操作は時間がかかるので、ダステンフェルドのアルゴリズムよりも遅いと予想できる。実際に、次のようなコードをリリースビルドして何回か実行してみてもらいたい。十倍以上の速度差があるのだが、10万個を取得しても大して待たされないはずだ。数千個のオーダーまでであれば、どちらのロジックを使っても実用上の差は出ないだろう。
WriteLine("10万個の整数から10万個");
var stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
var results1 = GetUniqRandomNumbers(1, 100000, 100000).ToList();
stopwatch.Stop();
WriteLine($"GetUniqRandomNumbersで{results1.Count/10000}万個: {stopwatch.ElapsedMilliseconds}mSec");
GC.Collect();
stopwatch.Restart();
var results2 = GetUniqRandomNumbersEasy(1, 100000, 100000).ToList();
stopwatch.Stop();
WriteLine($"GetUniqRandomNumbersEasyで{results2.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec");
WriteLine("10万個の整数から10万個")
Dim stopwatch = New System.Diagnostics.Stopwatch()
stopwatch.Start()
Dim results1 = GetUniqRandomNumbers(1, 100000, 100000).ToList()
stopwatch.Stop()
WriteLine($"GetUniqRandomNumbersで{results1.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec")
GC.Collect()
stopwatch.Restart()
Dim results2 = GetUniqRandomNumbersEasy(1, 100000, 100000).ToList()
stopwatch.Stop()
WriteLine($"GetUniqRandomNumbersEasyで{results2.Count / 10000}万個: {stopwatch.ElapsedMilliseconds}mSec")
指定した範囲の整数から重複しない乱数を生成するロジックを2つ紹介した。ダステンフェルドのアルゴリズムは高速だがちょっと難解だ。本稿の後半で示したように、まず分かりやすいロジックで実装し、実際の処理時間を計測し、その処理速度では問題だと判明してから高速化に取り組もう。
利用可能バージョン:.NET Framework 3.5以降
カテゴリ:クラスライブラリ 処理対象:乱数
使用ライブラリ:Randomクラス(System名前空間)
関連TIPS:乱数を生成するには?
関連TIPS:Listに要素を追加/挿入するには?[C#/VB]
関連TIPS:一時ファイル用のランダムなファイル名を生成するには?[2.0のみ、C#、VB
関連TIPS:処理時間を正確に計測するには?[2.0のみ、C#、VB]
関連TIPS:Stopwatchクラスで時間計測をリセットして再開するには?[4以降、C#、VB]
関連TIPS:構文:クラス名を書かずに静的メソッドを呼び出すには?[C# 6.0]
関連TIPS:VB.NETでクラス名を省略してメソッドや定数を利用するには?
関連TIPS:数値を右詰めや0埋めで文字列化するには?[C#、VB]
関連TIPS:構文:メソッドやプロパティをラムダ式で簡潔に実装するには?[C# 6.0/7.0]
関連TIPS:Visual Studioでコンソール・アプリケーションのデバッグ実行時にコマンド・プロンプトを閉じないようにするには?
Copyright© Digital Advantage Corp. All Rights Reserved.