Struktur data berasaskan jadual hash mengoptimumkan persilangan tatasusunan PHP dan pengiraan kesatuan

Gunakan jadual cincang untuk mengoptimumkan persilangan tatasusunan PHP dan pengiraan kesatuan, mengurangkan kerumitan masa daripada O(n * m) kepada O(n + m) Langkah-langkah khusus adalah seperti berikut: gunakan jadual cincang untuk menambah elemen tatasusunan pertama Peta kepada nilai Boolean untuk mencari dengan cepat sama ada unsur itu wujud dalam tatasusunan kedua dan meningkatkan kecekapan pengiraan persilangan. Gunakan jadual cincang untuk menandakan elemen tatasusunan pertama sebagai sedia ada, dan kemudian tambahkan elemen tatasusunan kedua satu demi satu, mengabaikan elemen sedia ada untuk meningkatkan kecekapan pengiraan kesatuan.

Pengoptimuman persilangan tatasusunan PHP dan pengiraan penyatuan berdasarkan jadual cincang

Kata Pengantar

Memproses persilangan tatasusunan dan penyatuan dalam PHP adalah operasi biasa, terutamanya apabila melibatkan operasi yang besar bagi data. Untuk mengoptimumkan pengiraan ini, kami boleh menggunakan jadual cincang untuk meningkatkan kecekapan.

Jadual Hash

Jadual cincang ialah struktur data yang memetakan kunci kepada nilai. Sifat utama jadual cincang ialah ia boleh mencari dan memasukkan elemen dengan sangat cekap.

Optimumkan pengiraan persilangan tatasusunan menggunakan jadual cincang

Pertimbangkan kod berikut, yang mengira persilangan dua tatasusunan:

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

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

  return $result;
}

Kerumitan masa kod ini ialah O(n * m), dengan n dan m ialah arr1 masing-masing dan panjang arr2. Kita boleh menggunakan jadual cincang untuk memetakan elemen arr1 kepada nilai boolean yang menunjukkan sama ada elemen itu hadir dalam arr1. Kami kemudiannya boleh melelakan ke atas arr2 dan mencari dengan cepat jika elemen hadir dalam arr1 menggunakan nilai kunci yang sepadan dalam jadual cincang.

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

Kerumitan masa kod ini ialah O(n + m) kerana ia hanya berulang melalui setiap tatasusunan sekali.

Gunakan jadual cincang untuk mengoptimumkan pengiraan kesatuan tatasusunan

Untuk pengiraan kesatuan tatasusunan, kami juga boleh menggunakan jadual cincang. Mula-mula, kami memetakan elemen dalam tatasusunan pertama ke dalam jadual cincang. Kami kemudian menambah setiap elemen dalam tatasusunan kedua pada jadual cincang, mengabaikannya jika ia sudah wujud.

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

Kerumitan masa kod ini ialah O(n + m) kerana ia hanya berulang melalui setiap tatasusunan sekali.

Kes praktikal

Andaikan kita mempunyai dua tatasusunan dengan panjang 100,000 dan 50,000. Purata masa yang diperlukan untuk mengira persilangan dan kesatuan menggunakan pelaksanaan asal dan jadual hash pelaksanaan yang dioptimumkan masing-masing adalah seperti berikut:

0 Saat0.05 saatKesatuan1.80 saat0.10 saat

Operasi	Pelaksanaan asal	Jadual cincang dioptimumkan

🎜🎜🎜Seperti yang kita lihat, pelaksanaan pengoptimuman jadual persilangan cincang dengan ketara dan pengoptimuman 🎜

Atas ialah kandungan terperinci Struktur data berasaskan jadual hash mengoptimumkan persilangan tatasusunan PHP dan pengiraan kesatuan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!