Just because computers become faster doesn't necessarily mean we should lose track of what are efficient algorithms. And being computationally efficient doesn't necessarily have to be at odds with memory efficiency either.
An inefficient sort routine such as the Bubble Sort may be fairly straightforward to understand. So in on Mars where sort doesn't exist, computers are incredibly fast, and people are reluctant to learn about best practices, algorithms, and CPAN tools (that's how they roll on Mars), one might be inclined to write his own sort routine. And in so doing, he may come up with the bubble sort, since it's so simple. He will have re-invented a O(n**2) sort implementation.
Now over on planet Vulcan, sort exists, as well as a good understanding of algorithms, and common best practices. And over on planet Vulcan, they're religious about learning the ins and outs of CPAN tools, as they are about reading the Perl POD. So they know that there's a better solution. The Merge Sort is a much better algorithm. It runs in O(n log n) time, and is stable.
Now since the population of Mars is relatively small, and computers are super duper fast there, nobody notices at first how inefficient their home brewed Bubble Sort is. The Vulcans have a higher population, and their computers are busy computing the question to the answer 42, so they value efficiency.
But then one day Earth sends a Mars rover up there, and it has a couple of specially engineered bunny rabbits on board who have no problem with cold, dry, oxygen-challenged worlds. All they care about is reproduction, and they're quite good at it. Martians take the rabbits as pets and give them all names. Population explosion: Given the Martians are such gracious individuals (have you ever met a rude one?) they can't bear to prevent their pets from doing what they enjoy most. And as loving as they are, they keep naming every one of the offspring. Computers are enlisted to help keep track of everything. But within a few years there are 8,000,000,000 bunny rabbits hopping around. What an opportunity! What an untapped market! Let's export them galactically!
So the Martians turn to their computer guru. "Please help us to catalog our rabbits so we can list them all on eBay." First they need to sort them into order by date of birth so that the ones nearing expiration get shipped first. Sadly their bubble sort takes 8,000,000,000**2 computations to find the order in which the rabbits should ship out. That's 64000000000000000000 computations! It doesn't matter how fast the computer is if the problem doesn't scale well. In the meantime rabbits consume all the food on Mars, the Martian population succumbs to the plague introduced upon it by the Old World (Earth), and the entire ecosystem collapses; all because an inefficient algorithm was chosen.
I have a nursery rhyme book that I read to my two year old. There's a poem in it that goes like this:
For want of a nail,
The shoe was lost;
For want of a shoe,
The horse was lost;
For want of a horse,
The rider was lost;
For want of a rider,
The battle was lost;
For want of a battle,
The kingdom was lost;
All for the want
Of a horseshoe nail.
Of course the Vulcans observed the whole thing, but it would have been illogical to go out of their way to prevent the collapse of a civilization that was so unwilling to learn to use efficient tools. They must have gotten Darwin's memo.
Note, the merge sort would have taken 180000000000 iterations before the first rabbit could sell, but the Vulcans had a copy of John Orwant's "Mastering Algorithms with Perl", and knew that Fibonacci Heap was a better alternative for choosing who goes first out of a huge group. That's the one the Vulcan god uses, but he doesn't reveal how he decides precedence. ;) At any rate, it would be illogical for Vulcans to keep rabbits as pets. But if they did, inserts would occur in O(1) (amortized), and extractions (selling a single rabbit) would take O(log n) at point of sale (22 units of computation). There's no need to actually do any sorting. At that point it just becomes imperative to find enough markets to ship them faster than they reproduce.
Dave
In reply to Re: Processor or Memory
by davido
in thread Reaped: Processor or Memory
by NodeReaper
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |