趣旨

F#でリストのシャッフルをしたい！
生成したリストは不変であるという前提の上で、どうやったらうまく実装できるのか考えてみる
あとは処理速度も比較してみようという試み。

リポジトリはこちら
git clone https://aoi_erimiya@bitbucket.org/aoi_erimiya/f-shuffle.git

考えたパターン

自分なりに４つほどパターン考えました(最初のやつはDomemo実装時のもの)
→(2018/08/03 追記)
　Twitterでぜくる(@zecl)さんから教えていただいた、パターン5追加
→(2018/08/06 追記)
　友人(@sakurasumizome)が考案したC#実装を置き換えてパターン6,7追加
教えていただきありがとうございます☆
→(2018/08/16 追記)
　新たに思いついたパターン8を追加

パターン1:シャッフル済みの状態でリストを生成する
パターン2:Linqを使う
パターン3:普通にSwapする
パターン4:先に移動先を決めてから一個ずつ移動させる
パターン5:Arrayに変換してSwap
パターン6:IComparableでランダムソート
パターン7:範囲カットソート
パターン8:シャッフル済みの状態でリストを生成(カウンタ方式)

計測コードはこんな感じ

どのコードも、元となるリスト生成から標準出力に結果書き出すまでを測ってます。

for i in 1..10 do
    let sw = new System.Diagnostics.Stopwatch();
    sw.Start();
    
    // -----------------------------------------------------
    //カード生成->シャッフル処理->結果出力のロジック
    // -----------------------------------------------------
    sw.Stop();
    printfn "%d" sw.ElapsedMilliseconds

→(2018/08/15 追記)@vain0xさんの記事を見て、stopwatchを使った計測からBenchmarkDotNetの計測に変えました。
いちいちループ処理書かなくても、自動ですごい回数を試行してくれるので楽ちん。
※クラス化しないといけないのは、ちょっと面倒だけども
F# でベンチマークをとる

実行速度はこの通り

→(2018/08/06 追記)Debugビルドで処理時間計測していたので、Releaseビルドで再計測
※単位はms

※1 戻り値の型は他の実装と異なる
※2 戻り値をArray型のままとした場合の結果

→(2018/08/15 追記)BenchmarkDotNet使ったらまったく異なる結果に。
BenchmarkDotNet=v0.11.0, OS=Windows 10.0.17134.165 (1803/April2018Update/Redstone4)
Intel Core i7-6700 CPU 3.40GHz (Max: 3.41GHz) (Skylake), 1 CPU, 8 logical and 4 physical cores
Frequency=3328130 Hz, Resolution=300.4690 ns, Timer=TSC
[Host] : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3131.0
DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3131.0

※1 Stopwatchによる計測結果。計測できる単位も違うし結果に差がありすぎる…！
　　ただし、Stopwatchでの計測時は、結果を標準出力する処理も含まれているので、多少早くなるのは間違いない。
　　BenchmarkDotNetで標準出力の処理を残していると、計測中にエラー乱舞になったので削除している。
※2 戻り値をArray型のままとした場合の結果

パターン1:Shuffled 最初からシャッフル済みのリストを作る(39,443.3ns)

let rand = Random()

let mutable cards = [1;2;3;4;5;6;7]
while cards.Length < 28 do
    let randCard = rand.Next(1, 8)
    List.countBy (fun elem -> if (elem = randCard) then 1 else 0) cards
    |> List.filter (fun tpl -> fst(tpl) = 1 && snd(tpl) < randCard)
    |> List.iter (fun x -> cards <- List.append [randCard] cards)
    |> ignore
        
showCards("Shuffled", cards) |> ignore

なんとなくわかってはいたけど、こいつが一番遅い！
一番F#っぽくて、スマートだと思うんだけどなぁ。
(乱数生成→リストの中に何個あるか数える→カウント数が必要数未満なら追加)
とはいっても、Domemoにおけるカード種類の制約があるから成り立ってるコードだけども。
※1~7の7種類のカードがあり、それぞれ数字の枚数だけ同じカードが存在するという前提。
頑張ったらもうちょっと高速化できるのだろうか。

パターン2:Linqを使う(12,005.8ns)

let rand = Random()

let mutable cards = []
for i in 1..7 do
    for _ in 1..i do
        cards <- List.append [i] cards

let mutable shuffledCards = []
let shuffledGenericCards: ResizeArray<int32> = cards.OrderBy(fun _ -> Guid.NewGuid()).ToList()
shuffledGenericCards.ForEach(fun x -> shuffledCards <- List.append [x] shuffledCards)

showCards("Linq    ", shuffledCards) |> ignore

