ハッシュ テーブル ベースのデータ構造により、PHP 配列の論理積と和集合の計算が最適化されます。

ハッシュ テーブルを使用すると、PHP 配列の論理積と和集合の計算を最適化し、時間の計算量を O(n * m) から O(n m) に減らすことができます。 具体的な手順は次のとおりです。 ハッシュ テーブルを使用して、要素を追加します。最初の配列 ブール値にマップして、要素が 2 番目の配列に存在するかどうかをすばやく調べ、交差計算の効率を向上させます。ハッシュ テーブルを使用して最初の配列の要素を既存としてマークし、次に 2 番目の配列の要素を 1 つずつ追加し、既存の要素を無視して共用体計算の効率を向上させます。

#ハッシュ テーブルに基づく PHP 配列の交差と共用体の計算の最適化

##まえがき

配列の交差と結合の処理は、特に大量のデータが関係する場合に、PHP で一般的な操作です。これらの計算を最適化するために、ハッシュ テーブルを利用して効率を大幅に向上させることができます。

ハッシュ テーブル

ハッシュ テーブルは、キーを値にマップするデータ構造です。ハッシュ テーブルの重要な特性は、要素を非常に効率的に検索して挿入できることです。

ハッシュ テーブルを使用した配列の交差計算の最適化

2 つの配列の交差を計算する次のコードを考えてみましょう。

function intersect($arr1, $arr2) {
  $result = [];

  foreach ($arr1 as $value) {
    if (in_array($value, $arr2)) {
      $result[] = $value;
    }
  }

  return $result;
}

このコードの時間計算量次数は O(n * m) です。ここで、n と m はそれぞれ arr1 と arr2 の長さです。ハッシュ テーブルを使用して、arr1 の要素を、その要素が arr1 に存在するかどうかを示すブール値にマップできます。次に、arr2 を反復処理し、ハッシュ テーブル内の対応するキーの値を使用して、arr1 に要素が存在するかどうかをすばやく確認できます。

function intersect_hash($arr1, $arr2) {
  $lookup = [];

  foreach ($arr1 as $value) {
    $lookup[$value] = true;
  }

  $result = [];

  foreach ($arr2 as $value) {
    if (isset($lookup[$value])) {
      $result[] = $value;
    }
  }

  return $result;
}

このコードの時間計算量は、各配列を 1 回だけ反復するため、O(n m) です。

ハッシュ テーブルを使用して配列和集合の計算を最適化する

配列和集合の計算には、ハッシュ テーブルを使用することもできます。まず、最初の配列の要素をハッシュ テーブルにマッピングします。次に、2 番目の配列の各要素をハッシュ テーブルに追加します。要素がすでに存在する場合は無視します。

function union($arr1, $arr2) {
  $lookup = [];

  foreach ($arr1 as $value) {
    $lookup[$value] = true;
  }

  foreach ($arr2 as $value) {
    $lookup[$value] = true;
  }

  $result = array_keys($lookup);

  return $result;
}

このコードの時間計算量は、各配列を 1 回だけ反復するため、O(n m) です。

実際的なケース

長さが 100,000 と 50,000 の 2 つの配列があるとします。元の実装とハッシュ テーブル最適化実装をそれぞれ使用して交差と和集合を計算するのに必要な平均時間は次のとおりです。

操作##Intersection2.00 秒0.05 秒1.80 秒ご覧のとおり、ハッシュ テーブルの最適化の実装は明らかにこれにより、交差および和集合の計算の効率が向上します。

元の実装	ハッシュ テーブルの最適化
		##Union
0.10 秒

以上がハッシュ テーブル ベースのデータ構造により、PHP 配列の論理積と和集合の計算が最適化されます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。