Optimizing Collectionsを読んだ

Swift情報満載のobjc.ioで販売されている電子書籍のこちらを読みました。

www.objc.io

内容

Swiftで次のデータ構造を順に実装しながら、各種操作のパフォーマンスとその最適化方法について解説されています。

  • ソート済み配列 (Sorted array)
  • 順序集合 (Ordered set)
  • 赤黒木 (Red black tree)
  • B木 (B tree)

図やグラフもあって理解を助けてくれました。

特徴

Attabenchというツールを使って実際に計算時間を測定しながらパフォーマンスの遷移を確認しているので、その改善過程がわかりやすいです。アルゴリズム以外にもCPUのキャッシュなどによる影響についても触れられています。

また、各データ構造を実装するに当たりCopy On Writeも満たすように実装しているため、その部分でも勉強になりました。

その他学んだこと

CustomStringConvertibleプロトコル

CustomStringConvertibleプロトコルのdescriptionプロパティを実装しておくと、printなどでわかりやすく表示させることができます。

extension SortedSet {
    public var description: String {
        let contents = self.lazy.map { "\($0)" }.joined(separator: ",")
        return "[\(contents)]"
    }
}

同様にCustomPlaygroundQuickLookableプロトコルの実装により、Playgroundでの表示をわかりやすく変更できます。

Collectionプロトコル

Swiftで独自オブジェクトをコレクションとして扱うには、Collectionプロトコルに準拠する必要があります。 具体的には以下の実装が最低限必要です。

これだけで、for-inでの列挙やmap、filterなどの便利な処理が使えるようになります。

// 単純なコレクション
struct MinimumCollection {
    var values: [Int] = []
    
    init() {}
    init(values: [Int]) { self.values = values }
}

// Collectionプロトコル準拠
extension MinimumCollection: Collection {
    var startIndex: Int {
        return 0
    }
    
    var endIndex: Int {
        return values.count
    }
    
    subscript(i: Int) -> Int {
        return values[i]
    }
    
    func index(after i: Int) -> Int {
        return values.index(after: i)
    }
}

// 使用例
var c = MinimumCollection(values: [1, 2, 3, 4, 5, 6, 7])

print("First value is \(c.first!)")
print("Number of collection is \(c.count)")

for v in c {
    print("value: \(v)")
}

c.filter { $0 % 2 == 0 }
    .map { print("\($0) is even number.") }

isKnownUniquelyReferenced

書籍ではCopy On Writeを実装するために利用されていました。

この関数では、ある変数が参照しているオブジェクトが複数の参照を持つかを確認できます。関数がtrueを返す場合、その変数のみが参照していることを示します。その為、そのオブジェクトを直接変更しても他への影響がないことを確認できます。 もし他の変数からも参照されている場合（falseが返る場合）、オブジェクトを直接変更してしまうと、他の変数からも参照しているオブジェクトが変更されてしまうことになります。そのため、変更を行う際には予めそのオブジェクトをコピーしてから変更することで、Copy On Writeを満たすことになります。