他の追随を許さない記述の簡潔さ
でも、.NetのCollectionとF#のCollectionが別モノな事を知って驚き。
ForEach挟まなかったら、もうちょい早くなる気がする。
.ToList()みたいに一発で変換できたらもっと素敵なんだけどなぁ。

パターン3:Swapする(20,451.8ns)

let rand = Random()

let mutable cards = []
for i in 1..7 do
    for _ in 1..i do
        cards <- List.append [i] cards

let mutable swapCards = cards
let cardsLength = cards.Length-1
for i in 0..cardsLength  do
    let targetIdx = rand.Next(0, cards.Length)
    if not (targetIdx = i) then
        if i < targetIdx then
            swapCards <- List.append(List.append (List.append (List.append swapCards.[0..i-1] swapCards.[targetIdx..targetIdx]) swapCards.[i+1..targetIdx-1]) swapCards.[i..i]) swapCards.[targetIdx+1..cardsLength]
        else
            swapCards <- List.append(List.append (List.append (List.append swapCards.[0..targetIdx-1] swapCards.[i..i]) swapCards.[targetIdx+1..i-1]) swapCards.[targetIdx..targetIdx]) swapCards.[i+1..cardsLength]

showCards("Swap    ", swapCards) |> ignore

基本に忠実にやってみたものの、appendの雨あられになるのは何とかならないものか。
やってる事は簡単なはずなのに、必要以上に複雑なコードに見えてしまう。

パターン4:Bucket 先に移動先を決めてから一個ずつ移動(11,757.2ns)

let rand = Random()

let mutable cards = []
for i in 1..7 do
    for _ in 1..i do
        cards <- List.append [i] cards

let mutable idxBucket = []
let cardsLength = cards.Length
let rec loop() = 
    if idxBucket.Length = cardsLength then
        ()
    else
        let targetIdx = rand.Next(0, cardsLength)
        let isFindIdx = List.exists (fun idx -> idx = targetIdx) idxBucket
        if not isFindIdx then    
            idxBucket <- List.append [targetIdx] idxBucket
        loop()
loop()

let mutable bucketSortCards = []
for i in 0..cardsLength-1 do
    bucketSortCards <- List.append [cards.Item(idxBucket.Item(i))] bucketSortCards

showCards("Bucket  ", bucketSortCards) |> ignore

ちょっとでも関数型っぽくしようとして、再帰で書いてみた
乱数の生成のされ方によってはパフォーマンスばらつくけど、なんかLinqより早い。
移動先のインデックスだけ先に決めて、一個ずつ移動させる作戦。
個人的にバケツソート好きなので、こういうコード書くの大好き

パターン5:Arrayに変換してからSwap(1,959.8ns)

let rand = Random()

let mutable cards = []
for i in 1..7 do
    for _ in 1..i do
        cards <- List.append [i] cards

let swap (array: _[]) x y =
    let tmp = array.[x]
    array.[x] <- array.[y]
    array.[y] <- tmp

// shuffle an array (in-place)
let shuffle array =
    Array.iteri (fun i _ -> swap array i (rand.Next(i, Array.length array))) array

let cardArray = List.ToArray cards
shuffle cardArray
showCards("Array  ", Array.toList cardArray) |> ignore

誰が見てもわかりやすいSwapのロジック！
パターン3と同じ事してるはずなのに圧倒的に速い。
一旦配列に変換する発想がなかったので、目からウロコ。
専門家に見てもらうのって本当に大事ですね

パターン6:IComparableでランダムソート(568.8ns)

[<AbstractClass; Sealed>]
type Math private() =
    static let rand = Random();
    static member Next(arg : int) : int =
        rand.Next(arg)

type CardNumber<[<EqualityConditionalOn; ComparisonConditionalOn >]'T>(value : 'T) =
    member x.Value = value

    override x.Equals(comparisonObject) = 
        match comparisonObject with
        | :? CardNumber<'T> as y -> Unchecked.equals x.Value y.Value
        | _ -> false

    override x.GetHashCode () =
        Unchecked.hash x.Value

    interface System.IComparable with
        member x.CompareTo _ = 
            match Math.Next(2) = 0 with
            | true -> -1
            | _ -> 1
    
    override x.ToString () =
        x.Value.ToString()

[<EntryPoint>]
let main argv = 
    let mutable cards = []
    for i in 1..7 do
        for _ in 1..i do
            cards <- List.append [(CardNumber(i))] cards

    let mutable shuffledCards = List.sort cards
    shuffledCards |> List.iter (fun card -> printf "%d," card.Value)
    printfn ""

