より整然としたエレガントなソリューション (これをBasic Solutionと呼んでいます) は次のとおりです。
基本的な解決策
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 ターミネーターは含みません)。再帰が終了すると、結果バッファーが 1 回 (NUL ターミネーターを含めて) 割り当てられ、再帰の巻き戻しを使用して、 の各コピーをs
結果に追加します。基本的なソリューションは次のように動作します。
- 空の文字列が何回繰り返されても、長さ 0 の文字列を返します。
- 空でない文字列の 0 回または負の繰り返しに対して、長さ 0 の文字列を返します。
- 空でない文字列のゼロ以外の正数の繰り返しに対して、長さがゼロでない文字列を返します。
上記の関数に基づいてプログラムを作成すると、次のステートメントが実行されます。
printf("Repeat \"\" 0 times: [%s]\n", repeat("", 0));
printf("Repeat \"\" 3 times: [%s]\n", repeat("", 3));
printf("Repeat \"abcde\" 0 times: [%s]\n", repeat("abcde", 0));
printf("Repeat \"abcde\" 1 times: [%s]\n", repeat("abcde", 1));
printf("Repeat \"abcde\" 4 times: [%s]\n", repeat("abcde", 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()
の のみを使用し、2 つのステートメントしか必要としませんが、驚くべきことにBasic Solution の実行時間も O( n^2 )です。文字列が長い場合、これは非常に非効率的でs
あり、基本的な解決策はここでの他のどの提案よりも効率的ではないことを意味します.
最適化されたソリューション
以下は、実際にO( n )で実行されるこの問題の最適な解決策です。
char *internalRepeat(char *s, int n, size_t total, size_t len)
{
return (n > 0)
? strcpy(internalRepeat(s, n - 1, total, len), s) + len
: strcpy(malloc(total + 1), "");
}
char *repeat(char *s, int n)
{
int len = strlen(s);
return internalRepeat(s, n, n * len, len) - (n * len);
}
ご覧のとおり、3 つのステートメントがあり、もう 1 つのパラメーター を使用しlen
て の長さをキャッシュしていs
ます。の' 番目のコピーが配置されるlen
結果バッファー内の位置を計算するために再帰的に使用されるため、結果に追加されるたびにforに置き換えることができます。これにより、 O( n^2 )ではなく、O( n ) の実際の実行時間が得られます。n
s
strcat()
strcpy()
s
基本ソリューションと最適化ソリューションの違いは何ですか?
他のすべてのソリューションでは、結果にコピーを追加するために文字列をstrcat()
少なくとも 1n
回使用しています。の実装は非効率性を隠しているため、ここに問題があります。内部的には、次のように考えることができます。s
n
s
strcat()
strcat()
strcat = strlen + strcpy
つまり、追加するときは、追加自体を行う前に、まず追加先の文字列の末尾を見つける必要があります。この隠れたオーバーヘッドは、実際、n
文字列のコピーを作成するには、n
長さのチェックとn
物理的なコピー操作が必要であることを意味します。ただし、本当の問題は、追加するコピーごとs
に、結果が長くなることです。これはstrcat()
、結果内の連続する各長さチェックも長くなっていることを意味します。「スキャンまたはコピーしなければならない回数s
」を比較基準として 2 つのソリューションを比較すると、2 つのソリューションの違いがどこにあるのかがわかります。
n
文字列 のコピーの場合s
、基本的なソリューションは次のように実行されます。
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 |
表からわかるように、基本的なソリューションは、組み込みの長さチェックインにより、文字列の( n^2 + n)/2 回strcat()
のスキャンを実行しますが、最適化されたソリューションは常に(n + 1)のスキャンを実行します。これが、基本的なソリューション (および に依存する他のすべてのソリューションstrcat()
) がO(n^2)で実行されるのに対し、最適化されたソリューションはO(n)で実行される理由です。
O( n ) と O( n^2 ) を比較すると、実数はどうなりますか?
大きな文字列が使用されている場合、実行時間は大きな違いになります。s
例として、 1,000 個のコピー (== 1GB) を作成したい 1MBの文字列を考えてみましょう。1 バイト/クロック サイクルでスキャンまたはコピーできる 1 GHz の CPU がある場合、次のように のコピーが 1,000 個生成され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 分かかる基本的なソリューションを解体します。ただし、文字列をs
小さくすることが役立つと考える場合、次の結果は恐ろしいことです。ここでも、1 バイト/クロック サイクルを処理する 1 GHz マシンでは、s
1 KB (1000 分の 1) として、1,000,000 のコピーを作成します (合計 == 1 GB、前と同じ)。これは与える:
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)
これは本当に衝撃的な違いです。書き込まれたデータの合計量が同じであるため、Optimized Solution は以前と同じ時間で実行されます。ただし、基本的なソリューションは、結果を構築するのに半日以上かかります。これは、O( n ) と O( n^2 )の実行時間の差です。