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

Original author: Michael Dowling
  • Translation
Довольно-таки часто встречается задача: проверить, совпадает ли строка с другими строками из набора. Например, вам нужно проверить каждое слово из сообщения на форуме на предмет того, не содержится ли оно в списке запрещённых. Распространённое решение: создать массив со списком запрещённых слов, а затем с помощью функции 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() на ключах ассоциативного массива.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 19

    +1
    Фактически, это множество.

    Тип Map<T, Boolean> изоморфен типу Set<T> (и, например, в Java множество HashSet построено как тонкая обёртка над HashMap). В языках, где нет эффективной поддержки дженериков, множества частно эмулируются через ассоциативные массивы непосредственно. Например, общепринятым в Go способом создания множества (упоминается даже в официальной документации) является использование map[<something>]bool.
      +15
      Краткое содержание: не реализуйте множество через массивы.
        +2
        В данной теме может быть полезной функция array_flip(), естественно, где-нибудь однократно.
          0
          Я обычно использовал array_combine($badWordList, $badWordList), но array_filp() — это даже лучше, спасибо!
            0
            автор, сделай пожалуйста тест с array_flip, потому что все-таки удобнее массив составлять без ключей
              0
              Тест тут какой написать? Если запихнуть array_flip в цикл, то выигрыша естественно не будет, даже наоборот, т. к. каждый раз будет пересоздаваться массив. Если же вынести из цикла, то выигрыш существенный:
              код
              define('TEST_ITER', 100000);
              $data = array('арбуз', 'дыня', 'вишня', 'слива', 'яблоко', 'груша', 'смородина', 'персик', 'абрикос', 'банан', 'виноград', 'киви');
              
              $t = microtime(true);
              for($i=0; $i<TEST_ITER; $i++)
              	$tmp = in_array('картофель', $data);
              var_dump(microtime(true)-$t); // float(0.082980155944824)
              
              
              $t = microtime(true);
              $data = array_flip($data);
              for($i=0; $i<TEST_ITER; $i++)
              	$tmp = isset($data['картофель']);
              var_dump(microtime(true)-$t); // float(0.0057001113891602)
              

          +5
          В следующем примере список запрещённых слов будет состоять из 10 000 элементов.

          Вы только что запретили общаться одной из европейских стран.
            +1
            А что за страна и язык? Я нашёл только информацию про язык Таки во Французской Гвинее — что-то в районе 340 слов.
              +1
              Это, конечно, оффтоп, но я имел в виду обиходный (читай «используемый в повседневном общении») словарь среднестатистического европейца.
            –4
            Очень конечно весело видеть десятикратный прирост. Однако в реальных приложениях разницы между 0.000023 и 0.000123 вы никогда не заметите ибо все одеяло на себя утащат запросы к бд, парсинг больших xml и проч.
              0
              Ну да, алгоритм довольно-таки «тепличный». Хотя, мне всё равно чем-то идея понравилась, поэтому я и решил перевести эту статью.
                +1
                Вот подумайте, у вас есть сервис, который крутится на 10 серверных стойках, а вы с помощью замены алгоритма понизили нагрузку на процессор на 10 процентов, то это значит, что одна из стоек безболезненно может быть отдана под другую задачу.
                Или же вы сможете сэкономить 10% электроэнергии вот просто на замене 10 строчек кода.
                  0
                  Поддержу, размера массива и кол-во обращений играют роль.

                  Помится, в Delphi, по крайней мере, до 7 версии было так.
                  Есть класс TDataSet для наборов данных, в него загружались данные из БД. Данный класс содержит в себе коллекцию полей (Fields), которые предоставляли доступ к значениям полей текущей записи. Доступ к объектам полей по имени, либо через метод FieldByName() либо более простой вариант типа dataset['fieldname']. Вся фишка в том, что эта коллекция построена на основе одного из базовых классов Delpgi — TList, по сути, массив.
                  Когда, по событию нужно прочитать/изменить поля одной записи, это не проблема. Но, например, если нужно обработать большой набор данных, данная особенность вылазила боком.
                  Решение, конечно, есть — получить объекты полей один раз перед циклом. Но сам этот факт вызывал искреннее удивление. В виду того, что в Delphi не было встроенных контейнеров типа хэш и множество, ситуация была не единична.
                  0
                  Я думаю что на массивах в несколько десятков и сотен тысяч элементов разница между O(1) и O(n) будет в разы очевиднее.
                  +5
                  люто
                    0
                    Стоит сказать, что преимущества поиска по ключам массива довольно очевидны, если знать внутренне устройство ассоциативных массивов в PHP. Вот тут подробно всё и разъяснено.
                      0
                      Осмелюсь предположить что через stristr можно аналогично пройтись по тексту, добавив маркер начала/окончания слова. А так же через пересечение масивов array_intersect* (хотя на смотрел как оно в php реализовано в коде, может тупо как в первом варианте перебирает).
                      PS: для получения уникального массива (когда данные идут по очереди) можно все элементы вставлять в массив как ключи (если это возможно), а потом сделать array_keys — отпадает нужна в in_array. Да и много где такое подход крайне удобно использовать.
                        +1
                        Вообще-то для данной задачи существует алгоритм Ахо-Карасик.
                          0
                          Если речь о словах, а не подстроках, до достаточно даже не алгоритма Ахо-Карасик, а структуры данных «бор».

                        Only users with full accounts can post comments. Log in, please.