友人からC#実装で送られてきた方法1。(最速)
Icompatibleを利用して、比較時にランダムな結果を返して並べ替える。
かなり高速だけど、戻り値がラッパークラスになるので、他のパターンと単純比較はできず。

折角の.Netだからこんな実装もアリだと思う。
F#におけるstaticクラスとか、Icompatibleの実装の仕方とかめちゃ勉強になりました。
ただ、F#実装に書き換えるのに結構時間かかった

パターン7:範囲カットソート(953.0ns)


let showCards(label:string, cards:List<int>) =
    printf "%s -> " label
    cards |> List.iter (fun card -> printf "%d," card)
    printfn ""

[<AbstractClass; Sealed>]
type Math private() =
    static let rand = Random();
    static member Next(arg : int) : int =
        rand.Next(arg)

[<EntryPoint>]
let main argv = 
    let arrayLength = 28
    let cards = Array.create arrayLength 0
    for i in 1..7 do
        for j in 0..i do
            if j < i then
                cards.[i * (i-1)/2 + j] <- i
    
    let shuffledCards = Array.create arrayLength 0
    for i in 0..arrayLength - 1 do
        let rand = Math.Next(arrayLength - i)
        shuffledCards.[i] <- cards.[rand]
        cards.[rand] <- cards.[arrayLength - i - 1]
    
    //ver.Array
    //shuffledCards |> Array.iter (fun card -> printf "%d," card)
    //printfn ""
    
    //ver.List
    showCards("Array  ", Array.toList shuffledCards) |> ignore

友人からC#実装で送られてきた方法2。
移動させるインデックスを求めた後、一番最後の要素を移動したところに代入して
ループが進むたびに置き換え範囲を削っていくスタイル。
めっちゃ高速で無駄がなく、いいアルゴリズムだなと感動しました
※ただし、元々の配列を書き換えていき、原型が残らないので利用場面は要検討。

挙動メモ

cards = 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7

i = 0
rand.Next(28) -> 25
result = [7]
cards = 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7

i = 1
rand.Next(27) -> 4
result = [7,3]
cards = 1,2,2,3,7,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7(無視)

i = 2
rand.Next(26) -> 16
result = [7,3,6]
cards = 1,2,2,3,7,3,4,4,4,4,5,5,5,5,5,6,7,6,6,6,6,7,7,7,7,7,7(無視),7(無視)

パターン8:シャッフル済みの状態でリストを生成(カウンタ方式)(4,128.8 ns)

type CardPair = {cardNumber:int; mutable cardCount:int}
let useCard(x:CardPair) = x.cardCount <- x.cardCount - 1

let patternShuffled2() = 
    let arrayLength = 28
    let cards = Array.create arrayLength {cardNumber = 0; cardCount = 0}
    let mutable arrayIndex = 0
    for i in 1..7 do
        for _ in 1..i do
            cards.[arrayIndex] <- {cardNumber = i; cardCount = i}
            arrayIndex <- arrayIndex + 1

    let shuffledCards = Array.create arrayLength 0

    cards |> Array.iter
        (fun cardPair -> 
            let rec loop() = 
                let rand = Math.Next(28)
                if shuffledCards.[rand] = 0 then
                    shuffledCards.[rand] <- cardPair.cardNumber
                    ()
                else
                    loop()
            loop()
        )

パターン1の考え方を元に、無駄なループ回数を減らそうとした結果。
パターン4の配列スワップには敵わないものの、Linqより速い実装が作れて自己満足

やってみて

ロジックに対して

一番F#っぽいと思って書いてた処理が一番遅くて悲しい！
F#愛が深まればもっと高速に書けるようになるかも

友人によるC#実装ではパターン6よりパターン7のほうが早いはずだけど、F#では正反対の結果に。
ここの謎はまた解明する必要がありそう。

自分では最大限知恵を振り絞ったつもりだったけども
色んな人から違う解法を提示してもらってすごく勉強になりました。

計測について

Stopwatchによる計測で驚いたのは、どのパターンにおいても初回ループだけコストがやたらと重いこと。
ListとかArrayとかの関数呼び出すにあたっての、内部オブジェクト生成コストがすごいのかも？
評価軸をどこに置けばいいのか悩んだので、最終的には初回ループ含めた全体平均で評価しました。

また、stopwatchを使った計測からBenchmarkDotNetの計測に変えるだけでがらりと結果が変わった。
平均値勝手に取ってくれるので、計測する際はこれ一択かなと。

ご意見など

F#の専門家の方、もっと綺麗に書けるよとかご意見ありましたら
ぜひ教えてください！！