Недавно я создал приложение на основе PHP, которое обычно требует нескольких (> 10) секунд для синтаксического анализа целевой строки (> 10 секунд, потому что существует много тысяч проверок на типичной строке 100 кбайт +). Я ищу способы уменьшить время выполнения.
Я начал задаваться вопросом, как записываются каждая из встроенных функций PHP. Например, если вы перейдете к ссылке strpos() в руководстве ( эта ссылка), есть много информации, но не алгоритм.
Кто знает, может быть, я могу написать функцию, которая быстрее, чем встроенная функция для моего конкретного приложения? Но у меня нет способа узнать алгоритм, например, strpos (). Использует ли алгоритм такой метод, как этот:
function strposHypothetical($haystack, $needle) { $haystackLength = strlen($haystack); $needleLength = strlen($needle);//for this question let's assume > 0 $pos = false; for($i = 0; $i < $haystackLength; $i++) { for($j = 0; $j < $needleLength; $j++) { $thisSum = $i + $j; if (($thisSum > $haystackLength) || ($needle[$j] !== $haystack[$thisSum])) break; } if ($j === $needleLength) { $pos = $i; break; } } return $pos; }
или он будет использовать гораздо более медленный метод, скажем, комбинацию substr_count () для появления иглы, а если вхождения> 0, то цикл for или какой-либо другой метод?
Я профилировал функции и методы в своем приложении и сделал значительный прогресс таким образом. Кроме того, обратите внимание, что этот пост не очень помогает. Где я могу узнать алгоритм, используемый для каждой встроенной функции в PHP, или эта информация является собственностью?
Встроенные функции PHP можно найти в / ext / standard / в исходном коде PHP .
В случае strpos вы можете найти реализацию PHP в /ext/standard/string.c . По своей сути эта функция фактически использует php_memnstr , которая на самом деле является псевдонимом zend_memnstr :
found = (char*)php_memnstr(ZSTR_VAL(haystack) + offset, Z_STRVAL_P(needle), Z_STRLEN_P(needle), ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
И если мы читаем источник zend_memnstr , мы можем найти сам алгоритм, используемый для реализации strpos :
while (p <= end) { if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) { if (!memcmp(needle, p, needle_len-1)) { return p; } } if (p == NULL) { return NULL; } p++; }
ne здесь представляет последний символ needle , а p – указатель, который увеличивается для сканирования через haystack .
Функция memchr является функцией C, которая должна выполнять простой линейный поиск через последовательность байтов, чтобы найти первое вхождение данного байта / символа в строке байтов. memcmp – это функция C, которая сравнивает два байтовых / символьных диапазона, которые могут быть внутри строк, сравнивая их побайтно.
Версия псевдокода этой функции выглядит следующим образом:
while (p <= end) { find the next occurrence of the first character of needle; if (occurrence is found) { set `p` to point to this new location in the string; if ((character at `p` + `length of needle`) == last character of needle) { if ((next `length of needle` characters after `p`) == needle) { return p; // Found position `p` of needle in haystack! } } } else { return NULL; // Needle does not exist in haystack. } p++; }
Это довольно эффективный алгоритм для поиска индекса подстроки в строке. Это почти такой же алгоритм для ваших strposHypothetical и должен быть столь же эффективным, насколько это возможно, если memcpy не вернется раньше, как только он увидит, что строки отличаются одним символом и, конечно, реализованы на C, это будет более компактным и быстрым.