Submitted:|| 23rd June, 2006
This article's more of a concept than anything else.
I want you to learn two fundamental concepts from this article...
What You Will Hopefully Learn:
1. That complicating a process can actually speed it up and sometimes make it simpler.
2. That looking at how things work in real life can help you speed up processes.
These two concepts are integral to software design, because software can be like real life in a lot of respects.
It requires a combination of actual common sense and virtual common sense. Read, and all shall become clear...
Let's look at a very simple example to illustrate this.
You have an application that lists hundreds of names. You also need to be able to find the ID number of any one of these names. We're going to assume that there is no 'find' or 'search' function for the List Object, and that there is no limit to the number of lines it can have. If you want to find something, you're gonna have to event-code the method.
Someone might suggest this:
"Build a list object, get it to auto-sort, and then fast-loop through the list to find the name you want."
So you try that, and watch your application freeze for a moment as you search for the name 'Zach' at the end of your 30,000-strong list of names.
It's a simple method for you, the coder. All you need to do is build a simple loop. But for the machine, it's not so simple. It's just had to plough through 29,996 names before it found the one you wanted!
What would you do in real life, looking up a name in the phonebook? If you were looking for a 'Mr Zach', you'd probably start from the back of the book and work inwards because you know that 'Z' is right at the end.
So with that in mind, you may suggest this:
"If a name starts with one of the first 13 letters of the alphabet, it should start looking at the top and work down. If it starts with any of the last 13 letters, it should start at the bottom and work up"
More complicated to code, but if you search for 'Zach', it'll find it instantly.
Another problem though. Suppose you search for 'Monty'. His name will be around the middle, so whether the system scans from Top-To-Bottom or Bottom-to-Top, it'll still be running like a sloth.
Again, what would you do? If you were looking for 'Monty' in the phonebook, you'd probably look down the strip on the edge of the book, find the section highlighted 'M' and look in there.
So *now* someone may suggest this:
"Build TWO lists. One contains the names, the other is an index. The index list contains 26 lines, one for each letter of the alphabet. Each line contains the number of names that start with that letter (so if we have 2,000 'A' names then the first line will read '2000').
"When we search for a name like 'Monty', we add up the sizes of A, B, C, D, E, F, G, H, I, J, K and L and start searching there. We also check how many 'M' names there are. If we only have 293 'M's in the directory, then we only search the 293 lines that come after the end of 'L'.
"When a new name is added, we check what letter it starts with and add 1 to the index for that number"
MUCH more complicated, but that will be a lot faster.
It's taken a lot of text showing that example, but do you see the two points considered so far?
1. Complicating a process can speed it up.
2. Common sense from real life can be applied to computing with very good results.
Best Article WriterRegistered