《Design of Computer Programs》学习笔记（2 - 1）Back of the Envelope - Lesson 2

Back of the Envelope

envelope n.信封（金山词霸）

Lesson 2

视频链接：
Lesson 2 - Udacity

1. 练习：Zebra Puzzle

zebra n.斑马

puzzle n.难题

Zebra Puzzle - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

napkin n.餐巾纸

profit n.利润 vi.获利

porous adj.能渗透的；易穿过的

cliche n.陈词滥调

calculation n.计算；估计；深思熟虑

virtue n.美德；德行；长处

methodology n.方法学；方法论

brute n.残忍的；无理性的

a brute force solution 蛮力解（来自于百度翻译）

inhabitant n.居民，住户；动物

nationality n.国籍；国家；部落

notion n.概念，观念

assignment n.分配；任命；委派

spaniard n.西班牙人

generic adj.属性的；一般的

subjective adj.主观的；个人的

plausible adj.貌似真实的；貌似有理的

mutually adv.互相地

exclusive adj.专用的；高级的；排外的；单独地

本段视频的核心部分的，我的翻译

这是一个有价值的技能。在真实的生活中，可以做快速的、脏的估计，对计算机程序员来说，特别有用。它允许程序员，有一个偷懒的重要的长处。它允许我们，也就是，我们将可以提出我们能够想出的最简单的设计，在一个信封背面确认，那个设计，对于我们尽力去做的事情，是足够高效的，然后我们可以停止。然后，我们就可以停止了。我们不必尝试使它更复杂。

这整个课程是关于管理复杂度，管理复杂度的最重要的方式之一是，忽略完整性，仅仅只搞最简单的解决方案。如果我们可以这样做，然后我们就会朝向更好的设计。这个课程，我们将会学习如何那样做，我们将会学习如何估计，你何时是足够高效的，我们将学习何时停止，并且我们将学习如何使程序更高效。

我将以一个广为人知的Zebra Puzzle难题开始。这里有一个说明书。我们将尝试解决这个难题(address this puzzle 解决这个难题。百度翻译)，查看我们是否可以想出一个程序、解决它，并且，探索我们如何提出那个解决方案的方法论，还有，决定足够好的解决方案的过程，1个蛮力解是否可以起作用。

你可以阅读这个puzzle的说明书。现在，我们开始分析它。第1个概念是房子houses。我们被告知，有5个房子houses。并且，然后，这里有这些房子的住户的财产特性(properties n.特性；财产；所有权；房地产)和房子自身的财产特性。所以，这里有国籍、房子的颜色、它们拥有(房子、还是住户？)的宠物，他们喝的饮料，他们抽的烟。并且，然后，除了properties之外，对于房子，这里有一个properties的分配(assignment)的概念。没关系，无所谓，你可以考虑那个。你可以考虑它as像是，分配房子号码2红颜色，或者考虑它作为as分配红色给房子号码2。然后，有1个位置的概念，位置1到5，提到第1个房子的想法、中间的房子、相邻的、紧接的右边的。

我认为那覆盖了出现在说明书中的绝大部分。让我们回到它，检查它是否起作用。所以我正在看大量的概念，我们已经覆盖到的：5个房子、英国人、红房子、西班牙人、狗。现在，有少量的单词，我们没有覆盖，比如“住进去”、“拥有”这些东西(things like lives in and owns the)。我们在一般意义上覆盖了它们，就是说，这是一个从英国人到1个房子的分配，狗到1个房子的分配，但是，问题是，我们是否需要区分不同类型的分配？

所以，问题是，我们是否漏掉了，附着了1个说明的1个property名称的概念？

所以，例如，property name会是国籍和the description is lived in。我们是否需要像那样命名它们，或者，我们是否仅仅需要1个property组的概念，也就是说，这里有这些英国人、西班牙人、挪威人、日本人、乌克兰人和他们5个一起的properties，但是我们不需要他们的名字，或者，我们是否可以无视这个组的概念(this notion of grouping altogether)？这是有点主观的——1个好的设计选择是什么样的？——但是，告诉我，这3个种，你认为哪个是貌似有理的、或者合理的设计选择，然后检查所有提供的。

概念清单

■ property name / description ■ property group □ ignore group

我的答案是，定义property names，将会是1个好的选择。它可能会帮助我们理解，在这个程序的定义中，发生了什么。定义没有名字的组(groups without groups)，也将是好的(选择)。无视groups，我认为将不会工作、起作用，并且这里有1个问题。我们必须知道，如果red被分配给房子号码2，然后，blue不能被分配给房子号码2，但是orange juice可以被分配给房子号码2。所以，properties放进1个组group中的想法，是互相地、单独地，properties在组之外不是(So there’s this idea that properties within a group are mutually exclusive and properties outside of the group are not.)。在某种意义上，我们需要表现那个。

