高速検索アルゴリズムとそのPHPへの応用

PHP は、人気のあるサーバーサイド プログラミング言語として、Web アプリケーション開発において不可欠な役割を果たしています。実際の開発では、大量のデータに対して検索や検索などの操作を行うことが多く、その際、検索アルゴリズムの高速化は非常に重要な方向性となっています。

この記事では、PHP でよく使われる高速検索アルゴリズムとその応用例を紹介します。

1. 概要

データ構造において、「検索」とは、データ集合の中から指定した条件でデータレコードを検索することを指し、一般的な検索方法としては、線形検索、二分検索、ハッシュ検索などが挙げられます。

線形検索は最も基本的な検索アルゴリズムであり、データ コレクション内のすべての要素を順番に走査し、ターゲット データが見つかるまでターゲット データと 1 つずつ照合します。時間計算量は O(n) です。

二分探索は、より効率的な検索アルゴリズムであり、順序付けられたシーケンスの特性を利用して、毎回検索範囲を半分に減らし、ターゲット データの位置を素早くロックします。時間計算量は O(log2n) であり、効率は非常に高くなります。

ハッシュ検索は、ハッシュテーブルに基づいた高速な検索アルゴリズムです。ハッシュテーブル内の目的のデータの位置を高速に特定できます。計算量はO(1)で、非常に効率的です。メソッド、アルゴリズム。

PHP で一般的に使用される高速検索アルゴリズムには、順序付けされた配列検索、バイナリ検索、ハッシュ検索、トライ木検索などが含まれます。

2. 順序付き配列検索

順序付き配列検索は、順序付き配列に基づく検索アルゴリズムです。配列要素の規則的な配置を利用し、検索ごとにすばやく検索を絞り込むことができます。 。

PHP では、順序付けされた配列検索は、PHP の組み込みの array_search() 関数によって実装できます。この関数は二分探索アルゴリズムを使用して実装されており、配列内のターゲット データの位置をすばやく見つけることができます。たとえば、100000 個の順序付けされた要素を含む配列内の要素 10 を検索する場合、コードは次のとおりです:

$arr = range(1, 100000); // 100000 個の要素の順序付けされた配列を生成します
$index = array_search(10, $arr); // 配列内の対象要素 10 の位置を検索します

array_search() 関数は PHP に付属する標準ライブラリ関数であるため、そのパフォーマンスは非常に優れています効率的で時間は複雑 次数は O(log2n) です。

3. 二分探索

二分探索は、順序付けられた配列に基づく分割統治アルゴリズムで、配列を 2 等分し、目的のデータが左側にあるかどうかを判定します。半分または右半分を選択し、目的のデータを再帰的に検索し続けることで、迅速なデータ取得を実現します。

PHP では、カスタム関数を使用して二分検索を実装できます。たとえば、100,000 個の順序付けされた要素を含む配列内の要素 20 を検索するには、コードは次のようになります。

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 = range(1, 100000); // 100000 要素の順序付き配列を生成します
$index = binary_search($arr, 0, 99999, 20); // を検索しますtarget 配列内の要素 20 の位置

二分探索アルゴリズムの時間計算量は O(log2n) であるため、非常に効率的であり、大量のデータの検索に適しています。

4. ハッシュ検索

ハッシュ検索は、ハッシュ テーブルに基づく高速検索アルゴリズムで、PHP の組み込み hash() 関数を通じて PHP に実装できます。

まず、ハッシュ テーブルにデータを挿入する必要があります。foreach ループを通じて配列を走査し、各要素の値をキーとして使用し、要素のインデックスを次のようにハッシュ テーブルに挿入します。値。例:

$arr = range(1, 100000); // 100000 要素の配列を生成します
$hash = array();

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

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

}

次に、hash() 関数を通じてターゲット要素を取得できます。たとえば、上記の例では、要素 20 を取得するコードは次のとおりです:

$index = isset($hash[20]) ? $hash[20] : -1; // 要素 20 を取得配列内の位置

ハッシュ検索アルゴリズムの計算量は O(1) であるため、非常に効率的で大規模なデータの検索に適しています。

5. トライ ツリー検索

トライ ツリーは、ツリー構造に基づいた効率的な文字列検索アルゴリズムであり、高速な文字列マッチングとプレフィックス検索を実現できます。 PHP では、これは Trie ツリー クラスをカスタマイズすることで実現できます。

まず、トライ ツリーを構築し、文字列をトライ ツリーに挿入する必要があります。たとえば、次のコードでは、3 つの文字列「hello」、「world」、「php」がトライ ツリーに挿入されます。

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

}

class TrieNode {

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

}

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

これで、Trie ツリーを通じて目的の文字列を見つけることができます。たとえば、上記の例では、文字列「php」を検索するコードは次のようになります:

function search($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"); // 文字列 "php" を検索します。

トライ ツリーの時間計算量は文字列の長さに関係するため、トライ ツリーはキーワード フィルタリング、文字列一致、その他のシナリオなど、文字列の長さが固定されているシナリオに適しています。

6. 概要

この記事では、順序付けされた配列検索、バイナリ検索、ハッシュ検索、トライ木検索などを含む、PHP で一般的に使用される高速検索アルゴリズムとそのアプリケーションを紹介します。

これらのアルゴリズムにはそれぞれ独自の長所と短所があり、さまざまなシナリオで使用して、効率的なデータ取得と文字列照合を実現できます。実際の開発では、特定の状況に基づいて適切なアルゴリズムを選択する必要があります。

以上が高速検索アルゴリズムとそのPHPへの応用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。