대규모 PHP 배열의 교차 및 합집합을 처리하기 위한 실용적인 솔루션-PHP 튜토리얼-php.cn

대규모 PHP 배열의 교차 및 합집합을 처리하기 위한 실용적인 솔루션

WBOY

풀어 주다： 2024-05-01 11:27:02

원래의

713명이 탐색했습니다.

대규모 PHP 배열의 교차 및 합집합을 처리하기 위한 실용적인 솔루션

대규모 PHP 배열 교차 및 합집합 처리를 위한 실용적인 솔루션

소개

대규모 데이터를 처리할 때 배열 교차 및 합집합 연산을 수행해야 하는 경우가 많습니다. 그러나 수백만 또는 수십억 개의 요소가 포함된 대규모 배열의 경우 기본 PHP 함수는 비효율적이거나 메모리 문제로 어려움을 겪을 수 있습니다. 이 기사에서는 대규모 어레이를 처리할 때 성능을 크게 향상시킬 수 있는 몇 가지 실용적인 솔루션을 소개합니다.

방법 1: 해시 테이블 사용

요소를 키로 사용하여 배열을 해시 테이블로 변환합니다.
다른 배열을 반복하고 해시 테이블에 키가 있는지 확인하세요. 존재하는 경우 요소는 교차점에 있습니다.
시간 복잡성: O(n)

코드 예:

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

$hash = array_flip($arr1);

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

로그인 후 복사

방법 2: Hashes.php 라이브러리 활용

효율적인 해시를 제공하는 Hashes.php와 같은 라이브러리를 사용하세요. 깨달았다.
교차로 연산에는 Intersect() 方法。对于并集运算，使用 Union() 메소드를 사용하세요.
시간 복잡도: O(n)

코드 예:

use Hashes\Hash;

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

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

로그인 후 복사

방법 3: 비트 연산

을 사용하여 배열의 각 숫자를 비트 비트맵으로 변환합니다.
두 개의 비트맵을 AND로 연결하여 교차점을 얻을 수 있습니다.
두 개의 비트맵을 OR로 합집합을 얻을 수 있습니다.
시간 복잡도: O(n), 여기서 n은 배열에서 가장 큰 숫자의 자릿수입니다.

코드 예:

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

로그인 후 복사

실용 예

100만 개의 요소가 포함된 배열을 고려하고 500만 개의 요소가 포함된 다른 배열과의 교차점 및 합집합을 찾고 싶습니다.

방법 1(해시 테이블) 사용: