Используйте поиск по хешу, а не обход массива

Довольно-таки часто встречается задача: проверить, совпадает ли строка с другими строками из набора. Например, вам нужно проверить каждое слово из сообщения на форуме на предмет того, не содержится ли оно в списке запрещённых. Распространённое решение: создать массив со списком запрещённых слов, а затем с помощью функции 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(), имеет линейную сложность — 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 

Вообще, тут ничего нового нет

Это не новая идея. Это довольно-таки распространённый подход во многих языках. Я недавно понял вдруг, что постоянно использую для подобных задач поиск по хэшу, пока читал книгу «Программирование на Lua».

В следующий раз, когда будете использовать in_array() для проверки, задумайтесь, а не ускорится ли работа, если вместо этого использовать функцию isset() на ключах ассоциативного массива.