《编程珠玑》英文PDF版-Jon Bentley著

需积分: 15 110 浏览量更新于2024-07-20 收藏 3.15MB PDF 举报

"《编程珠玑-618a 英文版pdf》是Jon Bentley所著的一本经典编程书籍，由AT&T Bell Laboratories出版。这本书是《Programming Pearls》系列的一部分，书中包含了作者作为一名程序员的见解和经验分享。内容涵盖电子计算机编程的多个方面，并附带索引，适合程序员阅读和学习。此版本为英文文字版，清晰度高，有目录，便于读者查阅。" 《More Programming Pearls: Confessions of a Coder》是Jon Bentley的著作，它是《Programming Pearls》系列的延续，深入探讨了软件开发中的问题解决和算法设计。这本书的核心理念是通过一系列精心挑选的问题，引导读者思考如何以更高效、更优雅的方式编写代码，提升编程技巧。书中的"珍珠"代表着编程中的智慧结晶，每个章节通常围绕一个具体问题展开，通过分析和讨论，展示解决问题的多种策略和方法。书中的内容不仅限于具体的编程语言或技术，而是关注通用的编程思维和原则，如代码的可读性、性能优化、数据结构的选择以及算法的应用。Jon Bentley强调代码质量的重要性，提倡编写简洁、可维护的程序，并且鼓励读者培养良好的编程习惯。书中的例子涵盖了各种实际问题，例如排序算法的比较、数据压缩技术、错误处理策略等。这些问题的探讨不仅让读者理解如何解决问题，还启发他们如何避免常见陷阱，提高编程效率。此外，书中还涉及软件工程的实践，如调试技巧、测试方法和项目管理。《More Programming Pearls》适合所有级别的程序员，无论是初学者还是经验丰富的专业人士，都能从中获益。通过阅读这本书，读者不仅可以学习到编程的深度知识，还能提升自己的问题解决能力和软件设计思维。书中的每个珍珠都是一次思维的锻炼，帮助读者在面对复杂编程挑战时，能够更加游刃有余。

10 MORE PROGRAMMING PEARLS

COLUMN 1

Here is the “pipeline profile” of the computation on a VAX-11/750:

lines words

chars

10717

59701

342233

57652 57651

304894

57652

57651

304894

57652

57651

304894

4731

9461

61830

4731

9461 61830

25 50

209

times

14.4u 2.3s 18r

11.9u 2.2s 15r

104.9u 7.5s 123r

24•5u 1•6s 27r

27.Ou 1.6s 31r

O.Ou 0.2s Or

tr -cs A-Za-z \0 12

tr A-Z a-z

sort

uniq -c

sort -rn

sed 25q

The left parts describe the data at each stage: the number of lines, words, and

characters. The right par^s describe the filters between the data stages: user,

system, and real times in seconds are followed by the command itself.

This profile provides much information of interest to programmers. The

pipeline is fast; 3.5 minutes of real time for 150 book pages is moving right

along. The first sort consumes 57 percent of the run time of the pipeline; that

finely tuned utility will be hard to speed up further. The second sort takes only

14 percent of the pipeline’s time, but is ripe for tuning.f The profile also

identifies a little bug lurking in the pipeline. UNIX gurus may enjoy finding

where the null line was introduced.

The profile also teaches us about the words in the document. There were

57651 total words, but only 4731 distinct words. After the first transliteration

program, there are 4.3 letters per word. The output showed that the most com

mon word was “the

” ；

it accounts for 6 percent of the words in the files. The six

most common words account for 18 percent of the words in the file. Special-

casing the 100 most common words in English might speed things up. Try

finding other interesting factoids in the counts.

Like many UNIX users, I had previously profiled pipelines by hand, using

the word count (wc) command to measure files and the time command to

measure processes. A “pipeline profiler” automates that task. It takes as input

the names of a pipeline and several input files, and produces the profile as out

put. Two hours of my time and fifty lines of code sufficed to build the profiler.

The next section elaborates on this topic.

1.4 Building Profilers

Building a real profiler is hard work. Peter Weinberger built the C line-

count profiler that produced the output we saw earlier; the project took him

several weeks of effort spread over several months. This section describes how a

simple version can be built more easily.

Dick Sites claimed that his friend “implemented statement counts one

