PHP的explode/implode的时间复杂度

Question

我想知道PHP在使用explode/implode函数时使用了哪些算法，它们的时间复杂度是什么?

提前感谢你。

- Headshota

---

"我想这应该是O(N)。我不认为你可以做得更好或更差。" - NullUserException

@KamilTomšík- 在经常对大数据集进行explode/implode调用的程序中，这可能非常重要。如果该函数是超线性的，那么尝试在大程序中使用这些函数将是一个非常糟糕的主意，OP最好重新实现它们以获得更快的速度。如果它们以某种方式是次线性的，则很值得知道，因为这样重写代码以尝试更频繁地使用explode/implode将是值得的。 - templatetypedef

@KamilTomšík 我需要知道使用 explode 函数的程序运行时间，就这么简单。 - Headshota

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中。所以是的，它是线性的。

- Shiplu Mokaddim

---

一个快速的问题 - Z_STRLEN_P 的复杂度是多少？如果不是O(1)，那么复杂度可能更准确地是O(mn)，其中n是字符串长度，m是分隔符的长度。 - templatetypedef

@templatetypedef 是 O(1)。因为 delim 是一个 zval，而这个宏指向了 (zval).value.str.val。 - Shiplu Mokaddim

Answer 2

短回答：对于单字节定界符，explode的时间复杂度为Ο(N); 但对于多字节定界符，其时间复杂度为Ο(N²)。 implode显然是Ο(N)，因为它只是将片段粘合在一起。

扩展回答：explode的基本算法是搜索string中delimiter的出现，并将封闭的子字符串复制到一个新数组中。

为了在字符串中查找分隔符的位置，它使用 内部函数 zend_memnstr（php_memnstr只是zebd_memnstr的别名）。对于单个字节，它只需调用执行线性搜索的memchr（因此在Ο（N）中）。

但是对于长度超过一个字节的delimiter值，它调用memchr来搜索string中第一个字节的位置，测试delimiter的最后一个字节是否存在于string中的预期位置，并调用memcmp来检查中间的字节。因此，它基本上检查delimiter是否包含在string中的任何可能位置。这听起来已经非常像Ο（N‍²）。

现在让我们来看一下这个算法的最坏情况，即模式的第一个和最后一个字节都匹配，但倒数第二个字节不匹配，例如：

string:     aaaabaaaa
delimiter:  aaaaaa

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

X代表memcmp中的不匹配和未知字节?。括号中的值是均匀度量下的时间复杂度。这将总结为

Σ (2+i)，其中i从M-floor(N/2)到ceil(N/2)

或

(N-‍M+1)·2 + Σ i - Σ j，其中i从1到ceil(N/2)，j从1到M-floor(N/2)-1。

由于Σ i，其中i从1到N可以表示为N·(N+1)/2 = (N²+N)/2，我们也可以写成：

(N-‍M+1)·2 + ((N/2)²+N/2) - ((M-N/2-1)²+M-N/2-1)/2

为了简化，我们假设N和M都是偶数，因此我们可以省略“ceil”和“floor”：

(N-‍M+1)·2 + ((N/2+1)²+N/2+1)/2 - ((M-‍N/2-1)²+(M-‍N/2)-1)/2
= (N-‍M+1)·2 + N²/8+3·N/4+1 - ((M-‍N/2-1)²+(M-‍N/2)-1)/2

此外，我们可以估算出：N-‍M < N和M-‍N/2-1 < N。因此我们得到：

此证明表明，使用多字节分隔符的explode的时间复杂度为Ο(N²)。

N·2 + N²/8+3·N/4+1 - (N²+N)/2
< N·2 + N²+4·N - N²+N

- Gumbo

Answer 3

根据 GitHub 上 PHP 的源代码，它是线性的。你可以在这里检查 `explode()`：链接。

- mirelon