Zebra Puzzle 的说明

Zebra Puzzle - 维基百科

1 There are five houses.
1 有5个房子。
2 The Englishman lives in the red house.
2 英国人住在红房子里。
3 The Spaniard owns the dog.
3 西班牙人有狗。
4 Coffee is drunk in the green house.
4 绿房子里，喝咖啡。
5 The Ukrainian drinks tea.
5 乌克兰人喝茶
6 The green house is immediately(立即；直接地；紧接地) to the right of the ivory(象牙色的) house.
6 绿房子紧挨着象牙色房子的右边。
7 The Old Gold smoker owns snails(慢性子；蜗牛).
7 古金色的烟民性子慢。
8 Kools are smoked in the yellow house.
8 黄色房子里在吸Kools。
9 Milk is drunk in the middle house.
9 中间的房子里，在喝牛奶。
10 The Norwegian lives in the first house.
10 挪威人住在第1个房子里。
11 The man who smokes Chesterfields(长沙发) lives in the house next to the man with the fox.
11 抽长沙发烟的人，住在带着狐狸的人的房子旁边。
12 Kools are smoked in a house next to the house where the horse is kept.
12 吸Kools的房子，挨着养马的房子。
13 The Lucky Strike(lucky strike 好彩，鸿运当头) smoker drinks orange juice.
13 好运烟民喝橘子汁儿。
14 The Japanese smokes Parliaments.
14 日本人抽议会(Parliaments)烟。
15 The Norwegian lives next to the blue house.
15 挪威人住在蓝色房子旁边。
Who drinks water? Who owns the zebra?
谁喝水？谁拥有斑马zebra？
Each house is painted a different color, and their inhabitants(居民；住户) are of different nationalities, own different pets, drink different beverages(饮料) and smoke different brands of American cigarettes.
每个房子被涂成一个不同的颜色，并且它们的住户是不同国籍的，拥有不同的宠物，喝不同的饮料，抽不同品牌的美国烟。

2. 练习：Wheres The Spaniard

Wheres The Spaniard - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

crux n.核心；关键；症结

deduce vt.推断，推论

deduction n.推理；(推理所得出的)结论

本段视频的核心部分的，我的翻译

整个问题的核心是进行分配。有2种方式做这件事情。我们可以推理，什么分配必须是真的(what assignment must be true)——它必须是这种情况，英国人在1个确定的房子里。或者我们可以仅仅尝试不同的可能性——尝试把英国人放进房子1，然后房子2，然后房子3，然后看看哪个起作用。你必须很聪明，计算出、解决、想出，怎样做这些推理，并且，我不想尝试变得那么聪明。我想看看，通过仅仅尝试所有的可能性，如果我能得到，让计算机做这件事，所以我不用这样做。所以，让我们达到那件事，并且，让我们说，我们将尝试所有的可能性。

并且，所以，首先我们把英国人放进房子1，并且，稍后，我们将尝试把他放进房子2、3、4、5。现在，西班牙人怎么样？如果英国人在房子1，对于西班牙人，我们应该尝试什么可能性？给我你最好的回答：

□ 1,2,3,4,5 □ 1 □ 2 ■ 2,3,4,5

3. 练习：Counting Assignments

Counting Assignments - Design of Computer Programs - YouTube

本段视频的核心部分的，我的翻译

在5个properties的1个class里面，这个class必须覆盖5个房子，但是是以任何顺序。我们可以以多少种方式做那种分配？换句话说，这里有5种properties，在1个property group里面，并且，这里有1个可能的分配。

有多少种分配这些properties的不同分配方式？并且，把它们和房子匹配起来？

□ 5 □ 5的平方 = 25 □ 2的5次方 = 32 ■ 5! = 120

我的理解：
第1个房子有5种选择，第1个房子放好了颜色之后，第2个房子就只有4种选择了，以此类推。分配方式公有5 x 4 x 3 x 2 x 1 = 120种。

4. 练习：Multiple Properties

Multiple Properties - Design of Computer Programs - YouTube

本段视频的核心部分的，我的翻译

但是，我们不是只有1个property class；我们有5个property classes。我们有国籍、宠物、等等。并且，所以，如果我们想创建所有不同的方式，将所有的5种properties分配给5个房子，所以，每1个房子将会有1个颜色、1个国籍、1个宠物，等等。在进行分配的每1种可能的方式中，数量是多少？

□ 5 X 5! □ (5!)的平方 ■ (5!)的5次方 □ 5!!

