C++ for beginners, part 7 (Compromise)

never compromiseRorschach would have made a lousy programmer.

Don’t get me wrong, I’m more stubborn than I should be, so I see what he’s getting at. (If I had a nickel for every time I shouted ‘it’s the principle of the thing, damnit’, and slammed my fist on a table, I’d have some nickels). But in programming, compromise is a necessity.

Finding balance

Most often, the compromise comes down to time (number of operations needed) vs. space (memory). You can save time by using memory to do something useful. Or you can save memory but do things the slow way.

The other compromise that occurs is between readability and generality. You can have no-nonsense code which gets the job done at an unimpressive speed. Or you can have incredibly quick code by abstracting and generalizing the problem (usually with math).

13 lines of code on the left. That a stranger could read and make sense of. 5 lines of code on the right. Which may or may not be witchcraft.

Pic1

Sometimes the situation (available memory, how long you’re willing to let a program run) dictates the approach. Sometimes it’s a matter of personal taste, and depends on whether or not you’re into the whole brevity thing. And there’s not always a clear answer. Approach A can be better than B which can be better than C, but then under some circumstances, C could be better than A!

Polymelia

  • At first we used brute force. On the one hand, it’s a straightforward approach that’s easy to follow the logic of, and more likely to get the right answer. On the other hand, it was a burden on memory. And slow, because it checked every number (twice!) and built an entirely unnecessary vector.
  • Then we vectorized. On the one hand, there was a limit to the size of the vectors again. On the other hand, we saved time by dealing with only the numbers that were relevant. On the other hand, since we treated 3 and 5 as independent factors, we had to add a variable to account for multiples of 15.
  • Then we used math. On the one hand, that required solving a math problem. On the other hand, it just flat-out owns in processor time. On the other hand, it didn’t leave us with the most transparent code.
  • Then we sped things up by doing them in C++. How much of an improvement was it? This much:

Speed compare

Yeah. Definite improvement. But we also come back to ‘it’s difficult to define “better” code without a frame of reference’.

On the one hand, C++ is all round better than R (about 100 times faster). On the other hand, you don’t need to explicitly ask R to use 32-bits instead of 16-bits for super-large numbers. On the other hand, knowing enough about the problem and your system that you know what to ask C++ for and when, will make you a better programmer. Note: I misaligned columns in excel, so it says holly is the same speed as brute force in C++, which is ridiculous. It is 10 times faster!

But the purely mathematical approach takes the same time in both languages regardless of how large the input is. This is an example of a ‘constant time complexity’ algorithm. Regardless of input size, it always takes approximately the same time to compute an output. Neat. Brute force and holly golightly scale up with the input, so if you have 10 times the input, it takes 10 times as long. This is logarithmic time complexity. The solution we came up with for this problem is a rare beast though. It uses an insignificant amount of memory and gives an answer instantly. In reality though, compromises will need to be made.

This is why all that talk about binary representation and bytes and memory was important. If you know what you’re working with, beyond just the code you write, you get a better idea of the lay of the land and you’ll be on much surer footing when it comes to writing fast and efficient functions and programs. And you’ll be able to make more informed decisions about usage of time and memory. Plus, you’ll also be less freaked out when things don’t go according to plan.

Rorschach’s Journal. ¬†October 12th, 1985:

Badly optimized function in program this morning, wasteful constructions. This algorithm is afraid of me. I have seen it’s true time complexity. The types are extended gutters and the gutters are full of bits and when the integers finally overflow, all the answers will drown. The accumulated result of all their sums and multiplications will foam up about their vectors and all the coders and programmers will look up and shout “Save us!”…

…and I’ll look down, and whisper “no.”

Advertisements
This entry was posted in C++, Problem 1 and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s