Эффективность Preg_replace

Question

Резюме:

preg_replace() выполняется быстрее, чем сравнение строк. Зачем? Разве регулярные выражения не должны быть медленнее?

---

В недавнем вопросе об обнаружении любого из массива запрещенных подстрок в данном входном сигнале я предложил сравнить результат вызова preg_replace() с исходным входным параметром, поскольку preg_replace() может занять массив шаблонов в качестве входных данных. Таким образом, мой метод для этого может быть один if, тогда как другие решения требуют одного (или нескольких) циклов.

Мне не интересно обсуждать мой ответ, потому что на самом деле он менее читабелен / удобен в обслуживании, чем циклы. Мой ответ там все еще содержит -1, и я приму его для удобства чтения / простоты обслуживания, но самая большая ошибка, указанная в моем методе, была недостаточной эффективностью. Это вызвало у меня любопытство и привело к некоторым испытаниям. Мои результаты были немного удивительны для меня: при прочих равных условиях preg_replace() был быстрее , чем любой другой метод.

Можете ли вы объяснить, почему это произошло?

Мой код для этих тестов можно найти ниже вместе с результатами:

$input = "In a recent question about detecting any of an array of disallowed substrings within a given input, I suggested comparing the result of a `preg_replace()` call to the original input, since `preg_replace()` can take an array of patterns as input. Thus my method for this could be a single `if` whereas the other solutions required one (or many) loops. I'm not interested in debating my answer, because really it is less readable/maintainable than the loops. However, the biggest fault pointed out with my method was a lack of efficiency. That got me curious, and led me to do some testing. My results were a bit surprising to me: with all other factors held equal, `preg_replace()` was **faster** than any of the other methods. Can you explain why this was the case?";
$input2 = "Short sentence - no matches";
$input3 = "Word";
$input4 = "Short sentence - matches loop";

$start1 = microtime(true);
$rejectedStrs = array("loop", "efficiency", "explain");
$p_matches = 0;
for ($i = 0; $i < 10000; $i++) {
    if (str_check($rejectedStrs, $input)) $p_matches++;
    if (str_check($rejectedStrs, $input2)) $p_matches++;
    if (str_check($rejectedStrs, $input3)) $p_matches++;
    if (str_check($rejectedStrs, $input4)) $p_matches++;
}

$start2 = microtime(true);
$rejectedStrs = array("loop", "efficiency", "explain");
$l_matches = 0;
for ($i = 0; $i < 10000; $i++) {
    if (loop_check($rejectedStrs, $input)) $l_matches++;
    if (loop_check($rejectedStrs, $input2)) $l_matches++;
    if (loop_check($rejectedStrs, $input3)) $l_matches++;
    if (loop_check($rejectedStrs, $input4)) $l_matches++;
}

$start3 = microtime(true);
$rejectedStrs = array("/loop/", "/efficiency/", "/explain/");
$s_matches = 0;
for ($i = 0; $i < 10000; $i++) {
    if (preg_check($rejectedStrs, $input)) $s_matches++;
    if (preg_check($rejectedStrs, $input2)) $s_matches++;
    if (preg_check($rejectedStrs, $input3)) $s_matches++;
    if (preg_check($rejectedStrs, $input4)) $s_matches++;
}

$end = microtime(true);
echo $p_matches." ".$l_matches." ".$s_matches."\n";
echo "str_match: ".$start1." ".$start2."= ".($start2-$start1)."\nloop_match: ".$start2." ".$start3."=".($start3-$start2)."\npreg_match: ".$start3." ".$end."=".($end-$start3);

function preg_check($rejectedStrs, $input) {
    if($input == preg_replace($rejectedStrs, "", $input)) 
        return true;
    return false;
}

function loop_check($badwords, $string) {

    foreach (str_word_count($string, 1) as $word) {
        foreach ($badwords as $bw) {
            if (stripos($word, $bw) === 0) {
                return false;
            }
        }
    }
    return true;
}

function str_check($badwords, $str) {
    foreach ($badwords as $word) {
        if (stripos(" $str ", " $word ") !== false) {
            return false;
        }
    }
    return true;
}

Результаты

20000 20000 20000

str_match: 1282270516.6934 1282270518.5881 = 1,894730091095

loop_match: 1282270518.5881 1282270523.0943 = 4.5061857700348

preg_match: 1282270523.0943 1282270523.6191 = 0,52475500106812

Answer 1

Давайте сначала посмотрим на preg_check и loop_check. Им обоим придется пройти всю строку, и им придется проверять каждое из отдельных слов в каждом обходе. Таким образом, их поведение будет, по крайней мере, O(n*m), где n - длина строки и m - количество плохих слов. Вы можете проверить это, запустив алгоритм с увеличивающимися значениями n и m и построив 3D-графики (однако вам может потребоваться или не потребоваться запустить его с очень высокими значениями n и m чтобы увидеть это поведение).

loop_check является более (асимптотически) эффективным здесь. Причина в том, что количество слов в строке не пропорционально их длине - я, кажется, напоминаю, что обычно она следует логарифмической функции. Вероятно, он использует хеш-таблицу для хранения слов, которые он находит путем, что делается в среднем постоянном времени (если мы игнорируем, что нам, возможно, придется время от времени перестраивать хеш-таблицу, чтобы вместить больше элементов).

Следовательно, loop_check будет иметь асимптотическое поведение, следующее за чем-то вроде n + m * log(n), что лучше, чем n*m.

Теперь, это относится к асимптотическому поведению алгоритмов, то есть, когда m и n растут очень (и это может потребовать "очень очень") большого. При малых значениях m и n константы играют большую роль. В частности, выполнение кодов операций PHP и вызовов функций PHP обходится дороже, чем та же задача, реализованная в C, всего в одном вызове функции. Это не делает алгоритм регулярного выражения более быстрым, он просто ускоряет его при малых значениях m и n.

Answer 2

Можете ли вы объяснить, почему это было так?

Easy. preg_match реализован на C. Другие решения реализованы на PHP. Теперь это не означает, что регулярное выражение будет всегда быстрее, чем эквивалентный PHP, но в большинстве случаев это, вероятно, будет.

Недавно у меня была похожая ситуация, когда у меня была функция (конвертер CamelCase), которая вызывалась десятки тысяч раз и занимала изрядное количество ЦП (я профилировал). Я пробовал каждую реализацию PHP, которую только мог придумать. preg_replace всегда был быстрее. В конце я оставил функцию такой, какой она была, и запомнил ее, что и помогло.

Во многих случаях, чем меньше выполнено PHP-операторов, тем лучше. Если вы можете заменить цикл одним вызовом функции, которая реализована в C под капотом, это может быть вашим лучшим выбором.

на самом деле он менее читабелен / удобен в обслуживании, чем циклы

Я не согласен. Однострочники настолько просты, насколько это возможно. Хотя я бы, наверное, пошел с чем-то более похожим на

function preg_check($rejectedStrs, $input) {
    return preg_match($rejectedStrs, "", $input);
}