• Choose a category
• All
• Classic-Fiction

By Root 5217 0

aspects. Sedgewick ("The analysis of Quicksort programs," Acta Informatica, Vol. 7) studies issues such as the space it requires and many other components of runtime for a variety of Quicksort variants. By concentrating on the key issues, we can ignore (for a while) other aspects of the program. One of my articles, "A Case Study in Applied Algorithm Design" (IEEE Computer, Vol. 17, No. 2) describes how I once faced the problem of evaluating the performance of a strip heuristic for finding an approximate travelling salesman tour through N points in the unit square. I estimated that a complete program for the task might take 100 lines of code. After a series of steps similar in spirit to what we have seen in this chapter, I used a dozen-line simulation to give much more accuracy (and after completing my little simulation, I found that Beardwood et al. ["The Shortest Path Through Many Points," Proc. Cambridge Philosophical Soc., Vol. 55] had re-expressed my simulation as a double integral, and thereby had solved the problem mathematically some two decades earlier).

Small pieces of code

I believe that computer programming is a practical skill, and I agree with Pólya that we "acquire any practical skill by imitation and practice." Programmers who long to write beautiful code should therefore read beautiful programs and imitate the techniques they learn as they write their own programs. I find that one of the most useful places to practice is on small code fragments, say of just one or two dozen lines. It was hard work but great fun preparing the second edition of Programming Pearls. I implemented every piece of code, and labored to pare each down to its essence. I hope that others enjoy reading the code as much as I enjoyed writing it.

Software systems

For specificity, I have described one tiny task in excruciating detail. I believe that the glory of these principles lies not in tiny code fragments, but rather in large programs and huge computer systems. Parnas ("Designing software for ease of extension and contraction," IEEE T. Software Engineering, Vol. 5, No. 2) offers techniques to whittle a system down to its essentials. For immediate applicability, don't forget the deep insight of Tom Duff: "Whenever possible, steal code."

The Most Beautiful Code I Never Wrote > Acknowledgments

3.6. Acknowledgments

I am grateful for the insightful comments of Dan Bentley, Brian Kernighan, Andy Oram, and David Weiss.

Finding Things > On Time

4. Finding Things

Tim Bray

Computers can compute, but that's not what people use them for, mostly. Mostly, computers store and retrieve information. Retrieve implies find, and in the time since the advent of the Web, search has become a dominant application for people using computers.

As data volumes continue to grow—both absolutely, and relative to the number of people or computers or anything, really—search becomes an increasingly large part of the life of the programmer as well. A few applications lack the need to locate the right morsel in some information store, but very few.

The subject of search is one of the largest in computer science, and thus I won't try to survey all of it or discuss the mechanics; in fact, I'll only consider one simple search technique in depth. Instead, I'll focus on the trade-offs that go into selecting search techniques, which can be subtle.

4.1. On Time

You really can't talk about search without talking about time. There are two different flavors of time that apply to problems of search. The first is the time it takes the search to run, which is experienced by the user who may well be staring at a message saying something like "Loading…". The second is the time invested by the programmer who builds the search function, and by the programmer's management and customers waiting to use the program.

Finding Things > Problem: Weblog Data

4.2. Problem: Weblog Data

Let's look at a sample problem to get a feel for how a search works in real life. I have a directory containing logfiles from my weblog (http://www.tbray.org/ongoing) from early