配列検索ではなくハッシュ検索を使用する

かなり頻繁にタスクが発生します：行がセットの他の行と一致するかどうかを確認します。 たとえば、フォーラムのメッセージの各単語が禁止リストに含まれているかどうかを確認する必要があります。 一般的な解決策：禁止された単語のリストを含む配列を作成し、 in_array()



関数を使用して確認します。 このようなアルゴリズムのパフォーマンスを改善する方法があります。

配列検索

通常、チェックは次のように行われます。

 <?php $words = get_all_words_in_text($text); $badWords = ['$$$$', '@#$%', 'crud' /** ... */ ]; foreach ($words as $word) { if (in_array(strtolower($word), $badWords)) { echo 'Found bad word: ' . $word . "\n"; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この方法は問題を解決しますが、最も効果的ではありません。 メッセージ内の単語の配列を調べて、禁止されている関数in_array()



リストにあるかどうかを確認します。 PHPでは、 in_array()



関数をin_array()



するアルゴリズムは線形の複雑さ-O（n）を持ちます。 これは、悪い単語のリストが増えると、稼働時間が比例して長くなることを意味します。 もっと良いものを思いつくことができます。

ハッシュ検索

悪い単語のリストは事前にわかっているため、リスト内の禁止されている単語の数に依存しない一定の複雑さを持つように比較方法を修正できます。 これには連想配列を使用できます。 ハッシュテーブルの場合と同様に、配列内のキー検索速度はO（1）です。ただし、状況によっては発生しない場合もあります。



悪い単語の配列の構造を変更して、その値がキーになり、これらのキーの値がちょうどtrue



になる場合、 isset()



関数を使用して、速度を大幅に向上させることができます。

 <?php $words = get_all_words_in_text($text); $badWords = [ '$$$$' => true, '@#$%' => true, 'crud' => true // ... ]; foreach ($words as $word) { if (isset($badWords[strtolower($word)])) { echo 'Found bad word: ' . $word . "\n"; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

性能試験

新しい方法をテストしてみましょう。 メソッドの同じデータセットに費やされた時間を示す簡単なテストを作成しました：「配列を検索」と「ハッシュで検索」。

 <?php $total = 10000; $paragraph = 'this is a sentence. Crud! $$$$!'; $words = explode(' ', $paragraph); $badWordList = ['$$$$', '@#$%', 'crud', 'fud', 'fudd', 'dud']; $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { in_array(strtolower($word), $badWordList); } } echo "in_array: " . (microtime(true) - $s) . "\n"; $badWordHash = [ '$$$$' => true, '@#$%' => true, 'crud' => true, 'fud' => true, 'fudd' => true, 'dud' => true ]; $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { isset($badWordHash[strtolower($word)]); } } echo "hash: " . (microtime(true) - $s) . "\n";
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リストからわかるように、テストでは10,000回の繰り返しが使用されます。 結果は次のとおりです。

 in_array: 0.033491134643555 hash: 0.0069370269775391
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、ハッシュ検索では、配列の検索に比べて480％の増加が見られました。



禁止されている単語の数が増えると、 in_array()



関数で配列を検索するのに必要な時間が長くなることを理解することが重要です。 ただし、 isset()



は要素の数に依存せず、その操作時間は一定のままです。 私が何を意味したかをお見せしましょう。 次の例では、禁止されている単語のリストは10,000個の要素で構成されます。

 <?php $total = 10000; $paragraph = 'this is a sentence. Crud! $$$$!'; $words = explode(' ', $paragraph); //     $sequence = []; for ($j = 0; $j < 10000; $j++) { $sequence[] = 'a' . $j; } $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { in_array(strtolower($word), $sequence); } } echo "in_array: " . (microtime(true) - $s) . "\n"; //     $hash = array_fill_keys($sequence, true); $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { isset($hash[strtolower($word)]); } } echo "hash: " . (microtime(true) - $s) . "\n";
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

速度の違いはずっとよく見えます。 ハッシュ検索は、配列検索よりも3 162％高速です。

 in_array: 20.464313983917 hash: 0.0064699649810791
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一般的に、新しいものは何もありません

これは新しいアイデアではありません。 これは多くの言語でかなり一般的なアプローチです。 私は最近、「 プログラミングon Lua 」という本を読んでいるときに、そのようなタスクに常にハッシュ検索を使用していることに突然気付きました。



次回in_array()



を使用してチェックするときは、連想配列のキーでisset()



関数を代わりに使用した場合に作業が高速化されるかどうかを検討します。