uniqueByから始める低計算量アルゴリズムのすゝめ

こんにちは、アプリ開発担当のエモトです。先日、弊社アプリが大型アップデートされました。我々アプリチーム含め社内メンバーと取り組んで、ダークモードなど新しい機能を追加してリリースすることができました。是非、新しくなったアプリをご利用くださいませ。

さて話は変わり、ある配列に対して、その配列の要素が重複しない配列に気軽に変換にしたい。

const array1 = [1, 1, 2, 2, 3, 3]
const array2 = uniqueBy(array1) // [1, 2, 3]

この問題、何も考えずに実装すると計算量 O(N²) となり、非常に大きい計算負荷になってしまいます。安易に実装するぐらいなら、サードライブラリを利用するのが良いと思います。

弊アプリは React Native を採用しているので、Swift などのネイティブ実装と比べると計算量はより気になる要因の1つです。アプリでは lodash の uniqBy を使用していました。ふと気になって、そのソースコードを確認すると while ループが2つ重なるパターンがあり、良い計算量の設計ではないと気づきました。また lodash の代替候補とも言われる just の just-unique は計算量は考慮されているが、重複確認は単純比較のみなので、必ずしも代わりになるわけではないとわかりました。これは何かしないといけない。

Set を利用した手法

重複なしを実現したいなら Set を利用するのが簡単ですが、要素の順番が保証されないケースがほとんどです。しかし、TypeScript (JaveScript) では Set は順序が保証されているとのことで、Set を利用するしかありません。

export const unique = <T>(args: T[]): T[] => [...new Set(args)]

上記だと、要素が Object 型の場合、比較が困難になります。そのため、特定要素を比較する場合も作成しました。

const uniqueBy = <T>(args: T[], key: keyof T): T[] => {
  const valueSet = new Set()
  return args.filter((arg) => {
    const value = arg[key]
    if (valueSet.has(value)) {
      return false
    }
    valueSet.add(value)
    return true
  })
}

検証として 0 から 4 までの数字で構成された 100 万個の要素を持つ配列を用意して、計測しました。

	unique	uniqueBy
対象配列	[0, 1, 2, ...]	[{x: 0}, {x: 1}, {x: 2}, ... ]
計算時間 (msec)	333	21

純粋な Set を利用した unique の方が早いと想像しましたが、予想外にもその unique の方が 10 倍以上の計算時間でした。ソースコードは短いが Set に変換した後に Array に変換するという処理だから？かもしれませんが、詳しくは分かりませんでした。

自作した uniqueBy

検証結果から以下のようなコードを作成しました。

/**
 * 配列から、ユニークな（重複しない）配列を生成する
 *
 * @description
 * keyが未指定の場合、[...new Set(args)] の方が早そうだが、実際は遅かった。
 * なお、jsのSetは順番が保証されている
 */
const _uniqueBy = <T>(args: T[], key?: keyof T): T[] => {
  const valueSet = new Set()
  return args.filter((arg) => {
    const value = key ? arg[key] : arg
    if (valueSet.has(value)) {
      return false
    }
    valueSet.add(value)
    return true
  })
}

/**
 * 単純な配列から、ユニークな（重複しない）配列を生成する
 * - 単純比較できる string[] や number[] など
 */
export const unique = <T>(args: T[]): T[] => _uniqueBy(args)

/**
 * 配列から、その配列内要素の特定keyを基準に、ユニークな（重複しない）配列を生成する
 *
 * @example
 * const uniqueArray = uniqueBy([{x:1}, {x:1}, {x:2}], 'x')
 */
export const uniqueBy = <T>(args: T[], key: keyof T): T[] =>
  _uniqueBy(args, key)

既存ライブラリとの比較

lodash の uniqBy と比較しました。対象データは先ほどと同様な100万個要素の配列を用意しました。

	自作/uniqueBy	lodash/uniqBy
平均 (msec)	68.9	111.7
標準偏差 (msec)	38.2	13.4
最小 (msec)	24	87
最大 (msec)	141	132

10回ほど検証したところ、多くの場合で、自作の方が早かったです（うれしい）。

まとめ

uniqueBy（重複なし配列への変換）を含め、安易なアルゴリズムでコーディングすると計算量が高くなる処理があります。これらは自作せずに、サードパーティを利用した方が良いと思っています。しかし、それぞれの設計思想や目的があり、自分が使いたいシーンで必ず良い結果や計算量が与えられるとは限らない問題もあります。

今回は対象データや、Set でうまく処理できたことが重なって、自作の採用にメリットがあり挑戦できました。最適なアルゴリズムを考える時間は、とても楽しい開発でした。

最後に、オトバンクではエンジニアを募集中です。日々高速で低計算量なアルゴリズムを考えるのが好きな方、オーディオブック・React Native 開発（Swift や Kotlinのネイティブコードも書いてます）にご興味があれば、是非どうぞ。