Довольно-таки часто встречается задача: проверить, совпадает ли строка с другими строками из набора. Например, вам нужно проверить каждое слово из сообщения на форуме на предмет того, не содержится ли оно в списке запрещённых. Распространённое решение: создать массив со списком запрещённых слов, а затем с помощью функции
Обычно проверка происходит так:
Такой способ решает задачу, но он не самый эффективный. Проходим по массиву слов в сообщении и проверяем каждое на нахождение в списке запрещённых функцией
Так как список плохих слов заранее известен, можно переработать способ сравнения так, что он будет иметь константную сложность, не зависящую от количества запрещённых слов в списке. Для этого можно использовать ассоциативные массивы. Как и в случае с хеш-таблицами, скорость поиска ключа в массиве равна O(1), за исключением некоторых случаев, которые в нашей ситуации не возникнут.
Если мы изменим структуру массива плохих слов таким образом, чтобы его значения стали ключами, а значения по этим ключам стали просто
Давайте попробуем протестировать новый способ. Я написал простой тест, который покажет затраченное время на одном и том же наборе данных для способов: «обыск массива» и «поиск по хешу».
Как видно из листинга, в тесте используется 10 000 повторов. Результат получился таким:
Как видно, поиск по хешу дал прирост в 480% по сравнению с обыском массива.
Важно понимать, что с ростом количества запрещённых слов, увеличивается время, необходимое для обыска массива функцией
Разница в скорости видна намного лучше. Поиск по хешу на 3 162 процента быстрее обыска массива.
Это не новая идея. Это довольно-таки распространённый подход во многих языках. Я недавно понял вдруг, что постоянно использую для подобных задач поиск по хэшу, пока читал книгу «Программирование на Lua».
В следующий раз, когда будете использовать
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()
на ключах ассоциативного массива.