SwiftでFunctionalといえどデータは使い捨てない方がいい理由

これ、私好みでもあるのですが…

Swiftで一次元配列を評価して二次元配列を生成する方法 - koherさんのコメント

僕がやるなら↓のような感じでしょうか。

extension SequenceType {
    typealias E = Generator.Element
    func groupBy<K: Hashable>(key: E -> K) -> [[E]] {
        return self.reduce([:]) { (var r: [K: [E]], x) in
            let k = key(x)
            r[k] = (r[k] ?? []) + [x]
            return r
        }.map { _, v in v }
    }
}
sampleArray.groupBy { "\($0.y)-\($0.m)" }

var を parameter で使う以上の問題があります。

それは、配列を使い捨てていること。 (r[k] ?? []) + [x]するたびに、古いr[k]に入っていたArrayが捨てられています。

「これってパフォーマンスに響くよねえ」と脊髄反射でベンチマークしてみたところ、こんな結果が。

Classic: [false: [1, 3, 5, 7], true: [0, 2, 4, 6]]
Stylish: [false: [1, 3, 5, 7], true: [0, 2, 4, 6]]
n = 1:
  Classic: 0.00138282775878906sec
  Stylish: 0.0041651725769043sec
  Stylish/Classic = 3.01206896551724
n = 10:
  Classic: 0.019071102142334sec
  Stylish: 0.0423140525817871sec
  Stylish/Classic = 2.21875234404301
n = 100:
  Classic: 0.198259830474854sec
  Stylish: 0.365303993225098sec
  Stylish/Classic = 1.84255172795294
n = 1000:
  Classic: 1.90600895881653sec
  Stylish: 3.60802412033081sec
  Stylish/Classic = 1.89297332714065

ベンチマーク対象なのは

(0..<n).groupBy{ $0 % 2 == 0 }

に相当するコードで、配列使い捨て版(sortByStylish)と配列使い回し版(sortByClassic)を比較しています。

なんちゃってなベンチマークではありますが、ほぼ倍の差が出ています。なお groupBy は、元発言主が求めていた Ruby の Enumerable#group_by と同様、再配列化はせずDictionaryをそのまま返すようにしてあります。

それにしても、PerlとかRubyの

$hash{$key} ||= []

に相当するエレガントな書き方ないっすかねえ。

just-a-thought

hash[key] ??= []
hash[key]!.append(value)

みたいに書ければいいんですが…

extension_Dictionary

extension Dictionary {
    mutating func defaultValue(key:Key, _ value:Value)->Bool {
        if self[key] == nil {
            self[key] = value
            return true
        } else {
            return false
        }
    }
}
// ...
hash.defalutValue(key,[]) // defaultは予約語なので使えない:(
hash[key]!.append(value)

というのは動くにゃ動くのですがなんか泥臭い…

Dan the Crusty Swift Programmer

benchmark.swift

今回のベンチマークに使ったコードです。そのまま script として実行しています。LinuxのSwift 2.2でも

 warning: Use of 'var' binding here is deprecated and will be removed in a future version of Swift
        return self.reduce([:]) { (var r:[K:[Generator.Element]], x) in
                                   ^~~

というwarningが出ますが動きます。

timeit()の引数を1000から100に減らしたら IBM Swift Sandbox でもタイムアウトにならずに動いたのでリンク貼っときます。

• http://swiftlang.ng.bluemix.net/#/repl/0f492b52c65c28c63b8b6a003bb1e801d4f628e2658d211977ff6f1f959c448f

benchmark.swift

#!/usr/bin/env swift

extension SequenceType {
    func groupByClassic<K:Hashable> (
        keygen: Generator.Element -> K
    ) -> [K:[Generator.Element]] {
        var result = Dictionary<K,[Generator.Element]>()
        for value in self {
            let key = keygen(value)
            if result[key] == nil {
                result[key] = [value]
            } else {
                result[key]!.append(value)
            }
        }
        return result
    }
    func groupByStylish<K:Hashable>(
        key:Generator.Element -> K
    ) -> [K:[ Generator.Element]] {
        return self.reduce([:]) { (var r:[K:[Generator.Element]], x) in
                   let k = key(x)
                   r[k] = (r[k] ?? []) + [x]
                   return r
            }
    }
}

print("Classic:",(0..<8).groupByClassic{ $0 % 2 == 0 })
print("Stylish:",(0..<8).groupByStylish{ $0 % 2 == 0 })

#if os(Linux)
import Glibc
#else
import Foundation
#endif

func now()->Double {
    var tv = timeval()
    gettimeofday(&tv, nil)
    return Double(tv.tv_sec) + Double(tv.tv_usec)/1e6
}

func timeit(count:Int, task:()->())->Double {
    let started = now()
    for _ in 0..<count { task() }
    return now() - started
}

for e in 0..<4 {
    let n = Int(pow(10.0,Double(e)))
    let tc = timeit(1000) {
        (0..<n).groupByClassic{ $0 % 2 == 0 }
    }
    let ts = timeit(1000) {
        (0..<n).groupByStylish{ $0 % 2 == 0 }
    }
    print("n = \(n):")
    print("  Classic: \(tc)sec")
    print("  Stylish: \(ts)sec")
    print("  Stylish/Classic = \(ts/tc)")
}