StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
11290417
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
2012-07-03T07:49:17.167
CreationDate
2012-07-02T08:46:43.273
FavoriteCount
0
LastActivityDate
2012-07-03T07:49:17.167
LastEditDate
2012-07-03T07:49:17.167
LastEditorUserId
1357650
OwnerUserId
1357650
ParentId
11281577
PostTypeId
2
Score
9
ViewCount
0
LastEditorDisplayName
text
Body
A much more tidy and elegant solution (which I've called Basic Solution) is as follows: Basic Solution <pre><code>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); } </code></pre> This is the beauty of recursion. The key to this solution uses recursion to incrementally build the length of the result. Parameter <code>total</code> does this (not including the NUL-terminator). When the recursion terminates, the result buffer is allocated once (including the NUL-terminator) and then we use the recursion unwinding to append each copy of <code>s</code>to the result. Basic Solution behaves as follows: <ol> <li>Returns a zero-length string for any number of repetitions of an empty string.</li> <li>Returns a zero-length string for zero or negative iterations of a non-empty string.</li> <li>Returns a non-zero-length string for a non-zero-positive number of repetitions on a non-empty string.</li> </ol> If you create a program based on the above functions, the following statements: <pre><code>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)); </code></pre> will produce the following output: <pre><code>Repeat "" 0 times: [] Repeat "" 3 times: [] Repeat "abcde" 0 times: [] Repeat "abcde" 1 times: [abcde] Repeat "abcde" 4 times: [abcdeabcdeabcdeabcde] </code></pre> EDIT : Optimised Solution follows. Read on if you're interested in optimisation techniques. <hr> All the other proposals here principally run in O(n^2) and allocate memory at every iteration. Even though Basic Solution is elegant, uses only a single <code>malloc()</code>, and takes only two statements, surprisingly Basic Solution also has a running time of O(n^2). This makes it very inefficient if string <code>s</code> is long and means that Basic Solution is no more efficient than any other proposal here. Optimised Solution The following is an optimal solution to this problem that actually runs in O(n): <pre><code>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); } </code></pre> As you can see, it now has three statements and uses one more parameter, <code>len</code>, to cache the length of <code>s</code>. It recursively uses <code>len</code> to compute the position within the result buffer where the <code>n</code>'th copy of <code>s</code> will be positioned, so allowing us to replace <code>strcat()</code> with <code>strcpy()</code> for each time <code>s</code> is added to the result. This gives an actual running time of O(n), not O(n^2). What's the difference between the Basic and Optimised solutions? All other solutions have used <code>strcat()</code> at least <code>n</code> times on string <code>s</code> to append <code>n</code> copies of <code>s</code> to the result. This is where the problem lies, because the implementation of <code>strcat()</code> hides an inefficiency. Internally, <code>strcat()</code> can be thought of as: <pre><code>strcat = strlen + strcpy </code></pre> i.e., when appending, you first have to find the end of the string you're appending to before you can do the append itself. This hidden overhead means that, in fact, creating <code>n</code> copies of a string requires <code>n</code> length checks and <code>n</code> physical copying operations. However, the real problem lies in that for each copy of <code>s</code> we append, our result gets longer. This means that each successive length check within <code>strcat()</code> on the result is also getting longer. If we now compare the two solutions using "number of times we have to scan or copy <code>s</code>" as our basis for comparison, we can see where the difference in the two solutions lies. For <code>n</code> copies of the string <code>s</code>, the Basic Solution performs as follows: <pre><code>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 | </code></pre> whereas the Optimised Solution performs like this: <pre><code>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 | </code></pre> As you can see from the table, the Basic Solution performs (n^2 + n)/2 scans of our string due to the built-in length check in <code>strcat()</code>, whereas the Optimised Solution always does (n + 1) scans. This is why the Basic Solution (and every other solution that relies on <code>strcat()</code>) performs in O(n^2), whereas the Optimised Solution performs in O(n). How does O(n) compare to O(n^2) in real terms? Running times make a huge difference when large strings are being used. As an example, let's take a string <code>s</code> of 1MB that we wish to create 1,000 copies of (== 1GB). If we have a 1GHz CPU that can scan or copy 1 byte/clock cycle, then 1,000 copies of <code>s</code> will be generated as follows: Note: n is taken from performance tables above, and represents a single scan of s. <pre><code>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) </code></pre> As you can see, the Optimised Solution, which completes nearly instantly, demolishes the Basic Solution which takes nearly 10 minutes to complete. However, if you think making string <code>s</code> smaller will help, this next result will horrify you. Again, on a 1GHz machine that processes 1 byte/clock cycle, we take <code>s</code> as 1KB (1 thousand times smaller), and make 1,000,000 copies (total == 1GB, same as before). This gives: <pre><code>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) </code></pre> This is a truly shocking difference. Optimised Solution performs in the same time as before as the total amount of data written is the same. However, Basic Solution stalls for over half a day building the result. This is the difference in running times between O(n) and O(n^2). 
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POExercise on recursion in C
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USaps2012
UserOwnerUserId
1. USaps2012
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.