[UEFN][Verse]配列のシャッフル[2]フィッシャー－イェーツのシャッフルをVerseで実装する
前回は「乱数を重複無しで生成し、配列に格納する」というアルゴリズムをVerseで実装する方法を考えました。 せっかくなのでその続きで、単純に配列をシャッフルするアルゴリズムについても考えてみたいと思います。
念の為先に書いておくと、標準ライブラリにShuffle()関数が用意されているので、単に配列をシャッフルしたいだけであればこちらを使う方が良いでしょう。
今回は「フィッシャー－イェーツのシャッフル」と呼ばれるアルゴリズムをVerseで実装します[1]。
Verseコード実装
コードは以下の様になりました。FisherYatesShuffle()関数はint型の配列を引数に取り、その配列がシャッフルされた物を返します。
#フィッシャー－イェーツのシャッフル（Ａ）
FisherYatesShuffle(Source:[]int)<transacts>:[]int =
var ShaffleDeck :[]int = Source #1
for:
Head := 0..ShaffleDeck.Length-2 #2
RandomNumber := GetRandomInt(Head, ShaffleDeck.Length-1) #3
Temp := ShaffleDeck[Head] #4
set ShaffleDeck[Head] = ShaffleDeck[RandomNumber]
set ShaffleDeck[RandomNumber] = Temp
do:
return ShaffleDeck
以下コードの解説です。アルゴリズム自体の話は省略しているので、そちらについてはwikipediaをご覧下さい。
#1
フィッシャー－イェーツのシャッフルは、元の配列の中の値をswapしながら巡回していく点がポイントです。引数で受け取った配列sourceは定数のためこのままではswapできません。そのため一度変数に代入しなおしています。どう考えても効率悪いのですが、他に方法を思いつきませんでした。
#2
フィッシャー－イェーツのシャッフルの一般的な実装は配列の末端から先頭に向かって巡回するのですが、Verseのrange型が順行（min..max）しか受け付けないため、先頭から巡回させています。
#3
GetRandomInt(min, max)はmin以上max以下の整数をランダムに返す関数です。maxを含むので気を付けて下さい。
#4
最後の３行はShaffleDeck[Head]とShaffleDeck[RandomNumber]のswapです。
バリエーション
以下の様に、for式に配列を生成させる事で、swapしない形に書き直すことも出来ます。
#フィッシャー－イェーツのシャッフル（Ｂ）
FisherYatesShuffle(Source:[]int)<transacts>:[]int =
var ShaffleDeck :[]int = Source
for:
Head := 0..ShaffleDeck.Length-1
RandomNumber := GetRandomInt(Head, ShaffleDeck.Length-1)
Result := ShaffleDeck[RandomNumber]
set ShaffleDeck[RandomNumber] = ShaffleDeck[Head]
do:
Result
お分かりでしょうが、このコードは前回書いた物と極めて似ています[2]。forのジェネレーター（HeadのRange）が（Ａ）と異なっている点に注意してください。for式が配列を末端まで巡回する必要があるため、このようになっています。
印象としては（Ａ）の方が効率が良さそうです。ただ、これはちゃんと計測してみないとわからないかな……。というのは、var配列の一部を更新する時、内部的にどういう処理が起きているのかはっきりしていない為です。とはいえ、今のVerseでロジックのまともなパフォーマンス計測は出来るんだろうか……？
反省点
確実に言えるのは、定数配列を変数配列に変換する為にvar ShaffleDeck :[]int = Sourceとやっているのがイマイチすぎます。
なお、引数をvarで受けられないか試してみたんですが「mutableな引数はまだ実装されていません」というコンパイルエラーになりました。将来的には実装されるかも？
もっと言えば、「配列の中身をswapしながら巡回する」というの挙動が、そもそも関数型言語らしくないように思います。この辺詳しくないのですが、なにか上手いアルゴリズムがあるのかな？ 効率のことはいったん置いておいて[3]、Verseらしい配列シャッフルアルゴリズムを考えてみたい所です。
お知らせ
verse言語とUEFNの記事を他にも書いているので御覧下さい。
最後まで読んで頂きありがとうございました。この記事がお役に立てたようであれば、是非LIKEとフォローをお願いします（今後の執筆のモチベーションに繋がります）。
#Verse #UEFN #Fortnite #Verselang #UnrealEngine
宣伝
「Unityシェーダープログラミングの教科書」シリーズ１～５をBOOTHで頒布中です。
Discussion