编程珠玑第二版：洞察与创新的编程艺术

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

《编程珠玑》(Programming Pearls, Second Edition) 是由Jon Bentley所著的一本经典编程著作，于2000年由Addison-Wesley出版社出版。本书的ISBN号码为0-201-65788-0，定价为$24.95，共239页。这本书的独特之处在于它并非传统的技术教程，而是将焦点放在软件开发中的洞察力和创新性上，即所谓的“编程珍珠”。这本书是一系列关于编程艺术的论文集，内容涵盖设计与编程实践，旨在引导读者不仅学习如何编写程序，更深入理解如何构思和创造高效的解决方案。作者通过丰富的案例研究、实际例子和有趣的练习，让读者在实践中掌握编程技巧和思考方式。《编程珠玑》的结构分为两个主要部分： 1. **Preliminaries**（预备篇）： - **Column1: Cracking the Oyster**：这部分可能探讨了如何深入问题，揭示其核心，类似于解构复杂问题的艺术。 - **Column2: Aha! Algorithms [Sketch]**：章节可能介绍了一些巧妙的算法设计思路和启发式方法，让读者体验到“啊哈！”时刻的惊喜。 - **Column4: Writing Correct Programs [Sketch]**：重点关注代码正确性和可维护性的原则，提供编写高质量代码的策略。 - **Column5: A Small Matter of Programming [Sketch]**：这可能是关于编程基本概念的精炼阐述，强调细节在编程中的重要性。 2. **Performance**（性能篇）： - **Column7: The Back of the Envelope**：这部分可能讨论如何快速估算或分析算法的性能，帮助读者做出高效决策。网站上还提供了书中的样本供读者自行探索，对教师而言，还有一些适合课堂使用的材料链接。Steve McConnell称赞这本书是“小规模设计的庆典”，可见其在强调设计精妙和小型示例中的价值。在这个网站上，你可以找到新内容更新以及来自书籍的详细目录，包括前言，概述了作者对于编程艺术的见解，以及每部分章节的主题。通过这些内容，读者可以提升自己的编程技艺，领略编程之美。

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页未读，继续阅读

djent

粉丝: 0
资源: 2

编程珠玑第二版：洞察与创新的编程艺术

编程珠玑第二版英文版 带源码

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

编程珠玑（中文版+英文版）

编程珠玑 英文版 第二版

Programming Pearls 编程珠玑 英文版 文字版

编程珠玑 编程珠玑 编程珠玑 编程

编程珠玑 续英文版

programming pearls 编程珠玑 英文第二版

编程珠玑 英文第二版，欢迎下载

编程珠玑英文原版 Programming Pearl

最新资源

编程珠玑第二版英文版带源码

编程珠玑英文版第二版

Programming Pearls 编程珠玑英文版文字版

编程珠玑编程珠玑编程珠玑编程

编程珠玑续英文版

programming pearls 编程珠玑英文第二版

编程珠玑英文第二版，欢迎下载