Swift 4.2 で追加される removeAll(:where) メモ（SE-0197）

どうも、運動したあとはお酒が飲みたくなってしまう tobi462 です。

ちょっと時間が空きましたが、今回はremoveAll(:where)という新たに追加されたコレクション系のAPIの Proposal を見ていきたいと思います。

今までの Swift 4.2 の記事は以下です。

なんだか増えてきましたね。

Tl;Dr

let isOdd: (Int) -> Bool = { $0 % 2 == 1 }

var xs = [1, 2, 3, 4, 5, 6]
xs.removeAll(where: isOdd) // mutating only
xs // => [2, 4, 6]

removeAll(where:) / SE-0197

RangeReplaceableCollection プロトコルに removeAll(where:) という mutating なメソッドが追加されました。

通常、特定の要素を除外する一般的な方法としては filter が利用できます。

xs.filter { !isOdd($0) }

しかし、これには2つの欠点があると Proposal では述べられています。

isOdd で無いもの 、という指定方法であり可読性が悪い（否定の条件は読みづらい）
新しいコレクションを生成するのでメモリ効率が悪い

可読性

可読性については例えば Ruby であれば select（Swiftでいうところの filter ）に対して、 reject というメソッドが用意されています。

xs = [1, 2, 3, 4, 5, 6]
xs.reject {|x| x % 2 == 1}

これは除外したいものをクロージャで指定しており分かりやすいと思います。同様の考えで Swift にも removeAll(where:) を追加するのは良い考えであると思います。（ただし、 filter と違って mutating なメソッドしか無いようですが・・・）

メモリ効率

filter の計算量は要素数を n とした場合 O(n) で固定です。

ただし、常に新しいコレクションを返すためメモリ効率という点から見ると優れているわけではありません。また要素が大きい場合はコピーコストがかかるという課題もあります。

今回の removeAll(where:) は（Proposalによると） shuffle-down というアルゴリズムを使用しており、新たなメモリを確保する必要なく要素の削除が行われるようになっています。

実際に merge された実装は以下のようです。
Add remove(where:) to RangeReplaceableCollection by airspeedswift · Pull Request #11576 · apple/swift · GitHub

なにやら込み入っていますが、要素を swap しつつ、最後に一気に除去する作りに見えます。

これにより filter と違って新たなメモリを確保することなく要素の削除が行えるという思想のようです。

速いか？

100万個の Int が格納された配列から奇数のみを抽出した場合、 filter と removeAll(where:) でどちらが速いか検証してみました。

import Foundation

let isOdd: (Int) -> Bool = { $0 % 2 == 1 }

let mesure: (String, () -> Void) -> Void = {
    let start = Date()
    $1()
    let interval = Date().timeIntervalSince(start)
    print("\($0):\n  \(interval)")
}

let xs = Array(1...1_000_000)
var ys = xs

mesure("filter") {
    xs.filter { !isOdd($0) }
}
mesure("removeAll(where:)") {
    ys.removeAll(where: isOdd)
}

-O で実行したところ、手元のMacBookでは以下の結果となりました。

$ ./swift -O removeAll.swift
filter:
  0.018193960189819336
removeAll(where:):
  0.01980602741241455

10回実行した結果の平均みたいな丁寧な計測方法はしていないのですが、そこまで実行速度には変化が無いようです。

removeAll(where:) はメモリ効率に優れてはいるものの、 filter に比べて処理が高速といったことはおそらくなさそうです。

filter バージョンが欲しい？

mutating なAPIではなく、filter のように新しいコレクションを返すAPIが欲しい人もいるかもしれません。

そうした場合は以下のように自前で実装するのが手っ取り早そうです。

extension Sequence {
    func reject(_ isReject: (Element) -> Bool) -> [Element] {
        return filter { !isReject($0) }
    }
}

let xs = [1, 2, 3, 4, 5, 6]
let ys = xs.reject(isOdd) // => [2, 4, 6]

標準APIでないので初見で戸惑う可能性もありますが、filter の条件を否定で書くよりは素直で可読性がよく見えます。まぁ、トレードオフですね。

まとめ

なんかいろいろ書きましたが、指定した条件の要素を削除できるAPIが追加されたよ、って理解で良いような気がします。

莫大な要素数を処理するとか、あるいはメモリがとても制限された環境だとかであれば、このあたりのメモリ効率などを考えることもあるかもしれませんが。

というわけで無駄に長くなってしまいましたが、今回はこれにて。

ペンギン村 Tech Blog

技術をこよなく愛するエンジニア集団が在住するペンギン村から、世界へ役立つ（かもしれない）技術情報を発信する技術系ブログです。某アラレちゃんが済む村とは一切関係ありません。んちゃ!