t The second sort takes 25 percent of the run time of the first sort on just 8 percent of the number of

input lines — the numeric (-n) flag is expensive. When I profiled this pipeline on a single column,

the second sort was almost as expensive as the first; the profile is sensitive to the input data.

COLUMN 1

PROFILERS 11

i++) { <<<998>>>

<<<167>>>

weekend”. I found that pretty hard to believe, so I decided I，d try to build a

profiler for Awk, an unprofiled language that is described in Appendix 1. A

couple of hours later, my profiler produced this output when I ran the Awk ver

sion of Program P6:

BEGIN { <<<1>>>

n = 1000

x[0] = 2; xc = 1

print 2

for (i = 3; i <= n;

if (prime(i)) {

print i

}

exit

function prime(n, i ) { <<<998>>>

for (i=0; x[i]*x[i]<=n; i++) { <<<2801>>>

if (n % x[i] == 0) { <<<831>>>

return 0

}

{ «<167>>> }

x[xc++] = n

return 1

}

The number in angle brackets after a left curly brace tells how many times the

block was executed. Fortunately, the counts match those produced by the C

line counter.

My profiler consists of two five-line Awk programs. The first program reads

the Awk source program and writes a new program in which a distinct counter

is incremented at the start of each block and a new END action (see Appendix

1) writes all counts to a file at the end of execution. When the resulting pro

gram runs, it produces a file of counts. The second program reads those counts

and merges them back into the source text. The profiled program is about 25

percent slower than the original, and not all Awk programs are handled

correctly

一

I had to make one-line changes to profile several programs. But for

all its flaws, a couple of hours was a small investment to get a prototype profiler

up and running. Section 7.2 of The AWK Programming Language cited in Sec

tion 2.6 presents details on a similar Awk profiler.

Quick profilers are more commonly written than written about. Here are a

few examples:

In the August 1983 BYTE, Leas and Wintz describe a profiler implemented

as a 20-line program in 6800 assembly language.

Howard Trickey of Bell Labs implemented function counts in Lisp in an

hour by changing defun to increment a counter as each function is entered.

12 MORE PROGRAMMING PEARLS

COLUMN 1

In 1978，Rob Pike implemented a time profiler in 20 lines of Fortran. After

CALL PROFIL( 10), subsequent CPU time is charged to counter 10.

On these and many other systems it is possible to write a profiler in an evening.

The resulting profiler could easily save you more than an evening’s work the first

time you use it.

1.5 Principles

This column has only scratched the surface of profiling. I ，v e stuck to the

basics, and ignored exotic ways of collecting data (such as hardware monitors)

and exotic displays (such as animation systems). The message of the column is

equally basic:

Use a Profiler. Make this month Profiler Month. Please profile at least one

piece of code in the next few weeks, and encourage your buddies to do likewise.

Remember, a programmer never stands as tall as when stooping to help a small

program.

Build a Profiler. If you don’t have a profiler handy, fake it. Most systems

provide basic profiling operations. Programmers who had to read console lights

25 years ago can get the same information today from a graphics window on a

personal workstation. A little program is often sufficient to package a system’s

instrumentation features into a convenient tool.

1.6 Problems

1. Suppose the array ^[1..1000] is sprinkled with random real numbers. This

routine computes the minimum and maximum values:

Max

Min :=

X[1]

for I : = 2 to 1000 do

X[I] >

Max then Max

：= X[I]

X[I] <

Min then Min

：= X[I]

Mr. B. C. Dull observed that if an element is a new maximum, then it can

not be a minimum. He therefore rewrote the two comparisons as

if X[I] > Max then Max := X[I]

else if X[I] < Min then Min := X[I]

How many comparisons will this save, on the average? First guess the

answer, then implement and profile the program to find out. How was your

guess?

2. The following problems deal with computing prime numbers.

a. Programs PI through P6 squeezed two orders of magnitude out of the

run time. Can you wring any more performance out of this approach to

the problem?

b. Implement a simple Sieve of Eratosthenes for computing all primes less

than n. The primary data structure for the program is an array of n bits,

COLUMN 1

PROFILERS 13

all initially true. As each prime is discovered, all of its multiples in the

array are set to false. The next prime is the next true bit in the array.

c. What is the run time as a function of n of the sieve in part b? Find an

algorithm with running time of 0{n).

d. Given a very large integer (say, several hundred bits), how would you

test it for primality?

3. A simple statement-count profiler increments a counter at each statement.

Describe how to decrease memory and run time by making do with fewer

counters. (I once used a Pascal system in which profiling a program slowed

it down by a factor of 100; the line-count profiler described in this column

uses tricks like this to slow down a program by only a few percent.)

4. A simple procedure-time profiler estimates the time spent in each procedure

by observing the program counter at a regular interval (60 times a second on

my system). This information tells the time spent in each part of the pro

gram text, but it does not tell which procedures called the time hogs. Some

profilers give the cost of each function and its dynamic descendants. Show

how to gather more information from the runtime stack to allocate time

among callers and callees. Given this data, how can you display it in a use

ful form?

5. Precise numbers are useful for interpreting profiles of a program on a single

data set. When there is a lot of data, though, the volume of digits can hide

the message in the numbers. How would you display the profiles of a pro

gram or a pipeline on 100 different inputs? Consider especially graphical

displays of the data.

6. Program P6 in Section 1.4 is a correct program that is hard to prove correct.

What is the problem, and how can you solve it?

1.7 Further Reading

Don Knuth，s “Empirical Study of Fortran Programs，，appeared in volume 1

of Software —Practice and Experience in 1971 (pp. 105-133). Section 3 on

“dynamic statistics” discusses both line-count and procedure-time profilers, and

the statistics they were used to gather. Section 4 tunes seventeen critical inner

loops, for speedup factors ranging from 1.5 to 13.1. I have read this classic

paper at least once a year for the past decade, and it gets better every time. I

strongly recommend it.

c o lu m n 2

：

ASSOCIATIVE ARRAYS

Anthropologists say that language has a profound effect on world view.

That observation, usually known as Whorfs hypothesis, is often summarized as

“Man’s thought is shaped by his tongue.”

Like most programmers, my computing thought is shaped by my Algol-like

tongue. PL/1, C and Pascal look pretty much alike to programmers like me,

and it's not hard for us to translate such code into Cobol or Fortran. Our old,

comfortable thought patterns can be easily expressed in these languages.

But other languages challenge the way we think about computing. We are

amazed by Lispers as they work magic with their S-expressions and recursion,

by APL fans who model the universe as the outer product of a couple of long

vectors, and by Snobol programmers who seem to turn any problem into a big

string. We Algolish programmers may find it painful to study these foreign cul

tures, but the exposure usually yields insight.

This column is about a language feature outside the Algol heritage: associa

tive arrays. The arrays we know have numeric subscripts, while associative

arrays permit references like count V'cat'']. Such data structures are present in

languages such as Snobol and Rexx (an IBM command interpreter); they allow

complex algorithms to be expressed in simple programs. These arrays are close

enough to Algol to be understood quickly, yet novel enough to challenge our

thinking habits.

This column examines the associative arrays provided by the Awk language.

Most of Awk is from the Algol tradition, but its associative arrays and several

other features merit study. The next section introduces Awk’s associative arrays.

Subsequent sections describe two substantial programs that are cumbersome in

most Algol-like languages, yet can be elegantly expressed in Awk.

2.1 Associative Arrays in Awk

The Awk language is sketched in Appendix 1. We’ll review the language

briefly by studying a program to find suspicious entries in a file of names. Each

line in the program is a “pattern-action” pair. For each input line that matches

a pattern on the left, the action enclosed in brackets on the right is executed.

剩余203页未读，继续阅读

just-cyf

粉丝: 5
资源: 3

《编程珠玑》英文PDF版-Jon Bentley著

编程珠玑+第二版(Programming+Pearls,2nd+Edition)(英文版+中文版+源码打包)PDF高清.rar

编程珠玑第二版（中英文版电子书+源代码）

编程珠玑-英文版+中文版+source code

ASP.NET\ASP.NET 2.0编程珠玑--来自MVP 2.0编程珠玑--来自MVP的权威开发指南

编程珠玑-第2版-修订版

编程珠玑-第2版

编程珠玑-pdf

编程珠玑--算法

编程珠玑 -- swap section

编程珠玑-中文第二版

最新资源