Sometimes Optimization Matters (Recursion vs Iterative OR "A 4 Billion Character String is REALLY Long")

Computers today are really fast. In fact, they’re fast enough that some people don’t bother to optimize a lot of code. Sometimes that’s okay – after all, premature optimization isn’t a positive thing and can see you spending a great deal of time in exchange for little or no gain. Other times, however, you know there’s going to be a difference of an order of magnitude or more on a computation intensive part of a system.

As an example, there is a coding challenge on CodeEval to find the character in a string at a specific location. You aren’t given the string ahead of time, just the first character and the pattern to use in order to build the string (up to a string length of 3,000,000,000).

I’ll summarize here since it’s pretty simple. The character set is 0, 1, and 2. The first character is 0. You build out the string by using the previous string as the first half of the new string and add one to each digit. This means that 0 => 01 => 0112 => 01121220 and so on.

You only want one character in the string (we’ll call it N). The rest, as far as you are concerned, is garbage.

The knee jerk reaction for a lot of people would be to build the string to the length that you need and just access the character directly. That might even be okay if your upper bound for length wasn’t 3 BILLION. Given that, however, you need a better way (I’ll show you why here in a little while).

If you take a minute to look at it, you’ll realize that, by following the pattern they’ve defined for the number, that you will always end up with a string that has a length of a power of 2 (1, 2, 4, 8, 16, and so on). That means that you can determine how long the shortest string of that pattern will be by taking x = Ceiling of log2(N) and then calculating 2^x.

That doesn’t help us much by itself, but with that information, the pattern, and the fact that we only need one character, it makes this problem a prime candidate for recursion.

Method 1 – Recursion

Recursion can be kind of a scary word for some people because initially it can be sort of difficult to wrap your brain around. However, given a little practice, the hardest parts of the exercise are structuring the problem in a way that you can use recursion and making sure that you actually write it properly (in fact, it took me a little while to get rid of a bug because I had a line of code in the wrong place).

I’ll link to the code here so I don’t have to walk through everything, but to put it succinctly, after calculating the needed string length, the recursive approach essentially keeps track of where the target character would be during each string transformation, uses that to calculate how many times the character would have to change (C) and then calculates our N = C % 3 (each character is essentially a one digit base 3 number, so we can get away with that).

It’s probably as close to doing the problem with pure math as you can get without actually having an equation. As a result, it’s quick. REALLY quick. Fast enough, in fact, that I had to measure runtime in ticks (according to MSDN documentation, it takes 10,000 ticks to make up a millisecond).

The chart below shows the runtime (in both ticks and milliseconds) of one calculation for each given string length (2^0 through 2^32) – not counting file I/O or output to screen (which the original project required). This is just the time from being handed the number to getting the answer to what N is.

Power of 2	Recursive Runtime (in Ticks)	Recursive Runtime (in Milliseconds)
0	4	0
1	10	0
2	4	0
3	4	0
4	5	0
5	5	0
6	5	0
7	4	0
8	5	0
9	5	0
10	4	0
11	5	0
12	4	0
13	5	0
14	5	0
15	5	0
16	5	0
17	5	0
18	5	0
19	5	0
20	5	0
21	5	0
22	6	0
23	6	0
24	6	0
25	6	0
26	6	0
27	32	0
28	6	0
29	6	0
30	6	0
31	7	0
32	7	0

Note that the 32 tick runtime for the 2^27 length string is an aberration (probably caused by time slicing in the operating system). Running it multiple times, every test case ran at 20 ticks or below (generally 10 ticks or less). The only reason it looks like a big difference is because ticks are really REALLY tiny.

So, to sum up the pros and cons for the recursive approach to this problem

Pros: Really fast. Takes up less memory because there’s no actual string being built.

Cons: More difficult to write and debug

Method 2 – Iterative (Don’t do it this way. Please)

Again, I’ll give you the code for this method.

This time, we’re actually building the string in order to find the character. There are a few problems with this.

First is that it’s SLOW. I initially tried doing it two different ways. The first way ran for over HALF AN HOUR trying to calculate the 2^32 length string before I stopped it. The way which is in the code linked above runs much faster because it uses String.Replace() but seems to use more memory.

Second, it takes up A LOT of memory because it’s actually building the string and keeping it in memory. That’s not a big deal when the string is small, but according to the formula here, the size of just the string at its maximum length is 512MB.

Below is the benchmark data for this approach using the same constraints (no file or screen I/O) and the same numbers as the recursive approach.

Power of 2	Iterative Runtime (in Ticks)	Iterative Runtime (in Milliseconds)
0	4	0
1	5	0
2	4	0
3	6	0
4	7	0
5	9	0
6	21	0
7	17	0
8	35	0
9	56	0
10	111	0
11	281	0
12	386	0
13	2011	0
14	6360	3
15	12657	6
16	12528	6
17	125246	61
18	57912	28
19	53481	26
20	101440	49
21	204253	99
22	400705	195
23	1250113	611
24	1778822	869
25	3158791	1544
26	6980949	3412
27	OME	OME
28	OME	OME
29	OME	OME
30	OME	OME
31	OME	OME
32	NA	NA

OME stands for Out Of Memory Exception. These test cases literally caused the program to exceed its allocated memory (it was compiled for “any processor” since NUnit’s test runner didn’t want to play nicely with forced x64 solutions).

The NA result at 2^32 reveals a special problem. In C#, a character at a specific index of a string is accessed by using stringName[int]. The catch is that 2^32 is larger than an Int (you need at least a Long if you want a number that big), so you’d need to compensate by doing a substring to chop off the first Int32.MaxValue and reducing the index by the same amount.

I did that in the first attempt at this problem, but since I found out it was going to throw memory exceptions, I decided that I’d refrain from re-implementing it for the sake of simplicity and more readable code.

As you can see, this approach is MUCH slower than the recursive one. In fact, the general trend is to roughly double the runtime for each larger string. This means that a string of length 2^32 would take roughly 384,000,000 ticks (38,400,000 times the length of time for the recursive solution assuming the recursive solution took 10 ticks).

This is, of course, assuming you made the string from scratch for every test case. You could get around that to an extent by storing the string and just building it out longer as needed. However, you’d still be eating up a lot of memory to store the string. At its longest, the string would be over 4 billion characters long.

That’s longer than War And Peace. This is why, sometimes, optimization really matters.

I’m not sure I really need to sum up the pros and cons for this approach, but

Pros: Stupidly easy to write

Cons: Slow and memory intensive.

That’s not to say that recursion is the right answer to every problem, because it isn’t. There are times, however, when the extra work in designing a more efficient algorithm in order to tackle a problem can really pay off.

Just some food for thought.

Current mood: thoughtful

Current music: Shawn Mullins – Lullaby