FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Unity »【Unity】【C#】配列・リストのシャッフル

【Unity】【C#】配列・リストのシャッフル  


 簡易音楽プレイヤーのデモを作っていて気づいたんだけど、C# にはシャッフル(Shuffle())の標準メソッドは無いのね。Java には Collections.shuffle() のメソッドがあるので、つい探してしまった…。あと要素のスワップ(Swap())も Java には標準であるんだよね(Collections.swap())。ちなみに私はプラグイン開発してるときは Java と C# を同時に書いているので、たまに混同する(笑)(実際に AndroidStudio とVisualSutdio の両方を開いている)。まぁ簡単に作れるものだけど、毎回書くのも面倒なのでとりあえずメモ的に残して置こうと思った。



(※) Unity 5.6.3p1 - 2018.1.5f1 / Windows10(x64) で確認



■配列のシャッフル

●配列のシャッフル(UnityEngine.Random / 拡張メソッド版)
using UnityEngine;
using Random = UnityEngine.Random;

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
//配列の要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this T[] arr)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
T tmp = arr[i]; //swap
arr[i] = arr[j];
arr[j] = tmp;
}
}
}


//メインでは・・・
using System.Linq;

int[] arr = { 0, 1, 2, 3, 4, 5 };
for (int i = 0; i < 5; i++)
{
arr.Shuffle();
Debug.Log(arr.Select(e => e.ToString()).Aggregate((s, a) => s + ", " + a));
}

4, 3, 1, 5, 2, 0
5, 4, 3, 2, 0, 1
0, 3, 5, 1, 2, 4
1, 5, 0, 2, 4, 3
0, 1, 2, 4, 3, 5

 使っているアルゴリズムは有名な「フィッシャー–イェーツのシャッフル」(英:Fisher–Yates shuffle)である。詳細は Wikipedia を見て欲しいが、簡単に言えばインデクス(i)を後ろから1つずつ前方へ移動しながら、0~i の範囲(終点は[1](と[0]))でランダムに要素をスワップするアルゴリズムである。オーダーは O(n) なので巨大な配列で毎フレーム更新とかではなければ(笑)、それほど負荷は無いだろう。音楽プレイヤーではどの様に使ってるかというと、曲順を1度シャッフルして、その順番に再生し、最後まで行ったらまたシャッフル…を繰り返しているだけである。なので、ほとんど負荷は無いと言って良い。そういう使い方の場合、何の問題も無いと考えて良いだろう(Unityの様な毎フレーム更新のアプリケーションはなるべくオーダーの小さいアルゴリズム[O(1)とかO(logn)とか]を採用する方が良い)。

 またついでなので要素のスワップも定義して置くと、以下のように簡潔に書ける。

●配列のシャッフル+要素のスワップ(UnityEngine.Random / 拡張メソッド版)
using UnityEngine;
using Random = UnityEngine.Random;

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
//配列の要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this T[] arr)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
arr.Swap(i, j);
}
}

//要素のスワップ
public static void Swap<T>(this T[] arr, int i, int j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}

//メインは同じ(※略)

 なお、ここでは拡張メソッドを用いているが、通常のメソッドで書くと以下のようになる。

●配列のシャッフル(UnityEngine.Random / 通常メソッド版)
・・・(略)・・・
public class Extensions //※通常メソッドの場合、static でなくても可
{
//配列の要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(T[] arr)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
Swap(arr, i, j);
}
}

//要素のスワップ
public static void Swap<T>(T[] arr, int i, int j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}

//メインでは・・・
・・・(略)・・・
Extensions.Shuffle(arr); //※クラス名は任意の定義による
・・・(略)・・・

拡張メソッドは便利だが、増えすぎるとかえって邪魔になることもあるので、汎用性の高いものだけにすると良いだろう。

 あと、ここでは Unity用にランダム関数は UnityEngine.Random を使っているが、C#標準の System.Random を使いたい場合、以下のように書くこともできる。

●配列のシャッフル+要素のスワップ(System.Random / 拡張メソッド)
using UnityEngine;
using Random = System.Random; //ここでエイリアスにしておくと表記が楽

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
static Random rand = new Random(); //※毎回 new するならいっそ static で利用する

//配列の要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this T[] arr)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int j = rand.Next(i + 1); //[0]~[i]
arr.Swap(i, j);
}
}

//スワップは拡張メソッドと同じ(※略)
}

//メインは同じ(※略)

 System.Random の場合は毎回 new しなくてはならないので、いっそ static で使い回しした方が良いだろう。もちろん「Shuffle<T>(this T[] arr, Random rand)」のように引数にランダムジェネレータを与えるようにしても良いと思う(他の言語を含め、標準関数にはそういうものが多い)。

 が、まぁしかし、Unity を使っている分には「UnityEngine.Random」の方が簡単だし、円状とか球状とか便利なので迷わず使っても良いだろう。また数が少ない場合、UnityEngine.Random の方が良い感じに乱数が出るという話もある。こういった実験は私もよくやるのだが、情報を公開してくれていると非常に有り難い(笑)。なので私も複数の書き方やアルゴリズムを試したりしてるわけだ(といってもアルゴリズム系の記事は Java の方が多いが[※思いつきでやるのでたまたま])。以下に参考資料も載せておこう。

(参考)Unityの乱数が本当にランダムかどうか見てみた



■リストのシャッフル

