Swift arrays are not lists

第2回 カジュアル Swift 勉強会 @ 青葉台で簡単に共有した内容をまとめました。
当日迷宮入りしてしまった部分も調査を進めましたので、ご興味あればご確認ください。

背景

Advanced Swiftを読んでいたら、mapはreduceを使うと簡単に実装できるよね、ということが書いてありました。

extension Array {
    func map2<U>(transform: Element ->U) -> [U] {
        return reduce([]) {
            $0 + [transform($1)]
        }
    }
}

そして、次にこんなことが書いてありました。

Swift is not Haskell, and Swift arrays are not lists.

Swiftのreduceは毎回新しいarrayを生成するため、パフォーマンスが出ないよ、ということがいいたいようです。
ただ、Haskellと比較してどう違うんだ?とか、Swiftのarrayがlistではないというのはどういうことだ?とか気になって調べていたら、色々発見がありました。

本題

まずは、いろいろな方法で実装したmapの速度を1000件程度で測ってみました。

gist.github.com

以下、解説します。

map2

まずはreduceを使ってmap2を実装しました。このレベルだと体感は大して変わりませんが、数字で見るとやはり遅いようです。(Playgroundだとコンパイルオプションが違ったりするのか、なぜか劇的な違いが出ます。ぜひお手元のXcode7で試してみてください。)

map3

次に、reduceを使わないものをmap3として実装しました。for文を回してresultにappendするシンプルなものです。しかし、僅かに標準map に速度が及びません。
Arrayのcapacityをappendの度に拡張するのがパフォーマンスの障害になっているのでしょうか。

map4

そこで、init(count: Int, repeatedValue: Element) を使ってmap4を実装しました。
resultのcapacityをあらかじめ確保しておけば、appendの度にメモリ確保することはないので速くなるはず、という理論です。
勉強会当日はこのあたりの最適化の方法が不慣れで時間を取ってしまったのですが、なんとか動かせました。
でも数字を見ると明らかなように、遅くなりました。

map5

こうなったらもう意地です。Google先生にお願いしました。
検索でヒットしたこちらの記事を参考に、map5を実装しました。
なんとdispatch_group_asyncでバッチ実行しています。その発想はありませんでした。

しかし・・・いずれもよい結果がでませんでした。

まとめ

結局、なぜ私のコードが標準 map に追いつけないのか、いったい標準mapはどういう実装になっているのかといったことは、残念ながら私の力不足で謎のままとなってしまいました。

Swift is not Haskell, and Swift arrays are not lists.

この一文に含まれる意味を汲み取れれば、もう少し見当もつくのかもしれないなと思い、今日も「すごいH本」を手に取るのでした。

以上です。