CollectionType,SequenceTypeのmap()

前回Optional型のmap()を読んだのに続いて、今回はCollectionTypeとSequenceTypeのmap()を見てみることにします。 プロトコルの定義は次のとおりです。

func map<T>(@noescape transform: (Self.Generator.Element) throws -> T) rethrows -> [T]

これらはstdlib/public/coreディレクトリ下にCollection.swiftとSequence.swiftとで実装されています。なおmap()の実装はSequenceWrapper.swiftにもあるのですが、これは中でCollectionType,SequenceTypeのmap()を呼んでいるだけなので、今回は無視します。

CollectionTypeのmap()

ではまず、CollectionTypeから見てみます。

// CollectionType
@warn_unused_result
public func map<T>(
  @noescape transform: (Generator.Element) throws -> T
) rethrows -> [T] {
  let count: Int = numericCast(self.count)
  if count == 0 {
    return []
  }

  var result = ContiguousArray<T>()
  result.reserveCapacity(count)

  var i = self.startIndex

  for _ in 0..<count {
    result.append(try transform(self[i]))
    i = i.successor()
  }

  _expectEnd(i, self)
  return Array(result)
}

最初に要素数を数え、0だった場合には空の配列を返します。

0でなければ、型TのContiguousArrayを用意して、reserveCapacity()で要素数と同じサイズで確保します。なるほど、最初に確保しておけば再確保のコストを下げられますね。その後、自身の先頭から順に要素を取り出し、引数のtransformに渡します。その結果を配列に格納していきます。そしてArrayとして呼び側に戻しています。

ところで、return直前にある「_expectEnd(i, self)」とはいったい何でしょう。最終要素のインデックス番号と、自分自身を渡しています。coreフォルダ内を探してみると、Arrays.swift.gybファイルで次のように定義されていました。どうやらデバッグ用の処理のようで、iと自身の最終要素のインデックス番号とが同じかどうかをチェックしていました。

/// A _debugPrecondition check that `i` has exactly reached the end of
/// `s`.  This test is never used to ensure memory safety; that is
/// always guaranteed by measuring `s` once and re-using that value.
internal func _expectEnd<C : CollectionType>(i: C.Index, _ s: C) {
  _debugPrecondition(
    i == s.endIndex,
      "invalid CollectionType: count differed in successive traversals"
    )
}

ちなみに「〜.swift.gyb」というファイルはCの#defineマクロのようなプリプロセッサでのテンプレートを実現するファイルで、Swiftの開発チームによって使われているファイルとのこと。utils/gyb.pyを使ってコンパイル前にソースコードへ適用されるようです。

GYB: Generate Your Boilerplate (improved names welcome; at least 3 # this one's short). See -h output for instructions

GYBって「Generate Your Boilerplate」のことなのですね。

SequenceTypeのmap()

次はSequenceTypeのmapです。こちらはSequence.swiftに実装があります。

// SequenceType
@warn_unused_result
public func map<T>(
  @noescape transform: (Generator.Element) throws -> T
) rethrows -> [T] {
  let initialCapacity = underestimateCount()
  var result = ContiguousArray<T>()
  result.reserveCapacity(initialCapacity)

  var generator = generate()

  // Add elements up to the initial capacity without checking for regrowth.
  for _ in 0..<initialCapacity {
    result.append(try transform(generator.next()!))
  }
  // Add remaining elements, if any.
  while let element = generator.next() {
    result.append(try transform(element))
  }
  return Array(result)
}

基本的な処理の流れは同じですが、CollectionTypeとは細かいところで少しずつ違っています。要素数をカウントする処理でunderestimateCount()を使っていて、CollectionTypeのcountプロパティとは異なります。SequenceTypeはcountプロパティを持たず順繰りに辿るしかないためですが、配列の再確保コストを考えると、O(N)でもunderestimateCount()を使っているのでしょう。

あれ、でもinitialCapacity==0だったとしてもそのまま処理を続けていますね。空なら空配列を返した方が良さそうですが、なぜなんでしょう??

その後、generate()メソッドイテレータを取り出し、順番に「Unwrapしながら」transform()に渡しています。その後、もしまだnext()で取り出せるようなら、配列が再確保されるのを覚悟で追加しています。

・・・ここも疑問の残るコードです。はじめからwhileとOptional Bindingを使えばいいように思うのですが、この方が処理が速いのでしょうか。この記事にあるBenchmarkクラスを使って確かめてみます。

for num in [10, 100, 1000, 10000, 100000, 1000000, 10000000] {
    var src_array = [Int?]()
    for i in 0..<num {
        src_array.append(i)
    }

    var dst_array = ContiguousArray<Int>()
    dst_array.reserveCapacity(num)

    // 1) forによる実行
    var generator = src_array.generate()
    Benchmark.measure("for with \(num)") {
        for i in 0..<num {
            dst_array.append(generator.next()!!)
        }
    }

    dst_array.removeAll(keepCapacity:true)

    // 2) whileによる実行
    generator = src_array.generate()
    Benchmark.measure("while with \(num)") {
        while let v = generator.next() {
            dst_array.append(v!)
        }
    }
}

結果は次のとおり。コンパイル時の最適化レベルはデフォルトのままです。

素数 (1)for (2)while
10 0.000(s) 0.000(s)
100 0.000(s) 0.000(s)
1000 0.000(s) 0.000(s)
10000 0.004(s) 0.004(s)
100000 0.027(s) 0.026(s)
1000000 0.252(s) 0.260(s)
10000000 2.550(s) 2.507(s)

…うーん、同じですね。最適化レベルを「-Ounchecked」にしても試してみたのですが、むしろforの方が遅い結果になっています。何なんでしょう、「昔のバージョンは違った」とかあるのかもしれません。

疑問の残る結果でしたが、ソースから実装を確認できました。

まとめ

今回の気づいた点をまとめます。

  • CollectionTypeとSequenceTypeでは実装が異なる
  • ArrayはContiguousArray+reserveCapacity()で先に領域確保
  • SequenceTypeの実装は疑問の残る内容
  • Swift開発には.swift.gybファイルによるプリプロセッサ(もどき?)を使っている

C/C++のマクロって、なんだかんだ言われてもやっぱり便利なんだなと思った次第です。

参考サイト