●リストのシャッフル(UnityEngine.Random / 拡張メソッド版)
using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
//リストの要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this List<T> list)
{
for (int i = list.Count - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
}


//メインでは・・・
using System.Linq;

List<int> list = new List<int>() { 0, 1, 2, 3, 4, 5 };
for (int i = 0; i < 5; i++)
{
list.Shuffle();
Debug.Log(list.Select(e => e.ToString()).Aggregate((s, a) => s + ", " + a));
}

4, 3, 1, 5, 2, 0
5, 4, 3, 2, 0, 1
0, 3, 5, 1, 2, 4
1, 5, 0, 2, 4, 3
0, 1, 2, 4, 3, 5

 やっていることは配列のシャッフルと変わらないので、説明はいらないだろう。一瞬、IEnumerable で書くことも頭をよぎったが、そもそもシャッフルの対象となるのは静的配列かリストが最も多い。特に拡張メソッドで書くと入力候補もどんどん増加してしまうので、用途が限定されるならこれで十分と思った。まぁ、必要なら好きに改造してくれたまい(笑) [※たぶんコードが煩雑になる]。

 リストのスワップ定義も配列と同じようにやってみると、随分簡潔になる。

●リストのシャッフル+要素のスワップ(UnityEngine.Random / 拡張メソッド版)
using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
//リストの要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this List<T> list)
{
for (int i = list.Count - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
list.Swap(i, j);
}
}

//要素のスワップ
public static void Swap<T>(this List<T> list, int i, int j)
{
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}

//メインは同じ(※略)

 もちろん、配列のときと同じように通常のメソッドで書くには以下のようになる。

●リストのシャッフル(UnityEngine.Random / 通常メソッド版)
・・・(略)・・・
public class Extensions
{
//リストの要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(List<T> list)
{
for (int i = list.Count - 1; i > 0; i--)
{
int j = Random.Range(0, i + 1); //[0]~[i]
Swap(list, i, j);
}
}

//要素のスワップ
public static void Swap<T>(List<T> list, int i, int j)
{
T tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}

//メインでは・・・
・・・(略)・・・
Extensions.Shuffle(list); //※クラス名は任意の定義による
・・・(略)・・・

 ついでに C#標準の System.Random を使う場合、配列のときと同じように以下のように書ける。

●配列のシャッフル+要素のスワップ(System.Random / 拡張メソッド)
using UnityEngine;
using Random = System.Random; //ここでエイリアスにしておくと表記が楽

public static class Extensions //拡張メソッド用 static クラス(名前は任意)
{
static Random rand = new Random(); //※毎回 new するならいっそ static で利用する

//リストの要素をシャッフルする (Fisher-Yates shuffle)
public static void Shuffle<T>(this List<T> list)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int j = rand.Next(i + 1); //[0]~[i]
arr.Swap(i, j);
}
}

//スワップは拡張メソッドと同じ(※略)
}

//メインは同じ(※略)

 これも配列のときと同じように「Shuffle<T>(this List<T> list, Random rand)」のように引数にランダムジェネレータを与えるようにしても良いと思う。だがまぁ、「UnityEngine.Random」の方を使った方が楽だろう。

 ちなみに配列版の方が2倍くらい速いので、動的に要素数を変更する必要がないのなら、配列を用いた方が良いだろう(※基本的に配列と List で全く同じアルゴリズムでやってみると、配列の方が2~3倍ほど処理が速い)。


 ゲームの場合、アイテムドロップに直接ランダム関数を用いることも多いと思うが、アイテムのインデクスの確率テーブルなどを作ってシャッフルすれば、全体としては確実に分布が行き渡るので、そういう使い方も良いかもね(例えばテーブルを {0,0,0,1,1,2} としてシャッフル→順番に取り出せば、確実に 3:2:1 の分布でアイテムが出る=直接ランダムの場合、回数が多くなるほど確率は正しくなるが、少ない回数では偏ることもあるため)。

 音楽プレイヤーのシャッフルなんかも直接ランダムの場合、曲数少ないと「A-B-A-A-B-C」(=3曲を6回ランダム再生)のように偏ることもあるが、シャッフルで {A,C,B}+{C,A,B} のようにすれば(=3曲を2回シャッフルで順に再生)偏りは減る(末尾と先頭が連続することはあるが、全体的にはバラバラ順に聞こえる)。プラグイン(ver.1.16以降)の簡易音楽プレイヤーでもそのまま実装しているので、興味があったらダウンロードしてビルドして試してみるのも良いだろう(※好きに改造して貰っても構わない)。


※他、様々な機能を使ったデモが同梱。Unity×Androidアプリ開発に!

※サンプルで使っているループ曲を含んだライブラリも配信中。全31曲!




(関連記事)
【Unity】AssetStore版 FantomPlugin のセットアップ
【C#】連想配列(Dictionary)を値 or キーでソート
【C#】2次元配列(ジャグ配列・多次元配列)のソート
【C#】多次元配列とジャグ配列(2次元配列)のサイズ(長さ)、相互変換など
【Java】配列要素の反転(reverse)


このコンテンツの一部には『ユニティちゃんライセンス』で許諾されたアセットが使用されています。
Portions of this work are licensed under Unity-Chan License


スポンサーサイト

category: Unity

thread: ゲーム開発

janre: コンピュータ

tag: Unityライブラリ  C#ライブラリ  アルゴリズム 
tb: 0   cm: --



トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/298-d3b880f7
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop