编程艺术精华：洞察与创新的软件设计指南

需积分: 10 157 浏览量更新于2024-07-22 收藏 1.23MB PDF 举报

《编程珠玑：第二版》(Programming Pearls, Second Edition) 是由 Jon Bentley 所著的一本计算机科学经典著作，由 Addison-Wesley, Inc. 出版于2000年，ISBN号为0-201-65788-0。这本书以其独特的魅力吸引着软件开发者的目光，它并不局限于工程学的严谨，而是深入探讨了洞察力和创新在编程中的核心价值。作者旨在通过一系列的小型案例研究、实际例子和有趣的练习，为学习者提供关于如何设计和创造程序，以及如何思考编程问题的全面指南。这本书的特点在于它强调设计的艺术性，被 Steve McConnell 赞誉为“小型设计的庆典”。书中包含五个部分，旨在帮助读者提升编程技能： 1. **初步篇(Preliminaries)**：这部分分为几个专栏： - **Cracking the Oyster**：探索问题的本质，引导读者如何发现隐藏在复杂问题背后的简单解决方案。 - **Aha! Algorithms (Sketch)**：提供直观的算法设计思路，鼓励读者从不同角度思考问题并寻找创新的算法。 - **Writing Correct Programs (Sketch)**：强调代码正确性的原则和实践，教授如何编写无误的程序。 - **A Small Matter of Programming (Sketch)**：聚焦于编程中的细节和技巧，提升编码效率和代码质量。 2. **性能篇(Performance)**：关注程序性能优化，通过"Back of the Envelope"这一栏目，介绍快速估算和直觉分析的方法。网站上提供了全书样本，供教师和学生在线查阅，适合课堂使用。浏览网站可以让你亲自体验到这本书的独特魅力。网站还更新了一些新的内容，包括书中的部分内容和教学资源链接，以便用户及时获取最新的学习材料和讨论话题。《编程珠玑：第二版》是一本深入浅出的编程指南，不仅适用于初学者提升编程技能，也适合经验丰富的开发者扩展视野和激发灵感。书中所蕴含的设计哲学和实践技巧，对于任何追求卓越编程的人来说，都是宝贵的财富。

Word Frequencies

(Illustrating Section 15.1 of

Programming Pearls)

Section 15.1 describes word frequencies and gives an example. Here are

some more examples, generated

by this program from the King James

Bible (789,616 words), the Iliad (153,210 words), and Programming Pearls

(79,525 words). This table shows the 40 most common words, and their

percentage in the document.

BIBLE % ILIAD % PEARLS %

the 7.86 the 6.25 the 5.64

and 4.88 and 4.23 of 2.76

of 4.35 of 3.64 a 2.43

to 1.69 to 2.15 to 2.18

And 1.61 his 1.62 and 2.01

that 1.57 he 1.60 in 1.96

in 1.54 in 1.42 is 1.36

shall 1.24 a 1.17 that 1.20

he 1.20 with 1.04 The 0.91

unto 1.13 that 0.94 for 0.83

I 1.10 you 0.91 by 0.67

his 1.06 for 0.89 it 0.57

a 1.01 him 0.84 this 0.56

for 0.90 I 0.83 with 0.51

they 0.87 as 0.79 an 0.50

be 0.84 was 0.77 program 0.48

is 0.84 they 0.66 on 0.48

with 0.75 on 0.64 be 0.47

not 0.74 from 0.64 are 0.47

all 0.66 but 0.58 as 0.45

thou 0.59 son 0.58 we 0.43

thy 0.56 had 0.58 at 0.39

was 0.56 not 0.56 can 0.39

it 0.56 their 0.56 time 0.38

which 0.54 it 0.56 I 0.36

my 0.52 is 0.50 was 0.35

LORD 0.50 will 0.49 you 0.33

their 0.49 have 0.48 code 0.33

have 0.48 all 0.47 from 0.28

will 0.47 by 0.47 or 0.26

from 0.45 them 0.46 its 0.26

ye 0.45 were 0.43 one 0.25

them 0.44 at 0.43 This 0.25

as 0.41 who 0.42 array 0.25

him 0.40 my 0.40 have 0.25

are 0.36 so 0.40 two 0.25

upon 0.34 your 0.38 each 0.25

were 0.34 when 0.37 first 0.24

by 0.32 be 0.36 search 0.24

when 0.31 upon 0.35 function 0.23

Phrases

(Section 15.2 of

Programming Pearls)

Words are the basic component of documents, and many

important problems can be solved by searching for words.

Sometimes, however, I search long strings (my documents, or

help files, or web pages, or even the entire web) for phrases,

such as ``substring searching'' or ``implicit data structures''.

How would you search through a large body of text to find ``a

phrase of several words''? If you had never seen the body of text

before, you would have no choice but to start at the beginning

and scan through the whole input; most algorithms texts

describe many approaches to this ``substring searching problem''.

Suppose, though, that you had a chance to preprocess the body of text before performing searches. You could make

a hash table (or search tree) to index every distinct word of the document, and store a list of every occurrence of

each word. Such an ``inverted index'' allows a program to look up a given word quickly. One can look up phrases

by intersecting the lists of the words they contain, but this is subtle to implement and potentially slow. (Some web

search engines do, however, take exactly this approach.)

We'll turn now to a powerful data structure and apply it to a small problem: given an input file of text, find the

longest duplicated substring of characters in it. For instance, the longest repeated string in ``Ask not what your

country can do for you, but what you can do for your country'' is `` can do for you'', with `` your country'' a close

second place. How would you write a program to solve this problem?

[Click for more examples of long repeated strings]

This problem is reminiscent of the anagram problem that we saw in Section 2.4. If the input string is stored in

c[0..n-1], then we could start by comparing every pair of substrings using pseudocode like this

maxlen = -1

for i = [0, n)

for j = (i, n)

if (thislen = comlen(&c[i], &c[j])) > maxlen

maxlen = thislen

maxi = i

maxj = j

The comlen function returns the length that its two parameter strings have in common, starting with their first

characters:

int comlen(char *p, char *q)

剩余282页未读，继续阅读

WangLanguager

粉丝: 1w+
资源: 300

编程艺术精华：洞察与创新的软件设计指南

编程珠玑.英文第二版-Programming.Pearls

[计算机科学经典著作].Programming.Pearls

.High.Performance.Parallelism.Pearls.0128021187

Programming pearls.pdf

Bentley J. More programming pearls

Programming Pearls

programming pearls

Programming pearls

Programming+Pearls+(COMPLETE)

Programming_Pearls_(COMPLETE)

最新资源