Где я могу найти алгоритм, используемый для написания каждого PHP «встроенного»? функционировать?

Недавно я создал приложение на основе 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, или эта информация является собственностью?

0

Решение

Встроенные функции 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, он будет меньше и быстрее.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]