- Recursion Versus Iteration
- A More Challenging Example: Rabbit Numbers
- Inception: The True Benefit of Recursion
- The Tower of Hanoi
- Other Aspects of Efficient Algorithms
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Other Aspects of Efficient Algorithms
So far I have scratched the surface of some of the attributes of the best algorithms: efficiency, brevity, best use of data, and above all not recalculating a value that has already been calculated. Entire books have been written on the subject.
But I will also mention one of my pet peeves. Wherever possible, an algorithm should be as streamline as possible—that is, as much as possible, you should try to treat every case the same way. You want to use special cases as little as possible.
Consider the following problem: suppose you want to write a function called pass_or_fail() that takes a single integer n and returns true n percent of the time. For example, pass_or_fail(55) should return true 55 percent of the time and false 45 percent of the time. The obvious solution is to get a random number in the range 1 to 100 and then see if that number is less than or equal to the test value:
bool pass_or_fail(int test_val) {
int p = rand() % 100; // p = 0 to 99
if (p == 0) // Special-case 0...
p = 100; // This is stupid.
return p <= test_val;
}
Assuming the only randomization function you have access to is the classic C/C++ rand() function, the most efficient way to get a random number from 0 to N-1 is use modular division (%) on N—in this case, 100. Alternatively, you could divide by RAND_MAX, the number of integers in the range returned by rand(), and then multiply by 100, but this is more work and therefore less efficient:
int p = (rand() / (double) RAND_MAX) * 100:
The problem, in either case, is that you get a number from 0 to 99 instead of 1 to 100. The worst possible solution is to special-case zero and flip it over to 100, as done earlier. A better way is to just add 1:
bool pass_or_fail(int test_val) {
int p = rand() % 100 + 1; // p = 1 to 100
return p <= test_val;
}
But even that’s a poor way of doing things. The question any good C or C++ programmer should ask is: Why do we need to use a greater-or-less-than comparison (<=) in the first place? By using a less-than comparison (<), this function becomes really simple indeed:
bool pass_or_fail(int test_val) {
return rand() % 100 < test_val;
}
The moral of the story? Don’t use special cases unless you have to. And in general, don’t do make the program do unnecessary work.