1.
When I write large programs,
I use long names (ten or twenty characters)
for my global variables.
This column uses short variable names such as
x, n and t.
In most software projects,
the shortest plausible names might be more like
elem, nelems and target.
I find the short names convenient for building scaffolding
and essential for mathematical proofs like that in Section 4.3.
Similar rules apply to mathematics:
the unfamiliar may want to hear that
``the square of the hypotenuse of a
right triangle is equal to the sum of the squares of
the two adjacent sides'',
but people working on the problem usually say
``a2 + b2 = c2''.
I've tried to stick close to
Kernighan and Ritchie's C
coding style,
but I put the first line of code with the opening
curly brace of a function
and delete other blank lines to save space
(a substantial percentage,
for the little functions in this book).
The binary search in Section 5.1 returns an integer
that is -1 if the value is not present,
and points to the value if it is present.
Steve McConnell
suggested that the search
should properly return two values:
a boolean telling whether it is present,
and an index that is used only if the boolean is true:
Listing 18.3 on page 402 of McConnell's
Code Complete
is a Pascal Insertion Sort that occupies one (large) page;
the code and comments are together 41 lines.
That style is appropriate for large software projects.
Section 11.1 of this book presents the same algorithm
in just five lines of code.
Few of the programs have error checking.
Some functions read data from files into arrays
of size MAX,
and scanf calls can easily overflow their buffers.
Array arguments that should be parameters
are instead global variables.
Throughout this book,
I've used shortcuts that are appropriate for
textbooks and scaffolding,
but not for large software projects.
As Kernighan and Pike observe in Section 1.1 of their
The Practice of Programming,
``clarity is often achieved through brevity''.
Even so,
most of my code avoids the incredibly dense style
illustrated in the C++ code in Section 14.3.
7.
For n=1000,
searching through the array in sorted order
required 351 nanoseconds per search,
while searching it in random order raised the
average cost to 418 nanoseconds
(about a twenty percent slowdown).
For n=106,
the experiment overflows even the L2 cache
and the slowdown is a factor of 2.7.
For the highly-tuned binary search in Section 8.3, though,
the ordered searches zipped right through
an n=1000-element table
in 125 nanoseconds each,
while the random searches required 266 nanoseconds,
a slowdown of over a factor of two.
Copyright © 1999
Lucent Technologies. All rights reserved.
Thu 9 Sep 1999
boolean BinarySearch(DataType TargetValue, int *TargetIndex)
/* precondition: Element[0] <= Element[1] <=
... <= Element[NumElements-1]
postcondition:
result == false =>
TargetValue not in Element[0..NumElements-1]
result == true =>
Element[*TargetIndex] == TargetValue
*/