|
|
|
4. The Napoleon Method: Divide and Conquer
|
| |
 |
|
|
|
|
 |
|
From:
Sams Teach Yourself Network Troubleshooting in 24 Hours
Author: Jonathan Feldman
Publisher: Sams
More Information
|
|
|
|
|
After Napoleon crowned himself Emperor, it's said that Beethoven changed
the dedication of his Eroica symphony, originally dedicated to Bonaparte,
to read "To the memory of a great hero." I'll try not to swell your
head to that extent, but the divide-and-conquer methods in this hour are going
to make you into a really great troubleshooter; it worked for Napoleon, and
it's going work for you.
Divide and conquer refers to the concept that the location of a given
problem can be found more easily by splitting the problem area into smaller,
manageable pieces. When you know that a problem is within a given area (say,
a certain physical network or within a certain PC or user configuration),
you can figure out which portion of that area it's in by splitting the area
into pieces.
NOTE
Nine times out of ten, only one network problem is at work at
any given time. Unless you've been struck by lightning recently, the odds
of you having more than one problem simultaneously are very slim. (That's
not to say that domino effects don't exist, though.)
Because
only one problem usually exists at a time, it should be easy to search for
(even in a large network). For example, let's say that I'm thinking of a
number from one to one million, and you want to guess what that number is.
If you proceed sequentially and guess every number, you could potentially
go through 999,999 numbers before getting it right. However, if you divide
the maximum number in half, and I tell you “higher” or “lower,”
and you keep dividing that result in half, you will take at most
only 23 guesses. That's quite an improvement. Don't believe me? Here's an
example:
Me: Okay, I'm thinking of a number from 1 to 1,000,000.
You: 500,000?
Me: No, lower.
You: 250,000?
Me: No, higher.
You: (pausing to calculate 250,000 / 2 + 250,000) 375,000?
Me: No, lower.
You: (getting mad at me for picking a number between 250,000 and
375,000) Let's see, there are 125,000 numbers between 250,000 and 375,000,
so the middle of that would be...312,500?
Me: No, lower.
You: (whipping out your calculator) 281,250?
Me: No, lower.
You: (getting good at this now) 265,625?
Me: (astonished) How'd you guess?
In truth, this would probably go on for a couple of more guesses, but you
get the idea. The range is initially a 1,000,000—a huge range. Then
it goes to 500,000, then 250,000, then 125,000, then 62,500, then 31,250,
then 15,625, then 7812, and so on. You can see that you lose zeros pretty
fast in only seven guesses; by the time you guess another seven times, you're
down to only about 60 possibilities. That should come as no surprise. You
can see in Figure 4.1 how fast dividing
an area in half cuts
down your search.
NOTE
If you want to impress your boss or look cool at a geek convention,
you can refer to this method of guessing as a binary search.
As a bonus, you can scrawl its mathematical representation onto the
overhead projector:
NOTE
Here, x is the maximum number in the sequence, and n
is the maximum number of guesses.
|
| |
|
|
|
|
|
|
|
Breaking News
|
|
One of the primary architects of OpenCable, Michael
Adams, explains the key concepts of this initiative in his book
OpenCable Architecture.
|
|
|
|
|
Just Published
|
|
 Residential
Broadband, Second Edition
by George Abe
Introduces the topics surrounding high-speed networks
to the home. It is written for anyone seeking a broad-based familiarity
with the issues of residential broadband (RBB) including product
developers, engineers, network designers, business people, professionals
in legal and regulatory positions, and industry analysts.
|
|
|
|
|
;){kind=link}