Swiftの即時リストと遅延リスト - プログラマ英語学習日記

Swift(Kotlinもですが)はモダンな言語らしく、リスト（配列など全般）を map や filter で高階関数を使い処理というのをみなさんされてると思います。

では次のコードは何回 map が走るでしょう？

let data = [1, 2, 3, 4, 5]
data.map {
  //ここを何回とおるか？
  $0 * $0
}.filter {
  $0 % 2 == 0
}.first

first が重要ポイント。 data をよく見れば分かると思いますが２番めの要素「２」がfilterの条件にマッチするので、「３」以降の値は見ても見なくても一緒です。結局欲しいのは最初の値だけですから。

ではデバッグ出力しこんでみましょう

let data = [1, 2, 3, 4, 5]
data.map {(v) -> Int in //なぜかinを書かないとコンパイラがエラーだした
  print("MAP:\(v)") 
  return v * v
}.filter {
  print("FILTER:\($0)")
  return $0 % 2 == 0
}.first

さて、これを実行すると...?

MAP:1
MAP:2
MAP:3
MAP:4
MAP:5
FILTER:1
FILTER:4
FILTER:9
FILTER:16
FILTER:25

となります。はい、そうです。 本来不要な部分まで演算処理が走ってしまっています。

forに書き換えると次のようなコードでしょうか？

var result: Int? = nil
for v in data {
  let d = v * v
  if d % 2 == 0 && result == nil {
    result = d
  }
}

もちろん、というべきか次のように break すれば負荷は大幅に下がります

var result: Int? = nil
for v in data {
  let d = v * v
  if d % 2 == 0  {
    result = d
    break  //※
  }
}

これだとmap/filterの処理回数は最低限で済むので効率的です。

同じようなことを map で行う方法が用意されています。それが lazy です。

let data = [1, 2, 3, 4, 5]
data
  .lazy   //追加
  .map {
    print("MAP:\($0)")
    return $0 * $0
  }.filter {
    print("FILTER:\($0)")
    return $0 % 2 == 0
  }.first

こうすると実行結果は...?

MAP:1
MAP:2
FILTER:1
FILTER:4

breakいりforと同程度の計算回数ですみました！

いわゆる遅延評価というやつです。逆にlazyなしは即時評価。即座に配列全体に計算を適用するのに対し、遅延は必要になるまで計算させません。

即時評価を正格評価という場合もあります。関数型の成分が強いと後者が多い印象です。Haskellなど。

なら全部遅延でいいんじゃない？　と言いたいところですが、それでは効率が悪い箇所も多いのです。

それが 全件走査が必須な処理。たとえば最大値を取得する/ソートする、また配列に戻すなどです。この場合、結局配列全体の値を調べる必要があるので遅延評価させる意味がありません。

なので lazy に意味があるのは first 等の限られたシチュエーションです。「for文に置き換えた場合、breakできる処理か」が一つの目安になると思います。

Kotlin

同様のものがKotlinにもあり、 iterable と sequence です。前者が即時、後者が遅延です。

普通に配列/リスト他は即時評価になります。asSequence で遅延に変換できます

val arr = arrayOf(1, 2, 3, 4, 5)
arr
  .asSequence() //これ
  .map { 
      it * it 
  }.filter {
      it % 2 == 0
  }.firstOrNull()

逆にsequenceも asIterable() で即時に変換できます。とはいえ普通にKotlinやってるとほとんどが即時評価のListなので、asIterable()を使う機会はそうそうないんじゃないかな？と思います。

まとめ

以上、ともすれば計算量が大幅に変わってしまうリスト操作のお話でした。役に立つ機会は少ないかもしれませんが、頭の片隅においておくと処理負荷を軽減できるかもしれません。（特に競プロ）

ちょっと意識してみると面白いと面白いと思います。