我的理解：对于5个房子，每1种property的可能的方式都是5!，现在有5种properties，所以，共有5!的5次方。

5. 练习：Back Of The Envelope

Back Of The Envelope - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

approximately adv.近似地，大约

本段视频的核心部分的，我的翻译

(5!)的5次方，大约是多少？

□ 1 million ■ 20 billion □ 5 trillion

Peter的估算方法：
5!是120。让我们对120取整到100。100的5次方等于100,0000,0000，也就是10billion。并且，我们要做取整的逆向操作，可能是20billion的某个位置。实际算出的结果是24.9billion，所以，那不是个坏的估计。

6. 练习：Leaving Happy Valley

Leaving Happy Valley - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

infeasible adj.不可实行的

brute force approach 蛮力计算法

contour
n.外形，轮廓；概要
adj.显示轮廓的；

peak n.最高点；尖端

wilderness n.荒野；令人困惑的东西

in terms of 根据；用…的话；就…而言

concrete n.具体的，实际的

deep down 在内心深处

somehow 以某种方式，用某种方法

proof n.证明；检验

be up to 胜任，从事于

simultaneously adv.同时地；一齐

go through 通过；检查；完成

本段视频的核心部分的，我的翻译

我们现在在这个range里面，我们可能可以完成，但是我们不确定。我们的计算机每秒能够做大约10亿的指令，或者，在1个好的秒上面——那就是，它们没有浪费这1秒，页面错误或者cache miss。如果答案已经转变成在millions里面，我们可以说，“好极了，我们已经完成了。”如果转变成在trillions里面，我们会说，“这完全是不可行的。我们需要1个更好的解决方案。”但是，如果它在billions中间的某个地方，然后我们不是很确定。我们最好尝试，重新定义这个结果，一点一点地，来告知，这个蛮力解将是否可以起作用。

并且，根据执行时间，像1个轮廓图一样，考虑这个解决方案的空间。并且，在valley的这里的内心深处，只有millions条指令需要，去完成这个答案，然后我们真的开心，因为我们知道那会运行地非常快。并且，在happy valley之外，有这些高的尖端点，我们有trillions条计算需要，并且，这里，我们将会伤心。如果我们困在外面这些域里面，我们将必须以某种方式，找到1个路径进入，因为我们不能仅仅直接上、计算，当我们在外面trillions时。在中间这里，我们需要billions条指令，去完成我们的计算，然后我们不是很确定。可能我们在这里很开心，并且我们可以待在这个域里面。可能我们想找到我们的路径，通过令人困惑的背后，进入happy valley。这取决于问题。并且我们将尝试，根据这个空间，看待问题，尝试找到我们的路径back进入，但是知道合适停止，当我们已经足够接近的时候。

现在，让我们保持思考，进行一个分配，意味着什么。关于它，尝试更具体些。如果我们想分配red给房子号码1，让我们想想，我们能够以哪些方式实现。这里有1种可能，我们可以说，我们将有1个关于房子的数组、排列(an array of houses)。我们取得数1，并且，我们把red增加到它的properties集合上。那意味着，每1个房子被表示为1个集合(set)。这里有另一个可能性，我们取得数1，我们设置它的颜色属性property等于red。这里每1个房子将必须被表示为1个用户定义的custom class(子类？)，有着颜色和国籍等等属性(properties)。这里有第3个可能性。我们有1个变量，叫做red，我们仅仅分配那个数为1。所以，这里，我们把属性properties分配给房子houses，并且，在这个里面，我们把houses分配给了属性properties。

现在，我想要你检查所有的方法，你认为会是合理的设计，用于实现分配。

■ house[1], add('red') set() 集合 ■ house[1], color = 'red' House() 子类 ■ red = 1

我的想法：
用第2个答案，类来管理属性。

Peter的答案：
3个都可以，但是最好用第3个，因为够简单。所以我将go with那个，直到我能证明那个简单的，不起作用，并且，我们将go to更复杂的一些东西。

现在，在这个方法中，我们命名了properties。我们讨论了，你是否必须做那(指最简单的那个)的可能性。这里(最简单的red = 1)，我们没有命名它们，并且，所以，它会胜任作为程序员、去管理属性组(the groups of properties)。这里有1种方式，我可以做它。

我可以同时地分配这5个属性(properties)，这5个属性，在5个房子的颜色的相同的组中。
(red, green, ivory, yellow, blue) = [1, 2, 3, 4, 5]当然，这只会是1种可能的分配。在我尝试了这个之后，我将必须尝试另一个分配——可能是[1, 3, 2, 4, 5]——并且，我将必须检查所有的可能性。你能想出那样做的1个好的方式吗？什么声明(statement 声明；陈述)或者其他的实现，你可以提出来，以使得这5种属性properties、检查所有的可能的房子的组合？

