各PHPの "組み込み"関数の記述に使用されるアルゴリズムはどこにありますか？

Question

私は最近、通常は100kB +文字列に何千ものチェックがあるため、ターゲット文字列を解析するためには数秒（> 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は、2バイト/文字の範囲を比較する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++; 
} 

これは、文字列内のサブストリングのインデックスを見つけるため、かなり効率的なアルゴリズムです。 memcpyは文字列が1文字違うとすぐに早く返されない限り効率的な複雑さになりますが、もちろんC言語で実装されている場合は、それはあなたのstrposHypotheticalと同じアルゴリズムですより早く、より速くなります。