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

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.