Algoritma mendapatkan semula berkelajuan tinggi dan aplikasinya dalam PHP

Sebagai bahasa pengaturcaraan sebelah pelayan yang popular, PHP memainkan peranan yang sangat diperlukan dalam pembangunan aplikasi web. Dalam pembangunan sebenar, kita selalunya perlu melakukan operasi seperti mendapatkan semula dan mencari pada jumlah data yang besar Pada masa ini, algoritma mendapatkan semula berkelajuan tinggi telah menjadi arah yang sangat penting.

Artikel ini akan memperkenalkan algoritma perolehan semula berkelajuan tinggi yang biasa digunakan dalam PHP dan aplikasinya.

1. Gambaran Keseluruhan

Dalam struktur data, perolehan merujuk kepada mencari rekod data dengan syarat tertentu dalam pengumpulan data termasuk carian linear, carian binari, dll.

Carian linear ialah algoritma carian paling asas Ia merentasi semua elemen dalam pengumpulan data secara bergilir-gilir dan memadankan data sasaran satu demi satu sehingga data sasaran ditemui. Kerumitan masa ialah O(n).

Carian binari ialah algoritma carian yang lebih cekap Ia menggunakan ciri-ciri urutan tersusun untuk mengurangkan julat carian sebanyak separuh setiap kali dan mengunci lokasi data sasaran dengan cepat. Kerumitan masa adalah O(log2n) dan kecekapannya sangat tinggi.

Carian cincang ialah algoritma carian berkelajuan tinggi berdasarkan jadual cincangan Ia boleh mencari lokasi data sasaran dalam jadual cincangan Kerumitan masa ialah O(1). algoritma.

Dalam PHP, beberapa algoritma carian berkelajuan tinggi yang biasa digunakan termasuk carian tatasusunan tertib, carian binari, carian cincang, carian pokok Trie, dsb.

2. Carian tatasusunan tersusun

Carian tatasusunan tertib ialah algoritma carian berdasarkan susunan tersusun .

Dalam PHP, carian tatasusunan tertib boleh dilaksanakan melalui fungsi array_search() terbina dalam PHP, yang dilaksanakan menggunakan algoritma carian binari dan boleh mengesan kedudukan data sasaran dalam tatasusunan dengan cepat. Contohnya, untuk mencari elemen 10 dalam tatasusunan yang mengandungi 100000 elemen tertib, kodnya adalah seperti berikut:

$arr = julat(1, 100000); // Hasilkan tatasusunan tertib 100000 elemen
$ index = array_search(10, $arr); // Cari kedudukan elemen sasaran 10 dalam tatasusunan

Memandangkan fungsi array_search() ialah fungsi perpustakaan standard yang disertakan dengan PHP, prestasinya sangat cekap dan masa adalah kompleks Darjahnya ialah O(log2n).

3. Carian binari

Carian binari ialah algoritma bahagi-dan-takluk berdasarkan tatasusunan tertib Ia membahagikan tatasusunan kepada dua bahagian yang sama dan menentukan sama ada data sasaran berada di sebelah kiri separuh atau Separuh kanan, dan teruskan mencari data sasaran secara rekursif untuk mencapai perolehan data dengan cepat.

Dalam PHP, carian binari boleh dilaksanakan melalui fungsi tersuai. Contohnya, untuk mencari elemen 20 dalam tatasusunan yang mengandungi 100,000 elemen tertib, kodnya adalah seperti berikut:

function binary_search($arr, $low, $high, $target) {

while ($low <= $high) {
    $mid = ($low + $high) >> 1;
    if ($arr[$mid] === $target) {
        return $mid;
    } elseif ($arr[$mid] > $target) {
        $high = $mid - 1;
    } else {
        $low = $mid + 1;
    }
}

return -1;

}

$arr = julat(1, 100000); // Hasilkan tatasusunan tertib 100000 elemen
$index = binary_search($arr, 0, 99999, 20); kedudukan elemen 20 dalam tatasusunan

