今天在翻看php源码时, 研究了一下str_repeat的实现. 算法很有意思, 一般人的思路都是字符串拼接, 重复n次，就拼接n次, 时间复杂度为O(n). 但作者的思路很有意思, 把时间复杂度降到了log2^n+1.
上代码:
PHP_FUNCTION(str_repeat) { zend_string *input_str; /* Input string */ zend_long mult; /* Multiplier */ zend_string *result; /* Resulting string */ size_t result_len; /* Length of the resulting string */ if (zend_parse_parameters(ZEND_NUM_ARGS(), "Sl", &input_str, &mult) == FAILURE) { return; } if (mult < 0) { php_error_docref(NULL, E_WARNING, "Second argument has to be greater than or equal to 0"); return; } /* Don't waste our time if it's empty */ /* ... or if the multiplier is zero */ if (ZSTR_LEN(input_str) == 0 || mult == 0) RETURN_EMPTY_STRING(); /* Initialize the result string */ result = zend_string_safe_alloc(ZSTR_LEN(input_str), mult, 0, 0); result_len = ZSTR_LEN(input_str) * mult; /* Heavy optimization for situations where input string is 1 byte long */ if (ZSTR_LEN(input_str) == 1) { memset(ZSTR_VAL(result), *ZSTR_VAL(input_str), mult); } else { char *s, *e, *ee; ptrdiff_t l=0; memcpy(ZSTR_VAL(result), ZSTR_VAL(input_str), ZSTR_LEN(input_str)); s = ZSTR_VAL(result); //猜测这里的变量名为start e = ZSTR_VAL(result) + ZSTR_LEN(input_str); //这里应该是end ee = ZSTR_VAL(result) + result_len; //这里应该是end ending, 最后的结尾 //重点看这里, 整个算法的核心 while (e<ee) { //判断剩余内存的大小是否大于已经复制的内存大小, 取小者 l = (e-s) < (ee-e) ? (e-s) : (ee-e); memmove(e, s, l); e += l; } } ZSTR_VAL(result)[result_len] = '\0'; RETURN_NEW_STR(result); }内存图:
第一次循环: 因为e-s < ee-e, 所以l取e-s, 也就是1
第二次循环: 因为e-s < ee-e, 所以l取e-s, 也就是2
第三次循环: 因为e-s > ee-e, 所以l取ee-e, 也就是2
第四次循环: l=0
