book cover

Solutions
(To Column 5 of
Programming Pearls)

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:

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
  */

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