Memandangkan kerumitan masa bagi algoritma carian binari ialah O(log2n), ia sangat cekap dan sesuai untuk mendapatkan semula jumlah data yang besar.

4. Carian cincang

Carian cincang ialah algoritma carian berkelajuan tinggi berdasarkan jadual cincang, yang boleh dilaksanakan dalam PHP melalui fungsi cincang() terbina dalam PHP.

Pertama, kita perlu memasukkan data ke dalam jadual cincang Kita boleh melintasi tatasusunan melalui gelung foreach, menggunakan nilai setiap elemen sebagai kunci dan memasukkan indeks elemen ke dalam jadual cincang sebagai. nilainya. Contohnya:

$arr = julat(1, 100000); // Hasilkan tatasusunan 100000 elemen
$hash = array();

foreach ($arr sebagai $k = > $v) {

$hash[$v] = $k; // 插入元素到哈希表中

}

Kemudian, kita boleh mendapatkan semula elemen sasaran melalui fungsi hash(). Sebagai contoh, dalam contoh di atas, kod untuk mendapatkan semula elemen 20 adalah seperti berikut:

$index = isset($hash[20]) ? dalam Kedudukan tatasusunan dalam

Memandangkan kerumitan masa algoritma carian cincang ialah O(1), ia sangat cekap dan sesuai untuk mendapatkan semula data berskala besar.

5. Carian pokok cuba

Pokok Trie ialah algoritma pengambilan rentetan yang cekap berdasarkan struktur pokok, yang boleh mencapai padanan rentetan dan carian awalan yang pantas. Dalam PHP, ini boleh dicapai dengan menyesuaikan kelas pokok Trie.

Pertama, kita perlu membina pokok Trie dan memasukkan rentetan ke dalam pokok Trie. Contohnya, dalam kod berikut, tiga rentetan "hello", "world" dan "php" dimasukkan ke dalam pokok Trie:

class Trie {

private $root;

public function __construct() {
    $this->root = new TrieNode();
}

public function insert($word) {
    $node = $this->root;

    for ($i = 0; $i < strlen($word); $i++) {
        $char = $word{$i};

        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode();
        }

        $node = $node->children[$char];
    }

    $node->is_end = true;
}

}

kelas TrieNode {

public $children = array();
public $is_end = false;

}

$trie = new Trie();
$trie->insert("hello");
$trie-> ; insert("world");
$trie->insert("php");

Kemudian, kita boleh mencari rentetan sasaran melalui pokok Trie. Contohnya, dalam contoh di atas, kod untuk mencari rentetan "php" akan kelihatan seperti ini:

carian fungsi($trie, $word) {

$node = $trie->root;

for ($i = 0; $i < strlen($word); $i++) {
    $char = $word{$i};

    if (!isset($node->children[$char])) {
        return false;
    }

    $node = $node->children[$char];
}

return $node->is_end;

}

$found = search($trie, "php"); // Cari rentetan "php"

Memandangkan kerumitan masa pokok Trie berkaitan dengan panjang rentetan, pokok Trie sesuai untuk senario dengan panjang rentetan tetap Seperti penapisan kata kunci, padanan rentetan dan senario lain.

6. Ringkasan

Artikel ini memperkenalkan algoritma perolehan semula berkelajuan tinggi yang biasa digunakan dalam PHP dan aplikasinya, termasuk carian tatasusunan tertib, carian binari, carian cincang, carian pokok Trie, dsb.

Algoritma ini masing-masing mempunyai kelebihan dan kekurangannya sendiri, dan boleh digunakan dalam senario yang berbeza untuk mencapai perolehan semula data dan pemadanan rentetan yang cekap. Dalam pembangunan sebenar, kita perlu memilih algoritma yang sesuai berdasarkan situasi tertentu.

Atas ialah kandungan terperinci Algoritma mendapatkan semula berkelajuan tinggi dan aplikasinya dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!