각 PHP의 "내장"함수를 작성하는 데 사용되는 알고리즘은 어디에서 찾을 수 있습니까?

Question

나는 일반적으로 일반적으로 100kB + 문자열에 수천 개의 수천 개의 검사가 있으므로 대상 문자열을 구문 분석하기 위해 (> 10 초) 여러 (> 10) 초가 걸리는 PHP 기반 응용 프로그램을 만들었습니다. 나는 실행 시간을 줄이는 방법을 찾고있다.

각 PHP의 "내장"함수가 어떻게 작성되는지 궁금해졌습니다. 예를 들어, 설명서 (this 링크)의 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, 루프, 또는 다른 방법?

필자는 응용 프로그램에서 함수와 메서드를 프로파일 링하고 이러한 방식으로 중요한 발전을 이루었습니다. 또한 게시물 this 정말 도움이되지 않습니다. PHP의 각 내장 함수에 사용 된 알고리즘은 어디서 찾을 수 있습니까? 아니면이 정보는 독점 정보입니까?

Answer 1

내장 된 PHP 함수는 /ext/standard/ in the PHP source code에서 찾을 수 있습니다.

strpos의 경우 /ext/standard/string.c에 PHP 구현을 찾을 수 있습니다. 의 핵심이 기능은 실제로 zend_memnstr의 별칭 사실 인 php_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로 구현되는 것이 아닙니다. 더 야 위고 더 빠를 것입니다.