日期:2014-05-17  浏览次数:20401 次

再谈PHP中的str_repeat函数实现

前段时间讨论了在PHP中生成某多个某字符或字符串的字符串的问题,呵呵。这句话听起来太别扭了。举个例子就是,生成10个a的字符串就是aaaaaaaaaa。当然这里的a可以是ab或任何其他字符串。

?

在博客“生成固定长度的某字符的字符串 PHP ”中描述了一共5中方法。也对这五种方法的效率进行了比对,其中以PHP中自带的str_repeat函数效率最优,这也在意料和情理之中。

方法4,5都是对PHP本身的函数进行了组配以实现相同的功能,虽然没有str_repeat优秀,但是其效率还是好过了方法1,和方法2.

?

方法1,2是用PHP语言自己实现的逻辑,通过字符串的迭代拼接实现的,效率当然不能和PHP中的builtin方法相提并论。

?

今天看到了PHP中的str_repeat函数的实现,仔细一看,原来和自己实现的方法1中的思路是“异曲同工”啊。那PHP中的str_repeat究竟是怎么做的呢?核心逻辑代码如下:

?

    result_len = input_len * mult;
    result = (char *)safe_emalloc(input_len, mult, 1);
    
    /* Heavy optimization for situations where input string is 1 byte long */
    if (input_len == 1) { 
        memset(result, *(input_str), mult); 
    } else {
        char *s, *e, *ee; 
        int l=0; 
        memcpy(result, input_str, input_len);
        s = result;
        e = result + input_len;
        ee = result + result_len;

        while (e<ee) {
            l = (e-s) < (ee-e) ? (e-s) : (ee-e);
            memmove(e, s, l);
            e += l;
        }
    }

    result[result_len] = '\0';

首先计算了结果字符串的长度。并分配了对应的内存空间。

然后将input_str拷贝到分配内存空间的最开始,

然后迭代将已经拷贝的内容复制到剩余的内存空间。

从代码逻辑可以看出,复制的思路不是一份一份复制的,而是复制一份、两份、四份、八份......

直到填满所分配的内存空间,然后奖内存空间的最后一位赋值为'\0'。

?

初次看到这段代码时对以下代码逻辑有不解:

?

     while (e<ee) {
            l = (e-s) < (ee-e) ? (e-s) : (ee-e);
            memmove(e, s, l);
            e += l;
        }

所分配的内存空间一定是input_str的整数倍+1。因此如果每次只是向后移一倍原始字符串长度的话,只需要在剩余长度小于原始字符串长度时退出循环,然后在将最后一位赋值为'\0'。不就可以了吗?

?

如果你也是这么想的,那么你和我刚开始犯了同样的错误。

因为,原始字符串的复制不是一份一份地进行的。如果复制7份的话(即str_repeat("abc",7);),只需要复制4次(包括第一次)。

而且最后一次复制之前剩余的未赋值的内存空间为原始字符串长度的3倍+1,即3*3+1。只需要将"abcabcabcabc"字符串中的前10个字符进行复制。这样,result_str最后一个字符必定是原始字符串的第一个字符,'a'。这个‘a’本来就是不要的。

?

索性直接:

result[result_len] = '\0';

其实就是最后字符串中那个不需要的'a'替换为字符串的结束符'\0'。

?

这样str_repeat函数就完成了。

?

****************************************************************

此外:

博客“生成固定长度的某字符的字符串 PHP ”中的方法1,虽然思想上和str_repeat一致,但是采用了字符串拼接方式,而且每次拼接都要产生新的字符串,对内存空间也是极大的浪费,如下示例:

?

如果要生成8个‘a’的字符串,首先会生成'aa',然后是‘aaaa’,然后是‘aaaaaaaa’。循环次数和str_repeat一致,但是中间生成了'aa','aaaa'两个无用字符串,而且,目标字符串越长,则垃圾越多。而且,循环中采用字符串拼接方式,效率也不高。

?

?

而str_repeat则没有多余的无用空间的分配和释放操作。