lodash の intersection の計算量は O(n^2)?

同僚のコードレビューをしているときに、filter の中で includes している以下のようなコードを見つけました。

const array1 = [1,2,3];
const array2 = [3,4,5];
array1.filter( n => array2.includes(n));
// filter が O(n), includes が O(n) かかるので O(n^2) かかるはず

「計算量が O(n^2) になってよくない、lodash の intersection を使うといい」という指摘をしました。なんとなくO(n)ぐらいのオーダーだと思っていましたが、どれくらいの計算量か把握しておらず自信が持てなかったのでちゃんと調べておきたいと思いました。

lodash.intersection(array1, array2);
// 計算量は？

ちなみに intersection 関数は２つ以上の配列を引数にとり、すべての配列の要素の積集合を取る関数です。
https://lodash.com/docs/4.17.15#intersection

TL;DR

intersection は配列の長さによって計算量が違う
積集合を取る配列Aと配列Bの長さをそれぞれ、n, m とすると、

• 配列 A, B どちらかの長さが 120 以下なら O(n*m)
• 配列 A, B どちらの長さも 120 以上なら O(n+m)

（一応確認）filter のなかで includes すると O(n^2) になるか

一応 ECMAScript の Spec を見てみます
ECMAScript® 2022 Language Specification | Array.prototype.filter
filterはループを回していて O(n) っぽいですね

ECMAScript® 2022 Language Specification | Array.prototype.includes
includesも同様に O(n) のようです。

であればやはり filter * includes は O(n^2) になりそうです。じゃあ lodash の intersection ならどうでしょうか？

lodash intersection は O(n^2) ?

lodash のリファレンスには特にオーダーは書いてなかったです。
https://lodash.com/docs/4.17.15#intersection

仕方ないので intersection のコードを読みました。
intersection のメインの処理は baseIntersection 関数にあります。

以下は超省略した baseIntersection の関数です。

function baseIntersection(arrays, iteratee, comparator) {
    //(省略)
    // 配列Aの要素でループを回す
    outer:
    while (++index < length && result.length < maxLength) {
        var value = array[index]

        // othLength: arrays.length
        othIndex = othLength;
        while (--othIndex) {
            // ここで 配列Aと配列Bの要素と比較している
            if (!includes(arrays[othIndex], value)){
                continue outer;
            }
            // 積集合に当てはまる要素
            result.push(value);
        }
    }
    return result;
}

includes 関数は O(n) かかる関数です。配列Aの要素のループと合わせて O(n^2) ですね。
……あれ？ O(n^2) になりそうですね？ほんとに？
実際、includes の中に console.log を仕込むと、 O(n^2) になりました。

そんなことないはず

いや、そんなことないはず。
先程のbaseIntersectionはかなり省略したものでした。省略したところのコードをよく見ると以下のような記述がありました。
以下の処理は、配列の集合であるarrays から、一つづつ配列を取得して、キャッシュを作成するものです。

function baseIntersection(arrays, iteratee, comparator) {
    //(省略)
    while (othIndex--) {
        var array = arrays[othIndex];
        // length は１つ目の配列の要素数、 array.length は２つ目以降の配列の要素数
        caches[othIndex] = (length >= 120 && array.length >= 120)
            ? new SetCache(othIndex && array)
            : undefined;
    }
    //(省略)
}

つまり、「１つ目の配列が 120 要素以上 かつ、２つ目以降の配列が 120 要素以上」の場合に配列で SetCache を初期化しています。SetCacheの中では、Hash に値を代入していました。

なぜこんなことをしているのか、lodash のリポジトリを見ても理由はわかりませんでした。

ここからは自分の予想ですが、120 以下の場合は SetCache するときのオーバーヘッドのほうが大きいのかもしれないですね。本当のことを知っている人は教えてほしいです。

まとめ

lodash の intersection は配列の要素数によってオーダーが変わりました。
積集合を取る配列Aと配列Bの長さをそれぞれ、n, m とすると、

• 配列 A, B どちらかの長さが 120 以下なら O(n*m)
• 配列 A, B どちらの長さも 120 以上なら O(n+m)

になりました。不思議に思ったことはなんでも調べてみるものですね。