7. 练习：Ordering Houses

对房子进行排序
Ordering Houses - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

state vt.陈述，声明；规定

permutation n.排列，序列

本段视频的核心部分的，我的翻译

这里有个解决办法。

首先，我们将定义这些房子。say这里有5个房子。在问题中，数1被声明。
然后我们会说，orderings是这些房子的可能的顺序的一些集合，所以[1, 2, 3, 4, 5]将会是orderings的1个元素，[2, 1, 3, 4, 5]将会是另一个元素，等等。
并且，然后，我们仅仅使用1个for声明，以在property group中，迭代这5个变量，through所有可能的orderings，并且然后放进这里我们的代码。

现在，问题是，函数F给了我们所有的orderings，函数F是什么？是排列函数(permutation functions)、组合函数(combination functions)、阶乘函数(factorial functions)、或者其他什么？

permutation functions 这个 combination functions factorial functions else

Peter的答案：
permutation functions。那个所有可能的orderings的定义，被称为permutations。

8. 练习：Length Of Orderings

Length Of Orderings - Design of Computer Programs - YouTube

本段视频的核心部分的，我的翻译

结果是，Python有一个permutation函数在itertools模组中，所以你可以import那个，或者你可以自己写一个。如果你做了那个，orderings的长度会是什么？

Peter的答案：
答案是120，或者5!。

9. 练习：Estimating Runtime

Estimating Runtime - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

arrange vt.整理；把…分类

constraint n.限制；约束

check out 获得证明；得到证实

本段视频的核心部分的，我的翻译

补充：permutations()函数的用法。

现在，假设我们整理我们的程序像这样。

import itertools houses = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) for (red, green, ivory, yellow, blue) in orderings: for (Englishman, Spaniard, Ukrianian, Japanese, Norwegian) in orderings: for (dog, snails, fox, horse, ZEBRE) in orderings: for (coffee, tea, milk, oj, WATER) in orderings: for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in orderings: # constraints go here # 1 sec # 1 min # 1 hour is right # 1 day

我们设置了houses，我们有所有120中可能的orderings的1个列表，并且，然后，我们在4个property group中，迭代5个properties中的每1个，through all those orderings。并且，所有，现在，5级嵌套深入我们的代码，我们已经得到了所有25种properties的1个分配。它们中的每1个都被分配给这些房子的1个，并且，现在，我们可以检查约束，比如，英国人住在red house里面，西班牙人拥有狗，等等。那些全都可以go there。如果我们发现有些事情得到证实，我们可以仅仅报告，我们得到了1个答案。现在，我想要你回到你的信封背面，并且，告诉我，如果我们以这种方式写这个程序，并且，用所有这些约束填充这个代码，并且运行它，你认为，它大概会花多久，找到1个解决办法？大约1秒、1分钟、1个小时、还是1天？

10. 练习：Red Englishman

Red Englishman - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

gigahertz n.兆赫兹

fairly adv.相当地；完全；清楚地

typical adj.典型的；代表性的

ridiculous adj.荒唐的，愚蠢的

all the way 一路上，一直，完全；

definitely adv.明确地；确切地；肯定地

somehow adv.以某种方式，用某种方法

figure out 计算出；解决；想出

aside adv.在旁边；旁白；离题话

be sort of 有点

identically adv.相等地，同一地

turn out 结果是；关掉；制造

identical 同一的；相同的

differ by 与…相差

本段视频的核心部分的，我的翻译

(5!)的5次方，是240亿(24billion)。并且，如果我们假设我们有1个2.4GHz的计算机，完全具有代表性，然后如果，这全部可以被编译进1条计算机指令，然后，它会花10秒。但是，当然，那是荒唐的。你不会做所有的那些，在1条指令里面。如果它是100条指令，然后那意味着，它会是1000秒，大概是16分钟，但是，那看起来太短。它可能将是更像1000条指令，通过一直做所有这些(指几个for循环)、去完成它，并且，然后，检查约束，并且，所以，那将是大约160分钟。并且，所以1小时到3小时。我们将可能说，2或3个小时，在那里的某个地方。可能是1小时左右。我们不能真实地说明，因为这只是1个估算。但是，它肯定将会是在小时范围内，不是在分钟或者天范围内。

实际上，我确实运行了这个程序，并且，稍后，我们将会回来，并且，看看，在那里，以某种方式的这个估计，会多好地解决。

让我只是说，因为我们已经学习了，这会花费，以某种方式的一小时的范围，不要尝试在这里(指Udacity网页)运行，因为在几秒后，这个计算会超时。

