해시 테이블 기반 데이터 구조는 PHP 배열 교차 및 결합 계산을 최적화합니다.

해시 테이블을 사용하여 PHP 배열 교집합 및 합집합 계산을 최적화하여 시간 복잡도를 O(n * m)에서 O(n + m)으로 줄입니다. 구체적인 단계는 다음과 같습니다. 해시 테이블을 사용하여 요소를 추가합니다. 첫 번째 배열 부울 값에 매핑하여 두 번째 배열에 해당 요소가 존재하는지 빠르게 확인하고 교차점 계산의 효율성을 높입니다. 해시 테이블을 사용하여 첫 번째 배열의 요소를 기존 요소로 표시한 다음 기존 요소를 무시하고 두 번째 배열의 요소를 하나씩 추가하여 통합 계산의 효율성을 높입니다.

해시 테이블을 기반으로 한 PHP 배열 교집합 및 합집합 계산 최적화

Foreword

PHP에서 배열 교집합 및 합집합을 처리하는 것은 일반적인 작업이며, 특히 대량의 데이터가 관련된 경우 더욱 그렇습니다. 이러한 계산을 최적화하기 위해 해시 테이블을 활용하여 효율성을 크게 향상시킬 수 있습니다.

해시 테이블

해시 테이블은 키를 값에 매핑하는 데이터 구조입니다. 해시 테이블의 주요 속성은 요소를 매우 효율적으로 찾고 삽입할 수 있다는 것입니다.

해시 테이블을 사용하여 배열 교집합 계산 최적화

두 배열의 교집합을 계산하는 다음 코드를 고려하세요.

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

이 코드의 시간 복잡도는 각 배열을 한 번만 반복하므로 O(n + m)입니다.

해시 테이블을 사용하여 배열 합집합 계산 최적화

배열 합집합 계산에 해시 테이블을 사용할 수도 있습니다. 먼저 첫 번째 배열의 요소를 해시 테이블에 매핑합니다. 그런 다음 두 번째 배열의 각 요소를 해시 테이블에 추가하고 이미 존재하는 경우 무시합니다.

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

이 코드의 시간 복잡도는 각 배열을 한 번만 반복하므로 O(n + m)입니다.

실용 사례

길이가 100,000과 50,000인 두 개의 배열이 있다고 가정합니다. 원래 구현과 해시 테이블 최적화 구현을 각각 사용하여 교차점과 합집합을 계산하는 데 필요한 평균 시간은 다음과 같습니다. 초

0.05초Union1.80초0.10초

보시다시피 해시 테이블 최적화를 구현하면 교차점과 결합체 계산의 효율성이 크게 향상됩니다.

위 내용은 해시 테이블 기반 데이터 구조는 PHP 배열 교차 및 결합 계산을 최적화합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!