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

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

2018/06/28 Thu [edit]


　簡易音楽プレイヤーのデモを作っていて気づいたんだけど、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)を後ろから１つずつ前方へ移動しながら、0～i の範囲（終点は[1](と[0])）でランダムに要素をスワップするアルゴリズムである。オーダーは O(n) なので巨大な配列で毎フレーム更新とかではなければ(笑)、それほど負荷は無いだろう。音楽プレイヤーではどの様に使ってるかというと、曲順を１度シャッフルして、その順番に再生し、最後まで行ったらまたシャッフル…を繰り返しているだけである。なので、ほとんど負荷は無いと言って良い。そういう使い方の場合、何の問題も無いと考えて良いだろう（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」の方を使った方が楽だろう。

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


　ゲームの場合、アイテムドロップに直接ランダム関数を用いることも多いと思うが、アイテムのインデクスの確率テーブルなどを作ってシャッフルすれば、全体としては確実に分布が行き渡るので、そういう使い方も良いかもね（例えばテーブルを {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#】２次元配列（ジャグ配列・多次元配列）のソート
【C#】多次元配列とジャグ配列（２次元配列）のサイズ（長さ）、相互変換など
【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ブログユーザー)

| h o m e |

プロフィール

ヽ｜∵｜ゝ Fantom

Author:ヽ｜∵｜ゝ Fantom
誰もが好きなことをやって、そこから沢山の才能が生まれたら、きっと面白い世界になると思う

Social


SOUND CLOUD



(Fantom工房)

検索フォーム


全記事一覧

全ての記事を表示する

カテゴリ

VRMLiveViewer (16)
Unity (167)
C# (18)
VisualStudio (10)
Java (53)
Android (46)
Applet (4)
UnrealEngine (4)
Ruby (2)
プログラミング (4)
ゲーム (12)
環境構築 (7)
トラブルシューティング (8)
未分類 (3)

ユーザータグ

Unityライブラリ Unityリファレンス Unityプラグイン Unityトラブルシューティング 算術関数 FantomPlugin C# サンプル アルゴリズム 配列操作 VRMLiveViewer トラブルシューティング Unityオープンソースライブラリ C#ライブラリ InputSystem エディタ拡張 グラフィックス 開発ツール 一覧 VisualStudioリファレンス 画像ファイル読み込み テキストファイル読み込み uGUI 最短経路 SDカード インスペクタ 連想配列 クエリちゃん ユニティちゃん 練習問題 InputManager 約数 C#リファレンス VRoid VR VRM 二分探索 Unityバグ 背景3Dモデル 検証 Transform テキストファイル保存 内部ストレージ Windows インストール プロ生ちゃん PHP 素数 通信 JavaScript カメラスクリプト Java 画像ファイル保存 JSON UnrealEngine GLB 数列 ソート 幅優先探索 パズル解法 動的計画法 Eclipse 図解 ADT GearVR Androidライブラリ チュートリアル Android資料 オーディオファイル ストア申請 音声認識 データ構造 assets SourceTree べき乗 Git バージョン管理 cocos2d シェーダ Cardboard GLTF 文字列操作 Androidリファレンス Unity資料 AndroidStudio 東北ずん子 Python ニコニ立体ちゃん OpenGL データベース AR WebGL 深さ優先探索 Ruby WindowsAPI マテリアル Twitter mint SNS サウンド VRoidStudio Firebase 暗号化 HTMLリファレンス Javaライブラリ 

最新記事

リンク

このブログをリンクに追加する

PR

▲ Pagetop