Javascript 配列で集合の差を効率的に計算するにはどうすればよいですか?

JavaScript 配列を使用した効率的な集合差の計算

2 つの配列間の集合の差の計算は、データ操作と集合論において重要な操作となる場合があります。配列が主要なデータ構造として機能する Javascript では、このタスクを実行する効率的かつ洗練された方法を見つけることが不可欠です。

簡単なアプローチの 1 つは、以下に示すように、ネイティブの array.filter() 関数を活用することです。

<code class="js">var A = [1, 2, 3, 4];
var B = [1, 3, 4, 7];

var diff = A.filter(function(x) {
  return B.indexOf(x) < 0;
});</code>

このアプローチでは、indexOf() 関数を利用して、A の要素が B に存在するかどうかを判断します。存在しない場合、要素は結果の差分配列に追加されます。簡単ではありますが、A の各要素に対して B 配列内で線形検索を実行するという欠点があり、時間計算量が O(n^2) になる可能性があります。

より大きな配列の場合は、次のアルゴリズム:

1. B のすべての要素を含むセット S を作成します。
2. A を反復処理し、S に見つからない要素を差分配列 diff に追加します。

<code class="js">var s = new Set(B);
var diff = A.filter(function(x) {
  return !s.has(x);
});</code>

S にセットを使用すると、メンバーシップ テストが一定時間で実行されることが保証され、全体の時間計算量は O(n) になります。

以上がJavascript 配列で集合の差を効率的に計算するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。