1. ossan_pg

    Posted

    ossan_pg
Changes in title
+Elm で List comparable を検索する場合は Set comparable に変換するとちょっと速い (場合がある)
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,164 @@
+## TL; DR
+
+`Set` の要素へのアクセスは $O(log\ n)$ だから `List` の $O(n)$ より速いよ。やったね。
+ただし `Set` から `List` への変換処理は $O(n \cdot log\ n)$ だからそこも考慮しようね。
+
+アルゴリズムとデータ構造を履修済みの人には多分無用の記事です。
+でも変なこと言ってたらコメントもらえると助かります。
+
+
+## 計算量の目安
+
+| $n$ | $log\ n$ | $n \cdot log\ n\ $ | $n^2$ |
+|--:|--:|--:|--:|
+| 10 | 4 | 34 | 100 |
+| 100 | 7 | 665 | 10,000 |
+| 1,000 | 10 | 9,966 | 1,000,000 |
+
+小数点以下は切り上げ。
+
+
+## 状況
+
+ID を持つレコードを表現した `Record` という型があります。
+
+```elm
+type alias Record =
+ { id : Int
+ , ...
+ }
+```
+
+この `Record` 型で表現されたレコードを要素に持つリスト `records` があります。
+
+```elm
+records : List Records
+records = [ { id = 1, ... }, { id = 2, ... }, { id = 3, ... }, { id = 4, ... }, ... ]
+```
+
+それとは別に任意のレコードの ID を要素に持つリスト `ids` があります。
+
+```elm
+ids : List Int
+ids = [ 1, 2, 4, 8, ... ]
+```
+
+このとき `ids` に含まれる ID と同じ ID を持つレコードを `records` から抽出したい、という状況を考えます。
+「この状況何?」という感情は死滅させておいてください。
+
+
+## パターン1:素直に実装する
+
+`records` からレコードを 1つずつ取り出し、そのレコードの ID が `ids` に含まれていれば抽出対象です。
+`List comparable` な `ids` を検索する必要がありそうです。
+
+コードはこんな感じですね:
+
+```elm:素直に実装
+filterRecords : List Int -> List Record -> List Record
+filterRecords ids records =
+ List.filter (\record -> List.member record.id ids) records
+```
+
+できました。めでたしめでたし。
+
+ただし `ids` は `List` なので、任意の要素を参照するため先頭の要素から順番にアクセスしていきます。
+その計算量は $O(n)$ です。要素が増えると線形に増加します。
+
+- 参考:[`List.member` の実装](https://github.com/elm/core/blob/1.0.2/src/List.elm#L264) (大体 `List.any`)
+
+また、`ids` の走査は `records` の要素数分だけ実行されるので、全体の計算量は $O(n^2)$ になります。
+
+
+## パターン2:ちょっと速くする
+
+`ids` を `List` から `Set` へ変換します。
+
+```elm:ちょっと速く
+import Set
+
+filterRecords : List Int -> List Record -> List Record
+filterRecords ids records =
+ let
+ -- Set へ変換
+ ids_ = Set.fromList ids
+ in
+ List.filter (\record -> Set.member record.id ids_) records
+```
+
+[ドキュメントにも記述されている](https://package.elm-lang.org/packages/elm/core/1.0.2/Set) ように、`Set` の要素を参照する計算量は $O(log\ n)$ です。
+
+> Insert, remove, and query operations all take _O(log n)_ time.
+
+これに `records` の要素数を加味すると、全体の計算量は $O(n \cdot log\ n)$ になります。
+
+なのでこういう状況では `List` をそのまま使うより、一旦 `Set` へ変換する方が高速になります。
+めでたしめでたし。
+
+
+## おまけ1:`Set` のデータ構造
+
+`Set` を操作する計算量が $O(log\ n)$ なのは要素を二分木 [^1] で管理しているためです。
+`Set` のデータ構造については elm packages のドキュメントに記述が見当たらないので、こちらも実装を確認します。
+なお [`Set` の実体は value の型が `()` な `Dict`](https://github.com/elm/core/blob/1.0.2/src/Set.elm#L42-L47) です [^2] 。
+
+[^1]: 正確には赤黒木。いい感じに木のバランスを取る構造らしい。やるじゃない。
+
+[^2]: Java の [`HashSet`](https://docs.oracle.com/javase/jp/12/docs/api/java.base/java/util/HashSet.html) や [`TreeSet`](https://docs.oracle.com/javase/jp/12/docs/api/java.base/java/util/TreeSet.html) も同様の実装方法。よくあること?
+
+`Set.member` の実体である `Dict.member` の実装…の [本処理をやっている `Dict.get` を見ましょう](https://github.com/elm/core/blob/1.0.2/src/Dict.elm#L83-L121) 。
+
+```elm:Dict.getとDict.member
+get : comparable -> Dict comparable v -> Maybe v
+get targetKey dict =
+ case dict of
+ RBEmpty_elm_builtin ->
+ Nothing
+
+ RBNode_elm_builtin _ key value left right ->
+ case compare targetKey key of
+ LT ->
+ get targetKey left
+
+ EQ ->
+ Just value
+
+ GT ->
+ get targetKey right
+
+
+member : comparable -> Dict comparable v -> Bool
+member key dict =
+ case get key dict of
+ Just _ ->
+ True
+
+ Nothing ->
+ False
+```
+`targetKey` と現在の要素の `key` が一致していれば `value` を返し、そうでない場合は `targetKey` と `key` の大小関係に応じて左か右の要素を再帰的に走査しています。木ですねー。
+というわけで `Set` (`Dict`) のデータ構造は二分木になっています。
+
+
+## おまけ2:`Set.fromList` の計算量
+
+[`Set.fromList` は指定されたリストの要素の数だけ `Set.insert` を実行しています](https://github.com/elm/core/blob/1.0.2/src/Set.elm#L127-L132) 。
+
+```elm:Set.fromList
+fromList : List comparable -> Set comparable
+fromList list =
+ List.foldl insert empty list
+```
+
+`Set.insert` の計算量はドキュメントにあるように $O(log\ n)$ で、これがリストの要素の数だけ実行されます。
+なので `Set.fromList` の計算量は $O(n \cdot log\ n)$ です。
+
+
+今回のような状況とは異なり、例えば「`Record` 型の値 1個について検索する場合」は計算量が変わってきます。
+`records` を走査する処理がなくなるので、`List` のままの実装では $O(n)$ 、`Set` へ変換する実装では `Set.fromList` の計算量が支配的なため $O(n \cdot log\ n)$ となり、計算量が逆転します。
+
+後者においても、判定のたびに `Set` を作成しなくてよい場合 (あらかじめ `Set.fromList` が実施してある場合) は検索 1回あたりの計算量は $O(log\ n)$ となります。
+検索回数等を考慮して、どのような実装とするか判断するのがよいでしょう。
+
+
+**おしまり**