Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB