使用原型char * repeat(char * s,int n)实现一个函数,以便它创建并返回一个由n次重复的输入字符串组成的字符串.例如：如果输入为“Hello”且为3,则输出为“HelloHelloHello”.仅使用递归构造.
我的解决方案在我看来非常难看,我正在寻找更清洁的东西.这是我的代码：
char *repeat(char *s,int n) {
if(n==0) {
char *ris = malloc(1);
ris[0] = '\0';
return ris;
}
int a = strlen(s);
char *ris = malloc(n*a+1);
char *ris_pre = repeat(s,n-1);
strcpy(ris,ris_pre);
strcpy(ris+(n-1)*a,s);
free(ris_pre);
return ris;
}
解决方法
基本解决方案
char *internalRepeat(char *s,int n,size_t total)
{
return (n > 0)
? strcat(internalRepeat(s,n - 1,total + strlen(s)),s)
: strcpy(malloc(total + 1),"");
}
char *repeat(char *s,int n)
{
return internalRepeat(s,n,0);
}
这是递归之美.此解决方案的关键是使用递归来递增地构建结果的长度.参数total执行此操作(不包括NUL终止符).当递归终止时,结果缓冲区被分配一次(包括NUL终止符),然后我们使用递归展开来附加sto的每个副本结果.基本解决方案的行为如下：
>为任意数量的重复返回零长度字符串
空字符串.
>为非空的零或负迭代返回零长度字符串
串.
>返回非零正数的非零长度字符串
重复非空字符串.
如果基于以上函数创建程序,则以下语句：
printf("Repeat \"\" 0 times: [%s]\n",repeat("",0));
printf("Repeat \"\" 3 times: [%s]\n",3));
printf("Repeat \"abcde\" 0 times: [%s]\n",repeat("abcde",0));
printf("Repeat \"abcde\" 1 times: [%s]\n",1));
printf("Repeat \"abcde\" 4 times: [%s]\n",4));
将产生以下输出：
Repeat "" 0 times: [] Repeat "" 3 times: [] Repeat "abcde" 0 times: [] Repeat "abcde" 1 times: [abcde] Repeat "abcde" 4 times: [abcdeabcdeabcdeabcde]
编辑：优化解决方案如下.如果您对优化技术感兴趣,请继续阅读.
此处的所有其他提议主要在O(n ^ 2)中运行,并在每次迭代时分配内存.即使Basic Solution很优雅,只使用一个malloc(),只需要两个语句,但令人惊讶的是Basic Solution的运行时间也是O(n ^ 2).如果字符串s很长,这会使效率非常低,并且意味着基本解决方案不比此处的任何其他提议更有效.
优化的解决方案
以下是实际在O(n)中运行的此问题的最佳解决方案：
char *internalRepeat(char *s,size_t total,size_t len)
{
return (n > 0)
? strcpy(internalRepeat(s,total,len),s) + len
: strcpy(malloc(total + 1),int n)
{
int len = strlen(s);
return internalRepeat(s,n * len,len) - (n * len);
}
如您所见,它现在有三个语句,并使用另一个参数len来缓存s的长度.它递归地使用len来计算结果缓冲区中将定位s的第n个副本的位置,因此允许我们将strcat()替换为strcpy(),每次将s添加到结果中.这给出了O(n)的实际运行时间,而不是O(n ^ 2).
基本和优化解决方案之间有什么区别？
所有其他解决方案都在字符串s上使用strcat()至少n次来将n个s副本附加到结果中.这就是问题所在,因为strcat()的实现隐藏了低效率.在内部,strcat()可以被认为是：
strcat = strlen + strcpy
也就是说,在追加时,首先必须找到你要附加的字符串的结尾,然后再进行追加.这种隐藏的开销意味着,实际上,创建字符串的n个副本需要n个长度检查和n个物理复制操作.然而,真正的问题在于,对于我们附加的每个s副本,我们的结果会变得更长.这意味着结果中strcat()内的每个连续长度检查也会变得更长.如果我们现在使用“我们必须扫描或复制s的次数”比较两种解决方案作为比较的基础,我们可以看出两种解决方案的区别在哪里.
对于字符串s的n个副本,Basic Solution执行如下：
strlen's/iteration: 2 strcpy's/iteration: 1 Iteration | Init | 1 | 2 | 3 | 4 | ... | n | Total | ----------+------+---+---+---+---+-----+---+------------+ Scan "s" | 0 | 1 | 2 | 3 | 4 | ... | n | (n+1)(n/2) | Copy "s" | 0 | 1 | 1 | 1 | 1 | ... | 1 | n |
而优化解决方案的执行方式如下：
strlen's/iteration: 0 strcpy's/iteration: 1 Iteration | Init | 1 | 2 | 3 | 4 | ... | n | Total | ----------+------+---+---+---+---+-----+---+------------+ Scan "s" | 1 | 0 | 0 | 0 | 0 | ... | 0 | 1 | Copy "s" | 0 | 1 | 1 | 1 | 1 | ... | 1 | n |
从表中可以看出,由于strcat()中内置的长度检查,Basic Solution对我们的字符串执行(n ^ 2 n)/ 2次扫描,而Optimized Solution总是进行(n 1)次扫描.这就是基本解决方案(以及依赖于strcat()的所有其他解决方案)在O(n ^ 2)中执行的原因,而优化解决方案在O(n)中执行.
O(n)与O(n ^ 2)的实际比较如何？
使用大字符串时,运行时间会产生巨大差异.作为一个例子,让我们采用1MB的字符串,我们希望创建1,000份(== 1GB).如果我们有1GHz cpu可以扫描或复制1个字节/时钟周期,那么将生成1,000个s副本,如下所示：
注意：n取自上面的性能表,表示s的单次扫描.
Basic: (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
= (10^3 ^ 2) / 2 + (3 * 10^3) / 2
= (5 * 10^5) + (1.5 * 10^2)
= ~(5 * 10^5) (scans of "s")
= ~(5 * 10^5 * 10^6) (bytes scanned/copied)
= ~500 seconds (@1GHz,8 mins 20 secs).
Optimised: (n + 1) = 10^3 + 1
= ~10^3 (scans of "s")
= ~10^3 * 10^6 (bytes scanned/copied)
= 1 second (@1Ghz)
如您所见,优化解决方案几乎立即完成,拆除基本解决方案,需要将近10分钟才能完成.但是,如果你认为将字符串缩小会有所帮助,那么下一个结果会让你感到恐惧.同样,在处理1个字节/时钟周期的1GHz机器上,我们将s取为1KB(小1千倍),并制作1,000,000份(总数== 1GB,与之前相同).这给出了：
Basic: (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
= (10^6 ^ 2) / 2 + (3 * 10^6) / 2
= (5 * 10^11) + (1.5 * 10^5)
= ~(5 * 10^11) (scans of "s")
= ~(5 * 10^11 * 10^3) (bytes scanned/copied)
= ~50,000 seconds (@1GHz,833 mins)
= 13hrs,53mins,20 secs
Optimised: (n + 1) = 10^6 + 1
= ~10^6 (scans of "s")
= ~10^6 * 10^3 (bytes scanned/copied)
= 1 second (@1Ghz)
这是一个真正令人震惊的差异.优化的解决方案与之前同时执行,因为写入的数据总量相同.但是,基本解决方案停止了半天以上的结果.这是O(n)和O(n ^ 2)之间运行时间的差异.
