2020-07-22 16:25:04
当我在自己的程序中发现用到了模式,我觉得这就表明某个地方出错了。程序的形式应该仅仅反映它所要解决的问题。代码中其他任何外加的形式都是一个信号,(至少对我来说)表明我对问题的抽象还不够深——这通常意味着自己正在手动完成事情,本应该通过写代码来让宏的扩展自动实现。
——Paul Graham, Lisp 黑客和风险投资人
Python 内置了迭代器模式,用于进行惰性运算,按需求一次获取一个数据项,避免不必要的提前计算。
迭代器在 Python 中并不是一个具体类型的对象,更多地使指一个具体协议。
Python 解释器在迭代一个对象时,会自动调用 iter(x)
。
内置的 iter
函数会做以下操作:
__iter__
方法(abc.Iterable
),若实现,且返回的结果是个迭代器(abc.Iterator
),则调用它,获取迭代器并返回;__getitem__
方法(abc.Sequence
),若实现则尝试从 0 开始按顺序获取元素并返回;TypeError
,表明对象不可迭代。判断一个对象是否可迭代,最好的方法不是用 isinstance
来判断,而应该直接尝试调用 iter
函数。
注:可迭代对象和迭代器不一样。从鸭子类型的角度看,可迭代对象 Iterable
要实现 __iter__
,而迭代器 Iterator
要实现 __next__
. 不过,迭代器上也实现了 __iter__
,用于返回自身。
《设计模式:可复用面向对象软件的基础》一书讲解迭代器设计模式时,在“适用性”一 节中说:
迭代器模式可用来:
访问一个聚合对象的内容而无需暴露它的内部表示
支持对聚合对象的多种遍历
为遍历不同的聚合结构提供一个统一的接口(即支持多态迭代)
为了“支持多种遍历”,必须能从同一个可迭代的实例中获取多个独立的迭代器,而且各个迭代器要能维护自身的内部状态,因此这一模式正确的实现方式是,每次调用 iter(my_iterable)
都新建一个独立的迭代器。
iter
函数解释器需要迭代对象 x 时,会自动调用 iter(x)
:
检查对象是否实现了 __iter__
方法并调用,获取到迭代器
如果没有实现__iter__
, 检查是否有 __getitem__
函数,尝试按顺序下标获取元素
如果上述状况都不符合, 抛出 “C object is not iterable” 异常
这就是为什么这个示例需要定义 SentenceIterator
类。所以,不应该把 Sentence 本身作为一个迭代器,否则每次调用 iter(sentence)
时返回的都是自身,就无法进行多次迭代了。
1 |
# 通过实现迭代器协议,让一个对象变得可迭代 |
Return·a·list·of·all·non·overlapping·matches·in·the·string·
上面的例子中,我们的 SentenceIterator
对象继承自 abc.Iterator
通过了迭代器测试。而且 Iterator
替我们实现了 __iter__
方法。
但是,如果我们不继承它,我们就需要同时实现 __next__
抽象方法和实际迭代中并不会用到的 __iter__
非抽象方法,才能通过 Iterator
测试。
可迭代对象
使用 iter 内置函数可以获取迭代器的对象。
迭代器
迭代器是一种对象:实现了 __next__
方法,返回序列中的下一个元素,并在无元素可迭代时抛出 StopIteration
异常。
只要函数的定义体中有 yield
关键字,该函数就是生成器函数。
调用生成器函数会返回生成器对象。
如果懒得自己写一个迭代器,可以直接用 Python 的生成器函数来在调用 __iter__
时生成一个迭代器。
注:在 Python 社区中,大家并没有对“生成器”和“迭代器”两个概念做太多区分,很多人是混着用的。不过无所谓啦。
1 |
# 使用生成器函数来帮我们创建迭代器 |
1 |
# 使用 re.finditer 来惰性生成值 |
itertools
模块生成等差数列1 |
# 实用模块 |
1 |
# 使用 yield from 语句可以在生成器函数中直接迭代一个迭代器 |
[1, 2, 3, 4, 5] [1, 2, 3, 4, 5]
iter
函数还有一个鲜为人知的用法:传入两个参数,使用常规的函数或任何可调用的对象创建迭代器。这样使用时,第一个参数必须是可调用的对象,用于不断调用(没有参数),产出各个值;第二个值是哨符,这是个标记值,当可调用的对象返回这个值时,触发迭代器抛出 StopIteration 异常,而不产出哨符。
1 |
# iter 的神奇用法 |
2020-07-20 15:19:06
文章转载自:
对于支持继承的编程语言来说,其方法(属性)可能定义在当前类,也可能来自于基类,所以在方法调用时就需要对当前类和基类进行搜索以确定方法所在的位置。
而搜索的顺序就是所谓的「方法解析顺序」(Method Resolution Order,或MRO)。对于只支持单继承的语言来说,MRO 一般比较简单;而对于 Python 这种支持多继承的语言来说,MRO 就复杂很多。
先看一个「菱形继承」的例子:
如果 x
是 D
的一个实例,那么 x.show()
到底会调用哪个 show
方法呢?
如果按照 [D, B, A, C]
的搜索顺序,那么 x.show()
会调用 A.show()
;
如果按照 [D, B, C, A]
的搜索顺序,那么 x.show()
会调用 C.show()
。
由此可见,MRO 是把类的继承关系线性化的一个过程,而线性化方式决定了程序运行过程中具体会调用哪个方法。既然如此,那什么样的 MRO 才是最合理的?Python 中又是如何实现的呢?
Python 至少有三种不同的 MRO:
Python 有两种类:经典类(classic class)和新式类(new-style class)。两者的不同之处在于新式类继承自 object
。
在 Python 2.1 以前,经典类是唯一可用的形式;Python 2.2 引入了新式类,使得类和内置类型更加统一;在 Python 3 中,新式类是唯一支持的类。
经典类采用了一种很简单的 MRO 方法:从左至右的深度优先遍历。以上述「菱形继承」为例,其查找顺序为 [D, B, A, C, A]
,如果只保留重复类的第一个则结果为 [D, B, A, C]
。我们可以用 inspect.getmro
来获取类的 MRO:
1 |
import inspect |
这种深度优先遍历对于简单的情况还能处理的不错,但是对于上述「菱形继承」其结果却不尽如人意:虽然 C.show()
是 A.show()
的更具体化版本(显示了更多的信息),但我们的 x.show()
没有调用它,而是调用了 A.show()
。这显然不是我们希望的结果。
对于新式类而言,所有的类都继承自 object
,所以「菱形继承」是非常普遍的现象,因此不可能采用这种 MRO 方式。
为解决经典类 MRO 所存在的问题,Python 2.2 针对新式类提出了一种新的 MRO 计算方式:在定义类时就计算出该类的 MRO 并将其作为类的属性。因此新式类可以直接通过 __mro__
属性获取类的 MRO。
Python 2.2 的新式类 MRO 计算方式和经典类 MRO 的计算方式非常相似:它仍然采用从左至右的深度优先遍历,但是如果遍历中出现重复的类,只保留最后一个。重新考虑上面「菱形继承」的例子,由于新式类继承自 object
因此类图稍有改变:
按照深度遍历,其顺序为 [D, B, A, object, C, A, object]
,重复类只保留最后一个,因此变为 [D, B, C, A, object]
。代码为:
1 |
class A(object): |
这种 MRO 方式已经能够解决「菱形继承」问题,再让我们看个稍微复杂点的例子:
1 |
class X(object): pass |
首先进行深度遍历,结果为 [C, A, X, object, Y, object, B, Y, object, X, object]
;然后,只保留重复元素的最后一个,结果为 [C, A, B, Y, X, object]
。Python 2.2 在实现该方法的时候进行了调整,使其更尊重基类中类出现的顺序,其实际结果为 [C, A, B, X, Y, object]
。
这样的结果是否合理呢?首先我们看下各个类中的方法解析顺序:对于 A
来说,其搜索顺序为 [A, X, Y, object]
;对于 B
,其搜索顺序为 [B, Y, X, object]
;对于 C
,其搜索顺序为 [C, A, B, X, Y, object]
。我们会发现,B
和 C
中 X
、Y
的搜索顺序是相反的!也就是说,当 B
被继承时,它本身的行为竟然也发生了改变,这很容易导致不易察觉的错误。此外,即使把 C
搜索顺序中 X
和 Y
互换仍然不能解决问题,这时候它又会和 A
中的搜索顺序相矛盾。
事实上,不但上述特殊情况会出现问题,在其它情况下也可能出问题。其原因在于,上述继承关系违反了线性化的「 单调性原则 」。Michele Simionato对单调性的定义为:
A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C. Otherwise, the innocuous operation of deriving a new class could change the resolution order of methods, potentially introducing very subtle bugs.
也就是说,子类不能改变基类的方法搜索顺序。在 Python 2.2 的 MRO 算法中并不能保证这种单调性,它不会阻止程序员写出上述具有二义性的继承关系,因此很可能成为错误的根源。
除了单调性之外,Python 2.2 及 经典类的 MRO 也可能违反继承的「 局部优先级 」,具体例子可以参见官方文档。采用一种更好的 MRO 方式势在必行。
为解决 Python 2.2 中 MRO 所存在的问题,Python 2.3以后采用了 C3 方法来确定方法解析顺序。你如果在 Python 2.3 以后版本里输入上述代码,就会产生一个异常,禁止创建具有二义性的继承关系:
1 |
class C(A, B): pass |
我们把类 C
的线性化(MRO)记为 L[C] = [C1, C2,…,CN]
。其中 C1
称为 L[C]
的头,其余元素 [C2,…,CN]
称为尾。如果一个类 C
继承自基类 B1
、B2
、……、BN
,那么我们可以根据以下两步计算出 L[C]
:
L[object] = [object]
L[C(B1…BN)] = [C] + merge(L[B1]…L[BN], [B1]…[BN])
这里的关键在于 merge
,其输入是一组列表,按照如下方式输出一个列表:
L[B1]
的头),记作 H
。H
未出现在其它列表的尾部,则将其输出,并将其从所有列表中删除,然后回到步骤1;否则,取出下一个列表的头部记作 H
,继续该步骤。该方法有点类似于图的拓扑排序,但它同时还考虑了基类的出现顺序。我们用 C3 分析一下刚才的例子。
object
,X
,Y
的线性化结果比较简单:
1 |
L[object] = [object] |
A
的线性化计算如下:
1 |
L[A] = [A] + merge(L[X], L[Y], [X], [Y]) |
注意第3步,merge([object], [Y, object], [Y])
中首先输出的是 Y
而不是 object
。这是因为 object
虽然是第一个列表的头,但是它出现在了第二个列表的尾部。所以我们会跳过第一个列表,去检查第二个列表的头部,也就是 Y
。Y
没有出现在其它列表的尾部,所以将其输出。
同理,B
的线性化结果为:
1 |
L[B] = [B, Y, X, object] |
最后,我们看看 C
的线性化结果:
1 |
L[C] = [C] + merge(L[A], L[B], [A], [B]) |
到了最后一步我们没有办法继续计算下去 了:X
虽然是第一个列表的头,但是它出现在了第二个列表的尾部;Y
虽然是第二个列表的头,但是它出现在了第一个列表的尾部。因此,我们无法构建一个没有二义性的继承关系,只能手工去解决(比如改变 B
基类中 X
、Y
的顺序)。
我们再看一个没有冲突的例子:
计算过程如下:
1 |
L[object] = [object] |
当然,可以用代码验证类的 MRO,上面的例子可以写作:
1 |
class D(object): pass |
2020-07-09 16:24:11
抽象类表示接口。
——Bjarne Stroustrup, C++ 之父
本章讨论的话题是接口:
从鸭子类型的代表特征动态协议,到使接口更明确、能验证实现是否符合规定的抽象基类(Abstract Base Class, ABC)。
接口的定义:对象公开方法的子集,让对象在系统中扮演特定的角色。
协议是接口,但不是正式的(只由文档和约定定义),因此协议不能像正式接口那样施加限制。
允许一个类上只实现部分接口。
什么是接口
对象公开方法的子集,让对象在系统中扮演特定的角色。
鸭子类型与动态协议
受保护的类型与私有类型不能在接口中
可以把公开的数据属性放在接口中
1 |
class Foo: |
Foo 实现了序列协议的 __getitem__
方法。因此可支持下标操作。
Foo 实例是可迭代的对象,因此可以使用 in 操作符
FrenchDeck 类见前面章节。
FrenchDeck 实例的行为像序列,那么其实可以用 random 的 shuffle
方法来代替在类中实现的方法。
1 |
from random import shuffle |
FrenchDeck 对象不支持元素赋值。这是因为它只实现了不可变的序列协议,可变的序列还必须提供 __setitem__
方法。
1 |
def set_card(deck, pos, card): |
这种技术叫做猴子补丁:在运行是修改类或程序,而不改动源码。缺陷是补丁代码与要打补丁的程序耦合紧密。
抽象基类是一个非常实用的功能,可以使用抽象基类来检测某个类是否实现了某种协议,而这个类并不需要继承自这个抽象类。collections.abc
和 numbers
模块中提供了许多常用的抽象基类以用于这种检测。
有了这个功能,我们在自己实现函数时,就不需要非常关心外面传进来的参数的具体类型(isinstance(param, list)
),只需要关注这个参数是否支持我们需要的协议(isinstance(param, abc.Sequence
)以保障正常使用就可以了。
但是注意:从 Python 简洁性考虑,最好不要自己创建新的抽象基类,而应尽量考虑使用现有的抽象基类。
1 |
# 抽象基类 |
1 |
# 在抽象基类上进行自己的实现 |
有一点需要注意:抽象基类上的方法并不都是抽象方法。
换句话说,想继承自抽象基类,只需要实现它上面所有的抽象方法即可,有些方法的实现是可选的。
比如 Sequence.__contains__
,Python 对此有自己的实现(使用 __iter__
遍历自身,查找是否有相等的元素)。但如果你在 Sequence
之上实现的序列是有序的,则可以使用二分查找来覆盖 __contains__
方法,从而提高查找效率。
我们可以使用 __abstractmethods__
属性来查看某个抽象基类上的抽象方法。这个抽象基类的子类必须实现这些方法,才可以被正常实例化。
1 |
# 自己定义一个抽象基类 |
使用 register
接口可以将某个类注册为某个 ABC 的“虚拟子类”。支持 register
直接调用注册,以及使用 @register
装饰器方式注册(其实这俩是一回事)。
注册后,使用 isinstance
以及实例化时,解释器将不会对虚拟子类做任何方法检查。
注意:虚拟子类不是子类,所以虚拟子类不会继承抽象基类的任何方法。
1 |
# 虚拟子类 |
2020-06-24 10:48:36
本文档是对TeachYourselfCS内容的中文翻译,原作者为Ozan Onay和Myles Byrne。如需了解翻译相关信息或帮助改进翻译,请参见本文档结尾。
This document is a Chinese translation of TeachYourselfCS, which is written by Ozan Onay and Myles Byrne. For more information about this translation, please refer to the end of this document.
如果你是一个自学成才的工程师,或者从编程培训班毕业,那么你很有必要学习计算机科学。幸运的是,不必为此花上数年光阴和不菲费用去攻读一个学位:仅仅依靠自己,你就可以获得世界一流水平的教育💸。
互联网上,到处都有许多的学习资源,然而精华与糟粕并存。你所需要的,不是一个诸如“200+免费在线课程”的清单,而是以下问题的答案:
在这份指引中,我们尝试对这些问题做出确定的回答。
大致按照列出的顺序,借助我们所建议的教材或者视频课程(但是最好二者兼用),学习如下的九门科目。目标是先花100到200个小时学习完每一个科目,然后在你职业生涯中,不时温习其中的精髓🚀。
科目 | 为何要学? | 最佳书籍 | 最佳视频 |
---|---|---|---|
编程 | 不要做一个“永远没彻底搞懂”诸如递归等概念的程序员。 | 《计算机程序的构造和解释》 | Brian Harvey’s Berkeley CS 61A |
计算机架构 | 如果你对于计算机如何工作没有具体的概念,那么你所做出的所有高级抽象都是空中楼阁。 | 《深入理解计算机系统》 | Berkeley CS 61C |
算法与数据结构 | 如果你不懂得如何使用栈、队列、树、图等常见数据结构,遇到有难度的问题时,你将束手无策。 | 《算法设计手册》 | Steven Skiena’s lectures |
数学知识 | 计算机科学基本上是应用数学的一个“跑偏的”分支,因此学习数学将会给你带来竞争优势。 | 《计算机科学中的数学》 | Tom Leighton’s MIT 6.042J |
操作系统 | 你所写的代码,基本上都由操作系统来运行,因此你应当了解其运作的原理。 | 《操作系统导论》 | Berkeley CS 162 |
计算机网络 | 互联网已然势不可挡:理解工作原理才能解锁全部潜力。 | 《计算机网络:自顶向下方法》 | Stanford CS 144 |
数据库 | 对于多数重要程序,数据是其核心,然而很少人理解数据库系统的工作原理。 | 《Readings in Database Systems》 (暂无中译本) | Joe Hellerstein’s Berkeley CS 186 |
编程语言与编译器 | 若你懂得编程语言和编译器如何工作,你就能写出更好的代码,更轻松地学习新的编程语言。 | 《Crafting Interpreters》 | Alex Aiken’s course on Lagunita |
分布式系统 | 如今,多数 系统都是分布式的。 | 《数据密集型应用系统设计》 | MIT 6.824 |
如果花几年时间自学 9 门科目让人望而却步,我们建议你只专注于两本书:《深入理解计算机系统》 和 《数据密集型应用系统设计》。根据我们的经验,投入到这两本书的时间可以获得极高的回报率,特别适合从事网络应用开发的自学工程师。这两本书也可以作为上面表格中其他科目的纲领。
软件工程师分为两种:一种充分理解了计算机科学,从而有能力应对充满挑战的创造性工作;另一种仅仅凭着对一些高级工具的熟悉而勉强应付。
这两种人都自称软件工程师,都能在职业生涯早期挣到差不多的工资。然而,随着时间流逝,第一种工程师不断成长,所做的事情将会越来越有意义且更为高薪,不论是有价值的商业工作、突破性的开源项目、技术上的领导力或者高质量的个人贡献。
全球短信系统每日收发约200亿条信息,而仅仅靠57名工程师,现在的 WhatsApp 每日收发420亿条。
— Benedict Evans (@BenedictEvans) 2016年2月2日
第一种工程师总是寻求深入学习计算机科学的方法,或是通过传统的方法学习,或是在职业生涯中永无止息地学习;第二种工程师
通常浮于表面,只学习某些特定的工具和技术,而不研究其底层的基本原理,仅仅在技术潮流的风向改变时学习新的技能。
如今,涌入计算机行业的人数激增,然而计算机专业的毕业生数量基本上未曾改变。第二种工程师的供过于求正在开始减少他们的工作机会,使他们无法涉足行业内更加有意义的工作。对你而言,不论正在努力成为第一种工程师,还是只想让自己的职业生涯更加安全,学习计算机科学是唯一可靠的途径。
23333 然而他们… pic.twitter.com/XVNYlXAHar
— Jenna Bilotta (@jenna) 2017年3月4日
大多数计算机专业本科教学以程序设计“导论”作为开始。这类课程的最佳版本不仅能满足初学者的需要,还适用于那些在初学编程阶段遗漏了某些有益的概念和程序设计模式的人。
对于这部分内容,我们的标准推荐是这部经典著作:《计算机程序的构造和解释》。在网络上,这本书既可供免费阅读(英文版),也作为MIT的免费视频课程。不过尽管这些视频课程很不错,我们对于视频课程的推荐实际上是Brian Harvey 开设的 SICP 课程(即 Berkeley 的 61A 课程)。比起MIT的课程,它更加完善,更适用于初学者。
我们建议至少学完SICP的前三章,并完成配套的习题。如果需要额外的练习,可以去解决一些小的程序设计问题,比如exercism。
中文翻译新增:
- 关于SICP国内视频观看地址
- Scheme 学习的相关资源参见:https://github.com/DeathKing/Learning-SICP
- 更详细的补充说明:#3
自从 2016 年首次发布这份指南以来,最常被问到的一个问题是,我们是否推荐由 John DeNero 讲授的更新的 CS 61A 课程,以及配套的书籍 《Composing Programs》,这本书“继承自 SICP” 但使用 Python 讲解。我们认为 DeNero 的课程也很不错,有的学生可能更喜欢,但我们还是建议把 SICP, Scheme 和 Brian Harvey 的视频课程作为首选。
为什么这么说呢?因为 SICP 是独一无二的,它可以——至少很有可能——改变你对计算机和编程的基本认识。不是每个人都有这样的体验。有的人讨厌这本书,有的人看了前几页就放弃了。但潜在的回报让它值得一读。
如果你觉得SICP过于难,试试 《Composing Programs》。如果还是不合适,那我们推荐 《程序设计方法》(中文版,英文版) ;如果你觉得SICP过于简单,那我们推荐 《Concepts, Techniques, and Models of Computer Programming》 。如果读这些书让你觉得没有收获,也行你应该先学习其他科目,一两年后再重新审视编程的理念。
新版原文删除了对 《Concepts, Techniques, and Models of Computer Programming》 一书的推荐,但这本书对各种编程模型有深入的见解,值得一读。所以译文中依然保留。
— 译者注
最后,有一点要说明的是:本指南不适用于完全不懂编程的新手。我们假定你是一个没有计算机专业背景的程序员,希望填补一些知识空白。事实上,我们把“编程”章节包括进来只是提醒你还有更多知识需要学习。对于那些从来没有学过编程,但又想学的人来说,这份指南更合适。
计算机架构——有时候又被称为“计算机系统”或者“计算机组成”——是了解软件底层的的重要视角。根据我们的经验,这是自学的软件工程师最容易忽视的领域。
我们最喜欢的入门书是 《深入理解计算机系统》。典型的计算机体系结构导论课程会涵盖本书的 1 - 6 章。
我们喜爱《深入理解计算机系统》,因为它的实用性,并且站在程序员的视角。虽然计算机体系结构的内容比本书所涉及的内容多得多,但对于那些想了解计算机系统以求编写更快、更高效、更可靠的软件的人来说,这本书是很好的起点。
对于那些既想了解这个主题又想兼顾硬件和软件的知识的人来说,我们推荐 《计算机系统要素》,又名“从与非门到俄罗斯方块”(“Nand2Tetris”),这本书规模宏大,让读者对计算机内的所有部分如何协同工作有完全的认识。这本书的每一章节对应如何构建计算机整体系统中的一小部分,从用HDL(硬件描述语言)写基本的逻辑门电路出发,途经CPU和汇编,最终抵达诸如俄罗斯方块这般规模的应用程序。
我们推荐把此书的前六章读完,并完成对应的项目练习。这么做,你将更加深入地理解,计算机架构和运行其上的软件之间的关系。
这本书的前半部分(包括所有对应的项目)均可从Nand2Tetris的网站上免费获得。同时,在Coursera上,这是一门视频课程。
为了追求简洁和紧凑,这本书牺牲了内容上的深度。尤其值得注意的是,流水线和存储层次结构是现代计算机架构中极其重要的两个概念,然而这本书对此几乎毫无涉及。
当你掌握了Nand2Tetris的内容后,我们推荐要么回到《深入理解计算机系统》,或者考虑Patterson和Hennessy二人所著的 《计算机组成与设计》,一本优秀的经典著作。这本书中的不同章节重要程度不一,因此我们建议根据Berkeley的CS61C课程 “计算机架构中的伟大思想”来着重阅读一些章节。这门课的笔记和实验在网络上可以免费获得,并且在互联网档案中有这门课程的过往资料。
硬件是平台。
— Mike Acton, Engine Director at Insomniac Games
(观看他在CppCon上的演说)
正如几十年来的共识,我们认为,计算机科学教育所赋予人们的最大能量在于对常见算法和数据结构的熟悉。此外,这也可以训练一个人对于各种问题的解决能力,有助于其他领域的学习。
关于算法与数据结构,有成百上千的书可供使用,但是我们的最爱是Steven Skiena编写的 《算法设计手册》。显而易见,他对此充满热爱,迫不及待地想要帮助其他人理解。在我们看来,这本书给人一种焕然一新的体验,完全不同于那些更加经常被推荐的书(比如Cormen,Leiserson,Rivest 和 Stein,或者 Sedgewick的书,后两者充斥着过多的证明,不适合以 解决问题 为导向的学习)。
如果你更喜欢视频课程,Skiena慷慨地提供了他的课程。此外,Tim Roughgarden的课程也很不错,
在Stanford的MOOC平台Lagunita,或者Coursera上均可获得。Skiena和Roughgarden的这两门课程没有优劣之分,选择何者取决于个人品味。
至于练习,我们推荐学生在Leetcode上解决问题。Leetcode上的问题往往有趣且带有良好的解法和讨论。此外,在竞争日益激烈的软件行业,这些问题可以帮助你评估自己应对技术面试中常见问题的能力。我们建议解决大约100道随机挑选的Leetcode问题,作为学习的一部分。
最后,我们强烈推荐 《怎样解题》。这本书极为优秀且独特,指导人们解决广义上的问题,因而一如其适用于数学,它适用于计算机科学。
我可以广泛推荐的方法只有一个: 写之前先思考。
— Richard Hamming
从某个角度说,计算机科学是应用数学的一个“发育过度”的分支。尽管许多软件工程师试图——并且在不同程度上成功做到——忽视这一点,我们鼓励你用学习来拥抱数学。如若成功,比起那些没有掌握数学的人,你将获得巨大的竞争优势。
对于计算机科学,数学中最相关的领域是“离散数学”,其中的“离散”与“连续”相对立,大致上指的是应用数学中那些有趣的主题,而不是微积分之类的。由于定义比较含糊,试图掌握离散数学的全部内容是没有意义的。较为现实的学习目标是,了解逻辑、排列组合、概率论、集合论、图论以及密码学相关的一些数论知识。考虑到线性代数在计算机图形学和机器学习中的重要性,该领域同样值得学习。
学习离散数学,我们建议从László Lovász的课程笔记开始。Lovász教授成功地让这些内容浅显易懂且符合直觉,因此,比起正式的教材,这更适合初学者。
对于更加高阶的学习,我们推荐 《计算机科学中的数学》,MIT同名课程的课程笔记,篇幅与书籍相当(事实上,现已出版)。这门课程的视频同样可免费获得,是我们所推荐的学习视频。
对于线性代数,我们建议从Essence of linear algebra系列视频开始,然后再去学习Gilbert Strang的《线性代数导论》和视频课程。
如果人们不相信数学是简单的,那么只能是因为他们没有意识到生活有多么复杂。
— John von Neumann
《操作系统概念》 (“恐龙书”)和 《现代操作系统》 是操作系统领域的经典书籍。二者都因为写作风格和对学生不友好而招致了一些批评。
《操作系统导论》(Operating Systems: Three Easy Pieces) 是一个不错的替代品,并且可在网上免费获得(英文版)。我们格外喜欢这本书的结构,并且认为这本书的习题很值得一做。
在读完《操作系统导论》后,我们鼓励你探索特定操作系统的设计。可以借助“{OS name} Internals”风格的书籍,比如 Lion’s commentary on Unix, The Design and Implementation of the FreeBSD Operating System,以及 Mac OS X Internals。对于 Linux ,我们推荐 Robert Love 的 《Linux内核设计与实现》。
为了巩固对操作系统的理解,阅读小型系统内核的代码并且为其增加特性是一个很不错的方法。比如,xv6,由MIT的一门课程所维护的从Unix V6到ANSI C和x86的移植,就是一个很棒的选择。《操作系统导论》有一个附录,记载了一些可能的xv6实验项目,其中充满了关于潜在项目的很棒想法。
鉴于有那么多关于网络服务端和客户端的软件工程,计算机网络是计算机科学中价值最为“立竿见影”的领域之一。我们的学生,系统性地学习了计算机网络,最终能够理解那些曾困扰他们多年的术语、概念和协议。
在这一主题上,我们最爱的书籍是 《计算机网络:自顶向下方法》。书中的小项目和习题相当值得练习,尤其是其中的“Wireshark labs”(这部分在网上可以获得)。
如果更喜欢视频课程,我们推荐Stanford的Introduction to Computer Networking,可在他们的MOOC平台Lagunita上免费观看。
对于计算机网络的学习,做项目比完成小的习题更有益。一些可能的项目有:HTTP服务器,基于UDP的聊天APP,迷你TCP栈,代理,负载均衡器,或者分布式哈希表。
你无法盯着水晶球预见未来,未来的互联网何去何从取决于社会。
— Bob Kahn
比起其他主题,自学数据库系统需要更多的付出。这是一个相对年轻的研究领域,并且出于很强的商业动机,研究者把想法藏在紧闭的门后。此外,许多原本有潜力写出优秀教材的作者反而选择了加入或创立公司。
鉴于如上情况,我们鼓励自学者大体上抛弃教材,而是从2015年春季学期的CS 186课程(Joe Hellerstein在Berkeley的数据库课程)开始,然后前往阅读论文。
对于初学者,有一篇格外值得提及的论文:“Architecture of a Database System”。这篇论文提供了独特的对关系型数据库管理系统(RDBMS)如何工作的高层次观点,是后续学习的实用梗概。
《Readings in Database Systems》,或者以数据库“红书”更为人知,是由Peter Bailis,Joe Hellerstein和Michael Stonebraker编纂的论文合集。对于那些想要在CS 186课程的水平更进一步的学习者,“红书”应当是下一步。
如果你坚持一定要一本导论教材,那我们推荐Ramakrishnan和Gehrke所著的 《数据库管理系统:原理与设计》。如需更深一步,Jim Gray的经典著作 《Transaction Processing: Concepts and Techniques》 值得一读,不过我们不建议把这本书当作首要资源。
如果没有编写足够数量的代码,很难巩固数据库理论。CS 186课程的学生给Spark添加特性,倒是不错的项目,不过我们仅仅建议从零实现一个简单的关系型数据库管理系统。自然,它将不会有太多的特性,但是即便只实现典型的关系型数据库管理系统每个方面最基础的功能,也是相当有启发的。
最后,数据模型往往是数据库中一个被忽视的、教学不充分的方面。关于这个主题,我们推荐的书籍是 Data and Reality: A Timeless Perspective on Perceiving and Managing Information in Our Imprecise World。
多数程序员学习编程语言的知识,而多数计算机科学家学习编程语言 相关 的知识。这使得计算机科学家比起程序员拥有显著的优势,即便在编程领域!因为他们的知识可以推而广之:相较只学习过特定编程语言的人,他们可以更深入更快速地理解新的编程语言。
我们推荐的入门书是 Bob Nystrom 所著的优秀的 Crafting Interpreters,可在网上免费获取。这本书条理清晰,富有趣味性,非常适合那些想要更好地理解语言和语言工具的人。我们建议你花时间读完整本书,并尝试任何一个感兴趣的“挑战”。
另一本更为传统的推荐书籍是 《编译原理》,通常称为“龙书”。不幸的是,这本书不是为自学者而设计的,而是供教师从中挑选一些主题用于1-2学期的教学。
如果你选择使用龙书进行自学,你需要从中甄选主题,而且最好是在导师的帮助下。我们建议依据某个视频课程来设定学习的结构,然后按需从龙书中获取深入的内容。我们推荐的在线课程是Alex Aiken在MOOC平台 edX 所开设的。
不要做一个只写样板代码的程序员。相反,给用户和其他程序员创造工具。从纺织工业和钢铁工业中学习历史教训:你想制造机器和工具,还是操作这些机器?
— Ras Bodik 在他的编译器课程伊始
随着计算机在数量上的增加,计算机同样开始 分散。尽管商业公司过去愿意购买越来越大的大型机,现在的典型情况是,甚至很小的应用程序都同时在多台机器上运行。思考这样做的利弊权衡,即是分布式系统的研究所在,也是越来越重要的一项技能。
我们推荐的自学参考书是 Martin Kleppmann 的 《数据密集型应用系统设计》。与传统的教科书相比,它是一本为实践者设计的具有很高的可读性的书,并且保持了深度和严谨性。
对于那些偏爱传统教材,或者希望可以从网上免费获取的人,我们推荐的教材是Maarten van Steen和Andrew Tanenbaum所著的 《分布式系统原理与范型》(中文第二版,英文第三版)。
对于喜欢视频课程的人,MIT的6.824 是一门很好的在线视频课程,由 Robert Morris 教授的研究生课程,在这里可以看到课程安排。
不管选择怎样的教材或者其他辅助资料,学习分布式系统必然要求阅读论文。这里有一个不错的论文清单,而且我们强烈建议你出席你当地的Papers We Love(仅限美国)。
我们面向自学的软件工程师、培训班学生、“早熟的”高中生或者想要通过自学补充正式教育的大学生。关于何时开启这段自学旅程,完全取决于个人,不过多数人在有一定的职业经历后深入学习计算机科学理论会获益匪浅。比如,我们注意到,如果学生在工作中曾经使用过数据库,他们会 喜爱 学习数据库系统课程;如果学生从事过一两个Web项目,他们会 喜爱 学习计算机网络。
我们试图把计算机科学主题清单限制到那些我们认为 每一个软件工程师 都应该了解的内容,不限于专业或行业。拥有了这些基础,你将能更加轻松地挑选教材或论文,然而无需指引地学习核心概念。在这里,我们给出一些其他常见主题的自学起点:
事实上,所有主题之间都有一定程度的重叠,彼此循环引用。以离散数学和算法的关系为例:先学习数学可以帮助你更深入地分析和理解算法,然而先学习算法可以为学习离散数学提供更大的动力和应用背景。理想情况下,你将在你的职业生涯多次重温二者。
因此,我们所推荐的次序主要是为了帮助你 起步……如果你出于某种强烈的原因而倾向以不同的顺序学习,那也没有关系,勇敢开始吧!不过在我们看来,最重要的“先决条件”是:先学计算机架构再学操作系统或数据库,先学计算机网络和操作系统再学分布式系统。
OSS指引涵盖太多主题,在许多主题中推荐劣质资源,没有就特定课程哪些方面有价值提供原因或指引。我们努力对这份指引中的课程加以限制,仅仅包括那些你作为软件工程师 确实需要了解的,不论你的专业方向,并且对每门课程为何必要做出了解释以帮助你理解。
FreeCodeCamp主要关注编程,而不是计算机科学。至于你为什么要学习计算机科学,参见上文。如果你是个新手,我们建议先学 freeCodeCamp 的课程,一两年后再回归本指南。
学习一门特定的编程语言和学习计算机科学的一个领域完全不在一个维度——相比之下,学习语言 容易 且 缺乏价值。如果你已经了解了一些语言,我们强烈建议遵照我们的指引,然后在学习的空当中习得语言,或者暂且不管以后再说。如果你已经把编程学得不错了(比如学完了 《计算机程序的构造和解释》),尤其是如果你学习过编译器,那么面对一门新的语言,你只需要花一个周末稍多的时间即可基本掌握,之后你可以在工作中学习相关的类库/工具/生态。
没有任何一种技术的重要程度可以达到学习其使用足以成为计算机科学教学的核心部分。不过,你对学习那门技术充满热情,这很不错。诀窍是先从特定的技术回退到基本的领域或概念,判断这门流行技术在技术的宏观大局中位于何处,然后才深入学习这门技术。
先尝试读一下,有些人觉得 SICP 让人神魂颠倒,这在其他书很少见。如果你不喜欢,你可以尝试其他的东西,也许以后再回到 SICP。
龙书依旧是内容最为完整的编译器单本书籍。由于过分强调一些如今不够时新的主题的细节,比如解析,这本书招致了恶评。然而事实上,这本书从未打算供人一页一页的学习,而仅仅是为了给教师准备一门课程提供足够的材料。类似地,自学者可以从书中量身按需挑选主题,或者最好依照公开课授课教师在课程大纲中的建议。
我们所建议的许多教材在网上都可以免费获得,这多亏了作者们的慷慨。对于那些不免费的书籍,我们建议购买旧版本的二手书籍。广而言之,如果一本教材有多个版本,旧版本大概率是完全足够使用的。即便新版本的价格是旧版本的10倍,新版本也绝不可能比旧版本好10倍!
中文翻译新增: 事实上,比起美国,在国内购买技术书籍可以说是相当“廉价”了。如果仍旧寻求更加便宜的购买渠道,可以参考这篇V2EX上的讨论帖子,其中提到了一些不错的购买渠道。
这份指引由Bradfield School of Computer Science(旧金山)的两位教员:Ozan Onay和Myles Byrne编写,并由 Oz 于 2020 年更新。这份指引基于我们对数千名自学成才的工程师和培训班学生教授计算机科学基础的经验。感谢我们所有学生对自学资源的持续反馈。
只要有足够的时间和动力,我们非常有信心,你可以自学完以上所有课程。如果你喜欢一个集中式、结构化、由教师指导的课程,你可能对我们的计算机科学强化班感兴趣。我们不建议你去攻读硕士学位。
这份指引的中文翻译是社区共同贡献的成果,我们欢迎任何反馈和改进!
2020-06-15 14:53:31
转载自:https://ncona.com/2020/06/create-diagrams-with-code-using-graphviz/
您是否曾为绘制过架构图时重复的单击和拖动而感到乏味?
您是否需要对该图进行修改发现改动却很复杂?
Graphviz 是一个开源的图形可视化软件,它使我们能够使用代码描述图表,并为我们自动绘制。如果将来需要修改该图,我们只需要修改描述代码,节点和边将自动为我们重新定位。
在开始编写图形之前,我们需要学习如何将代码转换为图像,以便可以测试正在做的事情。
Webgraphviz.com 可用于从浏览器绘制图形。
我们可以使用 apt 在 Ubuntu 中安装命令行工具:
1 |
1 sudo apt install graphviz |
在 macOS 环境 使用 brew 安装
1 |
brew install graphviz |
除其他外,这将安装 dot
CLI,该CLI可用于从文本文件生成图像:
1 |
1 dot -Tpng input.gv -o output.png |
在上面的示例中,我们将 png 指定为output(-Tpng
),但是有许多可用的选项。如我们所见,输入文件通常使用gv
扩展名。
DOT是用于描述要由Graphviz解析的图形的最常见格式。
一个简单的图形具有以下形式:
1 |
graph MyGraph { |
如果要使用有向图(带箭头),则需要使用digraph
:
1 |
digraph MyGraph { |
箭头可以单向或双向:
1 |
digraph MyGraph { |
如果我们不喜欢椭圆形,可以使用其他形状:
1 |
digraph MyGraph { |
我们还可以向节点添加一些颜色和样式:
1 |
digraph MyGraph { |
箭头的尾巴和头部也可以修改:
1 |
digraph MyGraph { |
可以在箭头形状文档中找到不同的箭头类型。
以及向箭头线添加样式:
1 |
digraph MyGraph { |
如果我们注意上面的代码和图表,我们可以看到,当我们为箭头指定多种颜色时,如果不指定任何权重,每种颜色将只有一行。如果我们想要一个带有多种颜色的箭头,则至少一种颜色必须指定要覆盖的线条的重量百分比:
1 |
1 a -> e [dir=none,color="green:red;.3:blue"] |
我们可以向节点添加标签:
1 |
digraph MyGraph { |
以及顶点:
1 |
digraph MyGraph { |
我们可以设置标签样式:
1 |
digraph MyGraph { |
聚类也称为子图。集群的名称必须以开头cluster_
,否则将不会包含在框中。
1 |
digraph MyGraph { |
集群可以根据需要嵌套:
1 |
digraph MyGraph { |
HTML使我们可以创建更复杂的节点,这些节点可以分为多个部分。可以在图中独立地引用每个部分:
1 |
digraph MyGraph { |
只有HTML的一个子集可用于创建节点,并且规则非常严格。为了使节点正确显示,我们需要将设置shape
为plaintext
。
需要注意的另一件事是port
属性,它使我们可以使用冒号(a:a1
)来引用该特定单元格。
我们可以设置HTML节点的样式,但只能使用HTML的子集:
1 |
digraph MyGraph { |
有时我们想为节点使用指定图标,这可以通过image
属性来完成:
1 |
digraph MyGraph { |
等级是最难理解的事情之一,因为它们会改变渲染引擎的工作方式。在这里,我将介绍一些我认为有用的基本知识。
图表通常会从上到下呈现:
1 |
digraph MyGraph { |
使用rankdir
属性,我们可以从左到右渲染它:
1 |
digraph MyGraph { |
排名还可以用于强制一个节点与另一个节点处于同一级别:
1 |
digraph MyGraph { |
在上面的示例中,我们用于rank=same
将node c
与node 对齐b
。
该rankdir
属性是全局属性,因此无法在集群内部更改,但是使用rank
我们可以模拟LR
集群内部的方向:
1 |
digraph MyGraph { |
我们可以结合rank
使用constraint=false
以创建更紧凑的图形:
1 |
digraph MyGraph { |
等级还可以用于指定每个节点之间的距离:
1 |
digraph MyGraph { |
其缺省值ranksep
是.5
。
在这篇文章中,我们学习了如何使用 Graphviz 基于声明性语言生成图。这使我在将来更容易绘制架构图并对其进行修改。
我介绍了我认为对于日常使用最重要的功能,但是坦率地说,很多功能我仍还不了解。
2020-06-05 15:07:28
最近在用python写一个小工具,这个工具主要就是用来管理各种资源的信息,比如阿里云的ECS等信息,因为我工作的电脑使用的是LINUX,所以就想着用python写一个命令行的管理工具,基本的功能就是同步阿里云的资源的信息到数据库,然后可以使用命令行查询。
因为信息是展现在命令行中的,众所周知,命令行展现复杂的文本看起来着实累人,于是就想着能像表格那样展示,那看起来就舒服多了。
prettytable库就是这么一个工具,prettytable可以打印出美观的表格,并且对中文支持相当好(如果有试图自己实现打印表格,你就应该知道处理中文是多么的麻烦)
说明:本文使用Markdown语法编写,为了展示方便,以及复制方便,所以本文中没有使用截图,因为格式控制的问题,文章中的运行结果会出现一些分割线的偏移,在终端中呈现并此问题,请各位手动去操作验证。
prettytable并非python的内置库,通过 pip install prettytable
即可安装。
我们先来看一个示例:
1 |
#!/usr/bin/python |
以上示例运行结果如下:
1 |
linuxops@deepin:~$ python p.py |
在以上的示例中,我们通过form
导入了表格库。 table
实例化了一个表格库,并且添加了['编号','云编号','名称','IP地址']
为表头,如果没有添加表头,那么会以默认的Field+编号显示,例如:
1 |
+---------+----------+----------+------------+ |
所以为更直观看出每一列的意义,还是要添加表头的。
prettytable提供了多种的添加数据的方式,最常用的应该就是按行按列添加数据了。
在上面简单的示例中,我们就是按行添加数据的。
添加的数据必须要是列表的形式,而且数据的列表长度要和表头的长度一样。在实际的使用中,我们应该要关注到添加的数据是否和表头对应,这一点很重要。
看下面的示例:
1 |
#!/usr/bin/python |
运行结果如下:
1 |
+-------+--------+------------+ |
以上示例中,我们通过add_column
来按列添加数据,按列添加数据不需要在实例化表格的时候制定表头,它的表头是在添加列的时候指定的。
table.add_column('项目', ['编号','云编号','名称','IP地址'])
这一行代码为例,项目
指定了这个列的表头名为"项目",['编号','云编号','名称','IP地址']
为列的值,同样为列表。
PrettyTable不仅提供了手动按行按列添加数据,也支持直接从csv文件中读取数据。
1 |
#!/usr/bin/python |
如果要读取cvs文件数据,必须要先导入from_csv
,否则无法运行。上面的示例运行结果如下:
1 |
+------+----------+----------+------------+ |
csv文件不能通过xls直接重命名得到,会报错。如果是xls文件,请用另存为csv获得csv文件
从数据库查询出来的数据可以直接导入到表格打印,下面的例子使用了sqlite3
,如果使用的是mysql也是一样的,只要能查询到数据就能导入到表格中
1 |
#!/usr/bin/python |
运行结果如下:
1 |
+------+----------+----------+------------+ |
支持从html的表格中导入,请看下面这个例子:
1 |
#!/usr/bin/python |
运行结果如下:
1 |
+------+----------+----------+------------+ |
如上示例中,我们可以导入html的表格,但是不一样的地方是print
语句,使用html表格导入数据的时候print的必须是列表中的第一个元素,否则有可能会报[<prettytable.PrettyTable object at 0x7fa87feba590>]
这样的错误。
这是因为table
并不是PrettyTable对象,而是包含单个PrettyTable对象的列表,它通过解析html而来,所以无法直接打印table
,而需要打印table[0]
正如支持多种输入一样,表格的输出也支持多种格式,我们在上面中的例子中已经使用了print的方式输出,这是一种常用的输出方式。
直接通过print
打印出表格。这种方式打印出的表格会带边框。
print(table.get_html_string())
可以打印出html标签的表格。
在上面的例子中,使用print(table.get_html_string())
会打印出如下结果:
1 |
<table> |
prettytable在创建表格之后,你依然可以有选择的输出某些特定的行.
print table.get_string(fields=["编号", "IP地址"])
可以输出指定的列
通过print(table.get_string(start = 0, end = 2))
的可以打印出指定的列,当然start
和end
参数让我可以自由控制显示区间。当然区间中包含start
不包含end
,是不是很熟悉这样的用法?
根据输出指定行列的功能,我们可以同时指定行和列来输出,这里就不说明了。
从上面的输出区间,我们做一个大胆的假设,既然区间包含start
不包含end
这种规则和切片的一样,我们可以不可通过切片来生成一个新的表格然后将其打印。
事实上是可以的。
1 |
new_table = table[0:2] |
如上代码段中,我们就可以打印出0到1行共2行的表格,python的切片功能异常强大,配合切片我们可以自由的输入任意的行。
有时候我们需要对输出的表格进行排序,使用print table.get_string(sortby="编号", reversesort=True)
就可以对表格进行排序,其中reversesort
指定了是否倒序排序,默认为False
,即默认正序列排序。
sortby
指定了排序的字段。
通过set_style()
可以设置表格样式,prettytable内置了多种的样式个人觉得MSWORD_FRIENDLY
,PLAIN_COLUMNS
,DEFAULT
这三种样式看起来比较清爽,在终端下显示表格本来看起就很累,再加上一下花里胡哨的东西看起来就更累。
除了以上推荐的三种样式以外,还有一种样式不得不说,那就是RANDOM
,这是一种随机的样式,每一次打印都会在内置的样式中随机选择一个,比较好玩。
具体内置了几种样式,请各位参考官网完整自己尝试输出看看。
1 |
#!/usr/bin/python |
除了内置的样式以外,PrettyTable也提供了用户自定义,例如对齐方式,数字输出格式,边框连接符等等
align
提供了用户设置对齐的方式,值有l
,r
,c
方便代表左对齐,右对齐和居中 如果不设置,默认居中对齐。
在PrettyTable中,边框由三个部分组成,横边框,竖边框,和边框连接符(横竖交叉的链接符号)
如下示例:
1 |
#!/usr/bin/python |
table.junction_char
控制边框连接符
table.horizontal_char
控制横边框符号
table.vertical_char
控制竖边框符号
上例运行如下:
1 |
$++++++$++++++++++$++++++++++$++++++++++++$ |
以上简单介绍了表格常用的一些样式设置,具体的请参考官方网站。
https://github.com/jazzband/prettytable
https://code.google.com/archive/p/prettytable/wikis/Tutorial.wiki