There are a few basic concepts one has to get across if students are ever going to understand and work with computer languages. I’ll get to one of the most difficult in another story, but, first, an easy one.
Databases, indexed files, and the like, keep track of where everything is by using indexes, sort of like the index in a book. Keywords are stored separately from the actual data and stored with each keyword is a number; that number being the address of where the complete record is stored. Make sense? You want to find out something about “blogs” so, you look up the word “blog” in the index of a book which lists the numbers of the pages in the book where you will find information about blogs. Computers handle information pretty much the same way. I want the record for “Smith, John” who lives on “King Street” so the computer will look those terms up in its index and come up with the address of the memory location where the complete record that matches those two criteria resides.
Every location in computer memory has an address associated with it. A typical address might look like: 1A78C4DF. If you’ve been following these entries, you should recognize that as a hexadecimal number where each digit represents four bits of information. In other words, 1A78C4DF represents a group of 32 1’s and 0’s, and 32 bits can represent 4,294,967,296 integer numbers—which is why Windows computers based on 32-bit architecture can address a maximum of four Gigabytes of RAM (actually about 3.6 GB). Folks running computers with XP, for example, waste their money if they buy more than 4GB RAM because their machines simply can not address the excess storage.
The point of all this being: each 32-bit piece of information has a unique number associated with it so that the processor can find it when needed. (In reality it has an "offset" number rather than a fixed one.) Having said that: what is the fastest way to locate a number from a list where you know the end points (the lowest and highest numbers)? That’s what a computer has to do when it looks up data for you. It could start at the lowest address and work its way through the list one at a time: is it location 11111111? No? How about location 11111112? And so on. It can take a very long time to find a specific number (or address) using that method. Starting at the other end won’t help. Theoretically if you start at the lowest or highest number and work your way one at a time through the list you might have to actually look at every number in the list. If your list comprises the numbers 1 through 100 and you start at 1, if your target number is 100 you will have to look at 100 numbers to find it. There’s got to be a faster way—and there is.
I would ask a student to write a number from 1 to 100 on a piece of paper and then say I was going to tell her what the number is in seven guesses or less. All she had to do was answer “higher” or “lower” until I got the number. I started at 50. (Let’s assume all her answers were “lower” to make this description easier.) 50, 25, 12, 6, 3, 2, 1: yes. As you can probably tell, all I did was split the difference between the guess number and the closest known number in the direction (higher or lower) that the student told me to go. Let’s say I’m trying to find 36. Here’s how it would go: 50: lower; 25: higher; 37: lower; 31 higher; 34: higher; 35: higher ;36! Seven guesses maximum (less if I had picked 36 instead of 35 as the difference between 34 and 37).
This called a binary search (binary meaning two: you divide the difference between your guess number and the closest known number in the given direction by two.) Computers might be fast but when you compare seven guesses to find a number to potentially one hundred guesses out of a list with 100 items, a binary search comes out ahead almost every time—and computers usually have a lot more than 100 numbers to search when looking for information. A binary search will not always be the fastest way, but, if you do thousands of searches through thousands of numbers, overall, statistically, a binary search is the winner.
Students were usually delighted to discover this trick and I’d give them time to play with it between themselves. Like most tricks, it’s not really a trick at all: it’s applied logic. Data often has implied information associated with it and if you can figure out how to identify that implied information and apply it to your problem you’ve gone a long ways towards becoming a programmer. In this case, each number in our list has a relationship with our target number: It is the target number itself, or it is either higher or lower than it, and by exploiting that information we can make our search for it much quicker and more efficient.
By learning how to teach computers how to solve problems we are sometimes teaching ourselves how to solve our problems in other ways. It’s all in how you look at it.
No comments:
Post a Comment