Недавно я создал приложение на основе 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, он будет меньше и быстрее.
Других решений пока нет …