La structure de données basée sur une table de hachage optimise les calculs d'intersection et d'union des tableaux PHP

Utilisez une table de hachage pour optimiser les calculs d'intersection et d'union de tableaux PHP, en réduisant la complexité temporelle de O(n * m) à O(n + m). Les étapes spécifiques sont les suivantes : Utilisez une table de hachage pour ajouter les éléments du. premier tableau Mapper la valeur booléenne pour savoir rapidement si l'élément existe dans le deuxième tableau et améliorer l'efficacité du calcul d'intersection. Utilisez une table de hachage pour marquer les éléments du premier tableau comme existants, puis ajoutez les éléments du deuxième tableau un par un, en ignorant les éléments existants pour améliorer l'efficacité des calculs d'union.

Optimisation de l'intersection et du calcul d'union de tableaux PHP basés sur la table de hachage

Avant-propos

Le traitement de l'intersection et de l'union de tableaux en PHP est une opération courante, en particulier lorsque de grandes quantités de données sont impliquées. Pour optimiser ces calculs, nous pouvons utiliser des tables de hachage pour améliorer considérablement l'efficacité.

Table de hachage

Une table de hachage est une structure de données qui mappe les clés aux valeurs. Une propriété clé d’une table de hachage est qu’elle peut rechercher et insérer des éléments de manière très efficace.

Optimiser le calcul d'intersection de tableaux à l'aide d'une table de hachage

Considérez le code suivant, qui calcule l'intersection de deux tableaux :

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

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

  return $result;
}

La complexité temporelle de ce code est O(n * m), où n et m sont respectivement arr1 et la longueur de arr2. Nous pouvons utiliser une table de hachage pour mapper les éléments de arr1 à une valeur booléenne indiquant si l'élément est présent dans arr1. Nous pouvons ensuite parcourir arr2 et trouver rapidement si un élément est présent dans arr1 en utilisant la valeur de la clé correspondante dans la table de hachage.

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;
}

La complexité temporelle de ce code est O(n + m) car il ne parcourt chaque tableau qu'une seule fois.

Utilisez la table de hachage pour optimiser le calcul des unions de tableaux

Pour le calcul des unions de tableaux, nous pouvons également utiliser la table de hachage. Tout d’abord, nous mappons les éléments du premier tableau dans une table de hachage. Nous ajoutons ensuite chaque élément du deuxième tableau à la table de hachage, en l'ignorant s'il existe déjà.

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;
}

La complexité temporelle de ce code est O(n + m) car il ne parcourt chaque tableau qu'une seule fois.

Cas pratique

Supposons que nous ayons deux tableaux d'une longueur de 100 000 et 50 000. Le temps moyen requis pour calculer l'intersection et l'union en utilisant respectivement l'implémentation d'origine et l'implémentation optimisée de la table de hachage est le suivant : Secondes

0,05 secondesUnion1,80 secondes0,10 secondes

Comme nous pouvons le constater, la mise en œuvre de l'optimisation des tables de hachage améliore considérablement l'efficacité des calculs d'intersection et d'union.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!