值 Values
在 Python 中0o20
为八进制的16
,0b1101
为二进制13
,0x
为十六进制。
还有字符串 string ,元组 tuple ,范围 range ,列表 list ,字典 dictionary ,集合 set
函数 Functions,表达式 Expressions,环境 Environments
定义函数:
def saxb (a, x, b ): return a * x + b
写成 λ 表达式(能当作表达式的函数):
lambda a, x, b: a * x + b
Environment 是名称 对值 的映射
在环境中名称 被绑定到值 上
最外层环境叫 global environment frame
函数被称为第一类值 first-class values ,可以作为某一函数的参数或返回值:
def add_func (f, g ): def adder (x ): return f(x) + g(x) return adder>>> from math import sin,cos,pi>>> h=add_func(sin,cos)>>> sin(pi/4 )+cos(pi/4 )1.414 ⋯>>> h(pi/4 )1.414 ⋯
控制 Control
有if
,while
,for
等。
双分支:True部分 if 条件 else False部分
,类似于 C 语言的?:
运算符
多分支:
if 条件1 : 语句1 elif 条件2 : 语句2 ⋯else : 语句n
注:and
和or
有短路作用
注意缩进
递归 Recursion
一个函数只调用一次的叫做线性递归 Linear Recursion ,在函数末尾调用的叫做尾递归 Tail Recursion ,尾递归往往能写成循环形式。
如以下求平方和的程序:
"""循环形式:""" def sum_squares (N ): """1^2+2^2+⋯N^2""" accum = 0 k = 1 while k <= N: accum = accum + k**2 k = k + 1 return accum"""尾递归(同时也是线性递归)形式:""" def sum_squares (N ): def part_sum (accum, k ): if k <= N: return part_sum(accum + k**2 , k + 1 ) else : return accum return part_sum(0 , 1 )
防止无限递归的方法:确保每一次递归都减少了问题规模,直到最小的问题能被解决。
子问题 与自我相似 ,例如分形问题
树递归 Tree Recursion :单次递归中多次调用递归函数
异常 Exception
可以使用try
语句检查异常:
try : input = open (myfile).read()except FileNotFoundError: print ("Warning:could not open" , myfile) input = ""
修饰器 Decorator
@ATTR def afunc (⋯ ): ⋯ 相当于:def afunc (⋯ ): ⋯ afunc=ATTR(afunc)
容器 Container
Python 中的序列 Sequence 有:
类型
元素
可编号
可变
可迭代
元组 tuple
任何类型
✓
×
✓
列表 list
任何类型
✓
✓
✓
字符串 string
str
✓
×
✓
范围 range
整形 integer
✓
×
✓
迭代器 iterator
任何类型
×
×
✓
生成器 generator
任何类型
×
×
✓
构造:
类型
写法
值
tuple
(1,4,"Hello",(2,3)) ()
1,4,"Hello",(2,3) 空序列
list
[1,4,"Hello",(2,3)] []
1,4,"Hello",(2,3) 空序列
range
range(4) range(1,12,2)
0,1,2,3 1,3,5,7,9,11
string 类型即可用''
,也可用""
切片 slicing :
t = (2 , 0 , 9 , 10 , 11 ) t[1 :4 ] == (0 , 9 , 10 ) t[2 :] == (9 , 10 , 11 ) t[::-1 ] == t[0 :len (t):-1 ] == (11 , 10 , 9 , 0 , 2 )
序列之间可以嵌套,相同序列可以相加:
A = [1 , 2 ] B = [7 , 8 , 9 ] A + B == [1 , 2 , 7 , 8 , 9 ] A * 3 == [1 , 2 , 1 , 2 , 1 , 2 ]
for 循环
使用 for 循环可对可迭代对象迭代:
for x in range (10 ): print (x)
多变量迭代:
L = [(1 , 9 ), (2 , 8 ), (3 , 7 )]for x, y in L: print (f"x,y=({x} ,{y} )" ) x,y=(1 ,9 ) x,y=(2 ,8 ) ⋯
zip
函数能将多个序列合并为一个,返回一个 generator
>>> list (zip ([1 ,2 ,5 ,3 ],[9 ,2 ,6 ,3 ,10 ])) [(1 ,9 ),(2 ,2 ),(5 ,6 ),(3 ,3 )]
for
,if
,list
综合应用:
[表达式 for 变量 in 序列表达式 if boolean表达式] 可以嵌套for 循环:>>> [(a,b)for a in range (10 ,13 ) for b in range (2 )] [(10 , 0 ), (10 , 1 ), (11 , 0 ), (11 , 1 ), (12 , 0 ), (12 , 1 )]
所以 Python 程序总是写成一行,让人很难理解。
数据抽象 Data Abstraction
抽象数据类型 Abstract data type(ADT)
接口 interface
API:Application Programming Interface 应用编程接口
constructor:例如 pair
accessor:例如 left 和 right
mutator:例如 set_left 和 set_right
字典 dictionary,矩阵 matrix,树 tree
dictionary
相当于键值对的映射,排序方式为插入顺序:
words={"ljkadf" :"fadjosodfsij" ,"jfoe" :"aewffe" } words["ljkadf" ]=="fadjosodfsij"
矩阵实现:
def matrix (rows, cols ): return [[0 for col in range (cols)] for row in range (rows)]def value (matrix, row, col ): return matrix[row][col]def set_value (matrix, row, col, val ): matrix[row][col] = val
树的实现(list+tuple):
def tree (label, children=[] ): return (label, children)def label (tree ): return tree[0 ]def children (tree ): return tree[1 ]def is_leaf (tree ): return len (children(tree)) == 0 def count_leaves (t ): if (is_leaf(t)): return 1 else : children_leaves = 0 for c in children(t): children_leaves += count_leaves(c) return children_leaves
将树上的值翻倍:
非破坏性操作 Non-destructive :
def tree (label, children=[] ): return (label, children)def label (tree ): return tree[0 ]def children (tree ): return tree[1 ]def is_leaf (tree ): return len (children(tree)) == 0 def double (t ): """返回一棵树""" if (is_leaf(t)): return tree(label(t) * 2 ) else : doubled_children = [] for c in children(t): doubled_children.append(double(c)) return tree(label(t) * 2 , doubled_children)
破坏性操作 Destructive :
def tree (label, children=[] ): return [label] + childrendef label (tree ): return tree[0 ]def children (tree ): return tree[1 :]def is_leaf (tree ): return len (children(tree)) == 0 def set_label (tree, label ): tree[0 ] = labeldef set_children (tree, children ): tree[1 ] = childrendef double (t ): """直接在原树上修改""" set_label(t, label(t) * 2 ) if not is_leaf(t): for c in children(t): double(c)
方法一中的树为不可变的 immutable ,方法二中的是可变的 mutable
tuple 不可变,但可以修改其中的 list 中的值(因为 tuple 中存的类似于 list 的内存地址)
append()
:在 list 后添加一个元素
extend()
:在 list 后添加另一个 list 中的所有元素
pop()
:删除并返回最后一个元素
remove(x)
:删除第一个和x
相同的参数
相等 Equality 和同一 Identity
Identity: a is b
Equality: a == b
Identity 可以理解为指向同一位置的指针
迭代器 Iterator 和生成器 Generator
iter(可迭代对象)
返回一个迭代器
next(迭代器)
返回迭代器的下一个元素
L = [1 , 2 , 3 , 4 ] it1 = iter (L)next (it1) """本质上调用了__iter__()和__next__()对象""" it2 = L.__iter__() it2.__next__()
返回 iterator 的函数:
reversed(序列)
:返回相当于反迭代器
map(func,可迭代对象)
:对于每一个可迭代对象中的元素x
调用func(x)
,相当于[func(x) for x in 可迭代对象
filter(func,可迭代对象)
:返回满足func(x)
的可迭代对象中的每一个元素x
,相当于[x for x in 可迭代对象 if func(x)
sorted(可迭代对象,key=None,reverse=False)
:返回按照key
函数排序好的列表
generator 是一种 iterator,其由 generator function 生成
generator function 使用yield
代替return
def evens (): num = 0 while num < 10 : yield num num += 2 使用时:>>> evengen=evens()>>> next (evengen)0 >>> next (evengen)2 >>> next (evengen)4
generator 的优点在于只在需要的时候生成下一项
对象 Object 和类 Class
Python 中使用__
和_
给变量命名表示私有变量,但仍可强行从外部访问
继承 Inheritance 和组合 Composition
继承的声明方法:class Lion(Animal):
可使用super().__init__()
调用基类的__init__()
方法
Inheritance 表示"is-a"关系,Composition 表示"has-a"关系
特殊对象方法 Special Object Methods
Python 中所有类型都是对象,都继承自object
类
dir()
返回所有对象属性的列表
__init__(self)
方法在对象被实例化时调用,第一个参数为自身
__str__()
控制print()
的输出,str()
的转换之类
__repr__()
返回构造相同对象的字符串
getattr(对象,变量名[,默认值])
在对象中查找该名称的变量值,若没有找到,返回AttributeError
或默认值,背后调用的是__getattribute__()
方法
hasattr(对象,变量名)
在对象中查找该名称的变量值并返回是否找到,背后调用的也是__getattribute__()
还有其它的:
方法
实现
方法
实现
__setattr__(obj,"n",v)
x.n=v
__delattr__(obj,"n")
del x.n
__eq__(obj,x)
obj==x
__ne__(obj,x)
obj!=x
__ge__(obj,x)
obj>=x
__gt__(obj,x)
obj>x
__le__(obj,x)
obj<=x
__lt__(obj,x)
obj<x
__getitem__(S,k)
S[k]
__setitem__(S,k,v)
S[k]=v
__len__(S)
len(S)
__sub__(S,x)
S-x
__mul__(S,x)
S*x
复杂度 Complexity
无论 n n n 有多大,总有 K 1 g ( n ) ≤ f ( n ) ≤ K 2 g ( n ) K_1g(n) ≤ f(n) ≤ K_2g(n) K 1 g ( n ) ≤ f ( n ) ≤ K 2 g ( n ) ,记作 f ( n ) ∈ Θ ( g ( n ) ) f(n) ∈ Θ(g(n)) f ( n ) ∈ Θ ( g ( n ) ) (有的也写作 f ( n ) = Θ ( g ( n ) ) f(n) = Θ(g(n)) f ( n ) = Θ ( g ( n ) ) )
记忆化 Memoization
凑钱问题:
普通递归解法:
def count_change (amount, coins=(50 , 25 , 10 , 5 , 1 ) ): if amount == 0 : return 1 elif amount < 0 or len (coins) == 0 : return 0 else : return count_change(amount, coins[1 :]) + count_change(amount - coins[0 ], coins)
观察到有大量的重复计算,可使用记忆表 memorize table 储存已算出的值:
def count_change (amount, coins=(50 , 25 , 10 , 5 , 1 ) ): memo_table = [[-1 ] * (len (coins) + 1 ) for i in range (amount + 1 )] def count_change (amount, coins ): if amount < 0 : return 0 elif memo_table[amount][len (coins)] == -1 : memo_table[amount][len (coins)] = full_count_change(amount, coins) return memo_table[amount][len (coins)] def full_count_change (amount, coins ): if amount == 0 : return 1 elif amount < 0 or len (coins) == 0 : return 0 else : return count_change(amount, coins[1 :]) + count_change(amount - coins[0 ], coins) return count_change(amount, coins)
观察到总是 amount 小且使用 coins 少的先计算出,所以可以用循环控制顺序,即动态规划 Dynamic Programming :
def count_change (amount, coins=(50 , 25 , 10 , 5 , 1 ) ): memo_table = [[-1 ] * (len (coins) + 1 ) for i in range (amount + 1 )] def count_change (amount, coins ): if amount < 0 : return 0 return memo_table[amount][len (coins)] def full_count_change (amount, coins ): if amount == 0 : return 1 elif amount < 0 or len (coins) == 0 : return 0 else : return count_change(amount, coins[1 :]) + count_change(amount - coins[0 ], coins) for a in range (0 , amount + 1 ): memo_table[a][0 ] = full_count_change(a, ()) for k in range (1 , len (coins) + 1 ): for a in range (0 , amount + 1 ): memo_table[a][k] = full_count_change(a, coins[-k:]) return count_change(amount, coins)
泛型 Generics
鸭子类型 Duck typing 通过鸭子测试 ,即多种类型具有相同的性质,都适用于同一个函数
def sum (items, initial_value ): sum = initial_value for item in items: sum += item return sum
该函数就是一个泛型函数,只要items
满足能迭代,可相加即可
f string
:使用{变量名}
表示变量值而不是字符串
str.join(可迭代对象)
用法:
print ("\n" .join((1 ,2 )))""" 1 2 """
Scheme
Scheme 是Lisp 的一种方言
applicative programming 应用程序编程:没有副作用、破坏性操作、赋值的程序,更便于并行编程
scheme 的数据有atom 原子 和pair
atom 包括:
数字:整数、浮点、复数、有理数
symbol:类似于 string
boolean:#t,#f
空列表:()
procedure
列表表示为:(V1.(V2.(⋯(Vn.()))))
,数不尽的括号
Scheme programs are Scheme data ,都类似于(OP E1 ⋯ En)
,例如:表达式(+(* 3 7) (- x))
也是一个列表,在 Scheme 中,其已经是一棵abstract syntax tree 抽象语法树 了
quotation 引用:
scm> (+ 1 2 )3 scm> '(+ 1 2 ) (+ 1 2 ) scm> (quote (1 2 '(3 4 ))) (1 2 '(3 4 ))
其它特别的形式:
(if (> x y) x y) (define pi 3.14 ) (define (f x) (* x x)) (lambda (x y) (/ (* x x) y)) (cond ((< x 1 )'small ) (< x 3 )'medium ) (< x 5 )'large ) (#t 'big ))
对应于 python 中的:
x if x > y else y pi = 3.14 def f (x ): return x * xlambda x, y: x * x / y"small" if x < 1 else "medium" if x < 3 else "large" if x < 5 else "big"
一些表达式:
scm> (/ 3 2 )1.5 scm> (quotient 3 2 ) 1 scm> (integer? 5 ) #t scm> (= 1 (- 2 1 )) #t scm> (eqv? 1 2 ) #f
pairs:
scm> (cons 'a (cons 'b '())) (a b) scm> (define L '(a b c)) scm> (car L) a scm> (cdr L) (b c)
Let 形式:
scm> (let ((x 5 ) (y (+ x 2 ))) (+ x y)) 相当于: scm> ((lambda (x y) (+ x y)) 5 (+ x 2 ))
不可判定性 Undecidability
停机问题 halting problem 研究的是:是否存在一个「程序」,能够判断另外一个「程序」在特定的「输入」下,是会给出结果(停机),还是会无限执行下去(不停机)。
类似于理发师悖论 ,解决方法为:
"""假设有一个程序is_halt能实现该功能:""" def is_halt (program, input ) -> bool : def loop (): while (True ): pass def hack (program ): if is_halt(program, program): loop() else : return """你会发现,如果「停机程序」认为 hack(hack) 会给出结果,即 is_halt(hack, hack)返回 True ,那么实际上 hack(hack) 会进入无限循环。 而如果「停机程序」认为 hack(hack) 不会给出结果,即 is_halt(hack, hack) 返回 false,那么实际上 hack(hack) 会立刻返回结果……""" is_halt(hack, hack)
所以:程序不是万能的! ,也没有完美的防毒软件
哥德尔不完全性定理 :任意一个包含一阶谓词逻辑与初等数论的形式系统,都存在一个命题,它在这个系统中既不能被证明为真,也不能被证明为否。
宏 Macro
在 C 语言中在预编译器中进行,类似于查找替换。在 scheme 中功能更强大,相当于写了一个程序但并不执行它,其中操作数并不计算,但要注意变量名字不要和代码中的重复了。
(if (not (list? x)) (displayln x)) (define-macro (unless cond body) `(if (not ,cond) ,body)) (unless (list? x) (displayln x))
声明式编程 Declarative Programming
与之相对的是命令式编程 Imperative Programming ,注重如何实现一些计算相当于只能苦苦码字的程序员 ;而声明式编程关注结果,让计算机思考如何得到结果相当于只会下命令给员工的老板 。
正则表达式 Regular Expressions
详见:正则表达式
注意:Python 中记得在字符串之前加r
,表示为原字符串,否则\
会被转义
巴科斯范式 BNF
巴科斯范式(BNF)所描述的语法是与上下文无关的。它具有语法简单,表示明确,便于语法分析和编译的特点。
图形化表示:铁路图 Railroad Diagram
以一个算术表达式为例:
expression = term , {"+" term}; term = factor , {"*" factor}; factor = constant | variable | "(" , expression , ")"; variable = "x" | "y" | "z"; constant = digit , {digit}; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
对应的铁路图为:
SQL
结构化查询语言数据库 Structured Query Language(SQL)
多态 Polymorphism
多态指为不同数据类型的实体提供统一的接口,在 Python 中包括:
一个函数可运行在不同类的对象上
泛型函数,接受不同对象,Duck typing
强制多态 coercion ,类似于强制类型转换
类型分派 type dispatching :按照参数类型决定函数表现