但是，首先我们必须想出，怎样做所有的约束(constraints)。所以，我们已经做了constraint数1，这里，houses = [1, 2, 3, 4, 5]。现在，让我们做constraint number 2，这里，英国人生活在red house里面。并且，我们想要写一些if语句，去检查英国人是否生活在red house里面，并且，如果是这样，我们继续；如果不是，我， 放弃。所以，我们如何检查，这是否是真的，英国人住在red ouse里面？所以，如果，并且，我想要你填入一些表达式在这里。我们将仅仅说，这是constraint number 2。告诉我，你可以在这里填什么。

import itertools houses = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) for (red, green, ivory, yellow, blue) in orderings: for (Englishman, Spaniard, Ukrianian, Japanese, Norwegian) in orderings: for (dog, snails, fox, horse, ZEBRE) in orderings: for (coffee, tea, milk, oj, WATER) in orderings: for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in orderings: if (Englishman == red): #2 # 1 sec # 1 min # 1 hour is right # 1 day

Peter的答案：
答案是，我们所有必须要做的是，检查英国人和red是否已经被分配了相同的房子号码。并且，我们仅仅做那件事，说if(Englishman == red)。并且，我应该标记为1个aside，如果你想要变得有点聪明，并且使它看起来更像英语，在这种情况下，可以说if (Englishman is red)，因为是检查2个对象是否是相同的对象。==检查他们是否是相同的值。并且，这结果是，Python处理小的整数，像1、2、3、4、5，，作为1个单独的相同的对象。所以这个is，会和这里equals起一样的作用。

11. 练习：Neighbors

Neighbors - Design of Computer Programs - YouTube

本段视频的核心部分的，我的翻译

现在，在我们继续到constraint number 3之前，我想要往回走一点，并且说，这里还有2个我们没有提到的概念：being next to的概念，并且紧挨着右边(the concepts of being next to and immediately to the right of)。紧挨着右边(immediately to the right of——well)，因为我们已经使用了房子号码，以分配房子，我们可以说，房子1是紧挨着房子2的右边，如果他们相差1，如果h1 - h2是1。所以房子号码3是紧挨着房子号码2的。我想要你做的事，是为nextto填入代码，也就是说，如果2个房子是互相相邻的。

import itertools houses = [1, 2, 3, 4, 5] orderings = list(itertools.permutations(houses)) def imright(h1, h2): "House h1 is immediately right of h2 if h1-h2 == 1" return h1-h2 == 1 def nextto(h1, h2): "Two houses are next to each other if they differ by 1." return abs(h1-h2) == 1 ## code here

我的理解是，只要h1和h2的差的绝对值是1，那么肯定是相邻的。

12. Slow Solution

Slow Solution - Design of Computer Programs - YouTube

补充视频中，一些不认识的词汇

stick with 继续做；插满

state 规定；陈述，表明

视频中的一长串的代码，有点难以理解，这里，我先上一段我自己的代码，然后再对视频中的大段代码，做一点解读。

def f(): list1 = [4, 5, 6] list2 = [1, 2, 3, 4] return ((i1, i2) for i1 in list1 for i2 in list2 if i1 == i2) '''换行的形式： return ((i1, i2) for i1 in list1 for i2 in list2 if i1 == i2 ) ''' print f() print next(f()) -------------------- 输出： <generator object <genexpr> at 0x7facbe3cc6e0> (4, 4)

如上的代码，意义比较明确，，主要看return中的语句的含义：分别循环、迭代、遍历list1和list2列表中的每一个元素，如果list1列表中的某个元素，与list2列表中的某个元素相等，则返回这2个相等的元素。注意，这里return语句是圆括号，因此，返回的是生成器表达式，即generator object。调用了next(f())后，可以输出这2个值。

关于如下的代码，我的理解：
1. 首先需要阅读1. 练习：Zebra Puzzle中，对于Zebra Puzzle规则的文字描述。
2. #2到#15的if语句，实际上是把对应序号的规则，转换为了代码。
3. return语句中的代码，其实可以合为1行，含义相同。整个return语句的含义是，对颜色、国籍、动物、饮料、烟的品牌，在orderings中，进行遍历，然后，如果满足Zebra Puzzle规则(即这些if语句)，则返回(WATER, ZEBRA)生成器表达式的next()。
4. orderings是5个房子的号码的所有的全排列情况。
5. 对于下段代码，我存在疑问的地方是，为何要用单个下划线_作为变量名，并且，3个下划线，最终只有1个赋值了。

本段视频的核心部分的，我的翻译

def zebra_pu