php - PHP の爆発/内破の時間計算量

Question

PHP が爆発/内破関数に使用するアルゴリズムと、それらの時間の複雑さを知っているかどうかに興味がありますか?

前もって感謝します。

Answer 1

でstring.cアルゴリズムを見ることができます。1021行くらいから始まります..

    if (p2 == NULL) {
    add_next_index_stringl(return_value, p1, Z_STRLEN_P(str), 1);
    } else {
    do {
        add_next_index_stringl(return_value, p1, p2 - p1, 1);
        p1 = p2 + Z_STRLEN_P(delim);
    } while ((p2 = php_memnstr(p1, Z_STRVAL_P(delim), Z_STRLEN_P(delim), endp)) != NULL &&
             --limit > 1);

    if (p1 <= endp)
        add_next_index_stringl(return_value, p1, endp-p1, 1);
    }

それはただの単一のループなので、私はそれをO(N)複雑だと呼びます。そして、コードを注意深くチェックしてください。文字列をスキャンし、結果を に追加しreturn_valueます。あ、はい。その線形。

Answer 2

簡単な答え： 1バイトの区切り文字の場合、explodeの時間の複雑さはΟ（N‍）にあります。ただし、複数バイトの区切り文字の場合、時間計算量はΟ（N‍ <sup> 2）です。

implode単にピースを接着するだけなので、明らかにΟ（N‍ ）になります。

拡張回答：の基本的なアルゴリズムは、explode文字列内の区切り文字の出現を検索し、囲まれた部分文字列を新しい配列にコピーすることです。

文字列内の区切り文字の位置を見つけるために、内部関数を使用します（はのエイリアスにすぎません）。1バイトの場合、線形検索を実行することを呼び出すだけです（したがって、Ο（N）で）。zend_memnstrphp_memnstrzebd_memnstrmemchr

ただし、1バイトより長い区切り文字値の場合は、文字列内の区切り文字memchrの最初のバイトの位置を検索し、区切り文字の最後のバイトが文字列内の予想される位置にあるかどうかをテストし、その間のバイトもチェックするように呼び出します。したがって、基本的に、可能な位置の文字列に区切り文字が含まれているかどうかをチェックします。これはすでにΟ（ N‍ <sup> 2）のように疑わしいように聞こえます。memcmp

次に、このアルゴリズムの最悪のケースを見てみましょう。パターンの最初と最後のバイトの両方が適合しますが、最後から2番目のバイトは適合しません。例：

string:     aaaabaaaa
delimiter:  aaaaaa

aaaabaaaa
aaaaXa      (1+1+5)
 aaaX?a     (1+1+4)
  aaX??a    (1+1+3)
   aX???a   (1+1+2)

Aは、不明なバイトXの不一致を表します。括弧内の値は、均一測定での時間計算量です。これは合計するとmemcmp?

M -floor（N / 2）からceil（N / 2 ）までのiのΣ（2+ i）

また

（N -‍ <em> M + 1）・2+ Σi -- Σjfor i from 1 to ceil（N / 2）、j from 1 to M -floor（N / 2）-1。

1からNまでのiのΣiはN・（N +1）/ 2 =（N ² + N ）/ 2で表すことができるため、次のように書くこともできます。

（N -‍ <em> M + 1）・2 +（ceil（N / 2）² + ceil（N / 2））/ 2-（（M -floor（N / 2）-1）² +（M -floor（N / 2）-1））/ 2

簡単にするために、 NとMの両方が常に偶数であると仮定して、「ceil」と「floor」を省略できます。

（N -‍ <em> M + 1）・2 +（（N / 2 + 1）² + N / 2 + 1）/ 2-（（M -‍<em> N / 2-1）² +（M -‍ <em> N / 2）-1）/ 2
=（N -‍<em> M + 1）・2 + N 2/8 ⁺ 3・N / 4 + 1-（（M -‍<em > N / 2-1）² +（M -‍ <em> N / 2）-1）/ 2

さらに、値を上に見積もることができます：N -‍ <em> M< NおよびM -‍<em> N /2-1< N。したがって、次のようになります。

N・2 + N 2/8 ⁺ 3・N / 4 + 1-（N ² + N）/ 2
< N・2 + N ² + 4・N - N ² + N

explodeこれは、複数のバイト区切り文字がΟ（N ² ）にあることを証明します。

Answer 3

GitHub の PHP ソースによると、線形です。explode() ここで確認できます。