Elm で List comparable を検索する場合は Set comparable に変換するとちょっと速い (場合がある) #Elm

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 という型があります。

type alias Record =
    { id : Int
    , ...
    }

この Record 型で表現されたレコードを要素に持つリスト records があります。

records : List Records
records = [ { id = 1, ... }, { id = 2, ... }, { id = 3, ... }, { id = 4, ... }, ... ]

それとは別に任意のレコードの ID を要素に持つリスト ids があります。

ids : List Int
ids = [ 1, 2, 4, 8, ... ]

このとき ids に含まれる ID と同じ ID を持つレコードを records から抽出したい、という状況を考えます。
「この状況何？」という感情は死滅させておいてください。

パターン1：素直に実装する

records からレコードを 1つずつ取り出し、そのレコードの ID が ids に含まれていれば抽出対象です。
List comparable な ids を検索する必要がありそうです。

コードはこんな感じですね：

素直に実装

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 の実装 (大体 List.any)

また、ids の走査は records の要素数分だけ実行されるので、全体の計算量は $O(n^2)$ になります。

パターン2：ちょっと速くする

ids を List から Set へ変換します。

ちょっと速く

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

ドキュメントにも記述されているように、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)$ なのは要素を二分木 ¹ で管理しているためです。
Set のデータ構造については elm packages のドキュメントに記述が見当たらないので、こちらも実装を確認します。
なお Set の実体は value の型が () な Dict です ² 。

Set.member の実体である Dict.member の実装…の本処理をやっている Dict.get を見ましょう。

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 を実行しています。

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)$ となります。
検索回数等を考慮して、どのような実装とするか判断するのがよいでしょう。

おしまり

正確には赤黒木。いい感じに木のバランスを取る構造らしい。やるじゃない。 ↩
Java の HashSet や TreeSet も同様の実装方法。よくあること？ ↩

Elm で List comparable を検索する場合は Set comparable に変換するとちょっと速い (場合がある)