Typescriptで重複削除の計算速度を比較してみた

プログラミングをしていると、重複データを削除する必要性に直面することがあります。

APIの応答として大量のデータを扱う場合など、計算速度は非常に重要です。

そこで、TypeScriptでの配列から重複を削除するいくつかの手法のパフォーマンスを比較してみました。

typescriptでの主な重複削除

① Set

SetはJavaScriptにおいて、重複する要素を持たないコレクションを作成するための組み込みオブジェクトです。この特性を利用して配列から重複を削除できます。

ただし、参照のユニーク性に基づいて動作するため、異なる参照を持つが内容が同じオブジェクトや配列を重複として認識しません。

そのため、オブジェクトや配列の重複を除外したい場合は、Setではなく他の方法を検討する必要があります。

const numbers: number[] = [1, 2, 2, 3, 4, 4, 5];
const uniqueNumbers: number[] = Array.from(new Set(numbers));
console.log(uniqueNumbers); // [1, 2, 3, 4, 5]

② Map

Mapはキーと値のペアを持つコレクションで、オブジェクトの配列など、より複雑なデータ構造に対して重複削除を行う際に有用です。

// 単純な配列の場合 
const items = [1, 2, 3, 4, 5, 5];
const uniqueItemsMap = new Map(items.map(item => [item, item])); 
const uniqueItems = Array.from(uniqueItemsMap.values());
console.log(uniqueItems) // [1, 2, 3, 4, 5] 

// オブジェクト配列の場合
const itemObjects = [{ id: 1 }, { id: 2 }, { id: 2 }, { id: 3 }]; 
const uniqueItemObjectsMap = Array.from(new Map(itemObjects.map(itemObject => [itemObject.id, itemObject])).values()); 
console.log(uniqueItemObjectsMap); // [{ id: 1 }, { id: 2 }, { id: 3 }]

③ Filter

filterメソッドを使用して、配列内で最初に見つかった要素のインデックスが現在の要素のインデックスと一致する場合にのみ要素を保持することで、重複を削除します。

// 単純な配列の場合 
const numbers: number[] = [1, 2, 2, 3, 4, 4, 5];
const uniqueNumbers = numbers.filter((number, index, self) => self.indexOf(number) === index); 
console.log(uniqueNumbers); // [1, 2, 3, 4, 5] 

// オブジェクト配列の場合 
const itemObjects = [{ id: 1 }, { id: 2 }, { id: 2 }, { id: 3 }]; 
const uniqueItemObjects = itemObjects.filter((itemObject, index, self) => index === self.findIndex(item => item.id === itemObject.id) ); 
console.log(uniqueItemObjects); 　// [{ id: 1 }, { id: 2 }, { id: 3 }]

④ Reduce

reduceメソッドを利用して、累積された配列に現在の要素が含まれていない場合にのみ追加することで、配列から重複を削除します。

// 単純な配列の場合
const numbers: number[] = [1, 2, 2, 3, 4, 4, 5];
const uniqueNumbers = numbers.reduce((acc: number[], current) => {
　　if (!acc.includes(current)) {
　　　　acc.push(current);
　　}
　　return acc;
}, []);
console.log(uniqueNumbers); // [1, 2, 3, 4, 5]

// オブジェクトの配列の場合
const itemObjects = [{ id: 1 }, { id: 2 }, { id: 2 }, { id: 3 }];
const uniqueItemObjects = itemObjects.reduce((acc, current) => { 
　　if (!acc.find(item => item.id === current.id)) {
　　　　acc.push(current); 
　　} 
　　return acc;
}, []);
console.log(uniqueItemObjects); // [{ id: 1 }, { id: 2 }, { id: 3 }]

検証方法

単純な数値配列と、キーと値のペアのみを持つオブジェクトの配列の2種類の配列を用意し、

重複を削除する処理の速度を、配列のサイズ（要素数）を変化させながら、各手法ごとに実行時間を計測しました。

また、重複する要素の比率が計算速度に影響を与えるため、配列には重複した値を全体の20％にあたる分含ませるようにしました。

例えば、100要素ある配列では20要素が重複しており、重複削除後の配列は80要素となります。

実行環境

1. スペック
   • Microsoft Windows 10 Pro
   • CPU（プロセッサ）: 12th Gen Intel(R) Core(TM) i7-1255U、1.7 GHz、10 コア、12 ロジカルプロセッサ
   • メモリ（RAM）: 16.0 GB

• 実行方法
  • 本検証では、TypeScriptのファイル（.ts）をTypeScriptコンパイラ（tsc）でコンパイルした後、CLI（コマンドラインインターフェース）上でNode.jsを用いて実行しました。
    • tsc バージョン: 5.4.3
    • Node.js バージョン: v18.18.0

結果

以下の表とグラフは、各手法による計算速度の比較結果を示しています。

表は配列の長さごとに、それぞれの手法での処理時間をミリ秒（ms）単位で表示しています。

numberの配列の場合：

オブジェクトの配列の場合：

*setはオブジェクトや配列の重複削除には不向きなため除外（後述）

分析

• Filterの処理速度が遅い主な理由は、配列全体を走査する必要があることです。filterメソッド内で使用されるindexOfは、配列の各要素に対してその要素が配列内のどこにあるかを確認するために、配列の先頭から走査を行います。その結果、配列のサイズが大きくなるほど、処理に要する時間が増加します。
• Reduceも処理速度が遅くなる要因はいくつかありますが、その一つにincludesメソッドを用いた重複の検索があります。このメソッドは配列内で値が既に存在するかどうかを確認するために使用され、配列が大きくなると計算量も増加します。また、reduce処理の中で新しい配列に値をpushする操作も、処理の遅延に寄与しています。
• Mapの場合、filterやreduceとは異なり、配列全体を検索する必要がありません。Mapはキーに基づく直接アクセスを可能にするため、重複のチェックにおいては、特定のキーに対応する値が存在するかどうかだけを確認すればよいです。この操作は時間複雑度がO(1)であるため、データの量に関係なく一定の高速な処理が可能です。
• Setは特に単純なデータ型（数値や文字列など）の配列での重複削除において、非常に高速です。Setは重複する要素を自動的に排除するため、重複の明示的なチェックを行う必要がなく、これがSetの大きな利点となります。ただし、オブジェクトなどの参照型のデータに対しては、同じ内容でも異なる参照を持つと別の要素として扱われるため、この場合の重複削除には向いていません。

まとめ

• 計算速度が気になる場合はMapを使っておくと良い
• setも早いが、オブジェクトや配列では意図しない挙動をすることがある
• reduceやfilterは直観的であるが、配列が大きい際は注意が必要

追記:

より計算量やアルゴリズムについて詳しく書かれた良記事を教えていただいたので貼っておきます:

https://qiita.com/netebakari/items/7c1db0b0cea14a3d4419#:~:text=%E9%85%8D%E5%88%97%E3%82%92%E4%BA%8B[…]%E4%BA%86%E3%81%97%E3%81%BE%E3%81%99%E3%80%82

About 永田孝輔 1 Article

2021年に新卒として入社。React + Typescriptでのフロント開発を行っています。