Solution pratique pour gérer l'intersection et l'union de tableaux PHP à grande échelle-tutoriel php-php.cn

Solution pratique pour gérer l'intersection et l'union de tableaux PHP à grande échelle

WBOY

Libérer： 2024-05-01 11:27:02

original

710 Les gens l'ont consulté

Solution pratique pour gérer lintersection et lunion de tableaux PHP à grande échelle

Une solution pratique pour traiter l'intersection et l'union de tableaux PHP à grande échelle

Introduction

Lors du traitement de données volumineuses, il est souvent nécessaire d'effectuer des opérations d'intersection et d'union de tableaux. Mais pour les grands tableaux contenant des millions ou des milliards d’éléments, les fonctions PHP par défaut peuvent être inefficaces ou souffrir de problèmes de mémoire. Cet article présentera plusieurs solutions pratiques pour améliorer considérablement les performances lorsque vous travaillez avec de grandes baies.

Méthode 1 : Utiliser une table de hachage

Convertissez un tableau en table de hachage, en utilisant des éléments comme clés.
Parcourez un autre tableau et vérifiez si la clé existe dans la table de hachage. S'il est présent, l'élément est dans l'intersection.
Complexité temporelle : O(n)

Exemple de code :

$arr1 = range(1, 1000000);
$arr2 = range(500001, 1500000);

$hash = array_flip($arr1);

$intersection = array_keys(array_intersect_key($hash, $arr2));

Copier après la connexion

Méthode 2 : Utilisation de la bibliothèque Hashes.php

Utilisez une bibliothèque comme Hashes.php, qui fournit une table de hachage efficace. réalisé.
Pour les opérations d'intersection, utilisez la méthode Intersect() 方法。对于并集运算，使用 Union().
Complexité temporelle : O(n)

Exemple de code :

use Hashes\Hash;

$map = new Hash();
foreach ($arr1 as $val) {
    $map->add($val);
}

$intersection = $map->intersect($arr2);
$union = $map->union($arr2);

Copier après la connexion

Méthode 3 : Utilisez des opérations au niveau du bit

pour convertir chaque nombre du tableau en un bitmap au niveau du bit.
L'intersection peut être obtenue en exécutant ET deux bitmaps.
L'union peut être obtenue en effectuant un OU entre deux bitmaps.
Complexité temporelle : O(n), où n est le nombre de chiffres du plus grand nombre du tableau.

Exemple de code :

function bitInterset($arr1, $arr2) {
    $max = max(max($arr1), max($arr2));
    $bitSize = 32;  // 如果 max > (2^32 - 1)，可以调整 bitSize

    $bitmap1 = array_fill(0, $bitSize, 0);
    $bitmap2 = array_fill(0, $bitSize, 0);

    foreach ($arr1 as $num) {
        $bitmap1[$num >> 5] |= (1 << ($num & 31));
    }
    foreach ($arr2 as $num) {
        $bitmap2[$num >> 5] |= (1 << ($num & 31));
    }

    $intersection = [];
    for ($i = 0; $i < $bitSize; $i++) {
        $mask = $bitmap1[$i] & $bitmap2[$i];
        for ($j = 0; $j < 32; $j++) {
            if (($mask >> $j) & 1) {
                $intersection[] = ($i << 5) | $j;
            }
        }
    }

    return $intersection;
}

Copier après la connexion

Exemple pratique

Considérons un tableau contenant un million d'éléments et nous voulons trouver son intersection et son union avec un autre tableau contenant cinq millions d'éléments.

Utilisation de la méthode 1 (table de hachage) :