CS61A

Chapter 1: Building Abstractions with Functions

开始

python 交互式会话，按下<C>-p(上一个)<C>-n(下一个)浏览历史记录
使用<C>-d退出会话并丢弃历史记录

from urllib.request import urlopen
shakespeare = urlopen('https://www.composingprograms.com/shakespeare.txt')
words = set(shakespeare.read().decode().split())
result = {w for w in words if len(w) == 6 and w[::-1] in words}
print(result)

上述代码的作用是从莎士比亚戏剧中出现的单词中找出长度为 6 且互文的单词

编程要素

导入库函数
math模块提供了各种数学函数
operator模块提供了运算符对应的函数

from math import sqrt
from operator import add, sub, mul

赋值=可以为名称绑定值，也可以绑定函数
可以在单个语句中为多个变量分配值，左右用逗号隔开

rea, circumference = pi * radius * radius, 2 * pi * radius

对于多重赋值，先对=右边的表达式求值，再和左边变量绑定，因此可以在单个语句内交换两个变量的值

x, y = 3, 4.5
y, x = x, y

纯函数和非纯函数
纯函数接受参数并返回输出
非纯函数除了返回值外，还会产生改变状态的副作用
print就是个非纯函数，返回值是None，副作用是产生输出

定义新的函数

函数定义格式：def语句、函数名、参数以及返回
函数的第二行必须进行缩进

def <name>(<formal parameters>):
    return <return expression>

抽象函数
三个核心属性：
域 domain  是它可以接受的参数集合
范围 range  是它可以返回的值的集合 意图 intent  是计算输入和输出之间的关系（以及它可能产生的任何副作用）

运算符 对于除法，Python 提供了两个运算符，/和//，前者产生浮点数，后者向下取整

>>> 5 / 4
1.25
>>> 5 // 4
1

设计函数

文档
函数定义通常包括描述函数的文档，称为“文档字符串 docstring”，它必须在函数体中缩进。文档字符串通常使用三个引号，第一行描述函数的任务，随后的几行可以描述参数并解释函数的意图：

def pressure(v, t, n):
    """计算理想气体的压力，单位为帕斯卡

	使用理想气体定律：http://en.wikipedia.org/wiki/Ideal_gas_law

	v -- 气体体积，单位为立方米
	t -- 绝对温度，单位为开尔文
	n -- 气体粒子
	"""
	k = 1.38e-23  # 玻尔兹曼常数
	return n * k * t / v

当使用函数名作为参数调用help时，会看到他的文档字符串，按 q 退出

函数默认值 可以为函数的参数提供默认值

>>> def pressure(v, t, n=6.022e23):
        k = 1.38e-23  # 玻尔兹曼常数
        return n * k * t / v

pressure函数在提供两个参数时，使用默认值，在提供三个参数时，默认值被忽略

控制

通常，Python 代码是一系列语句。简单语句是不以冒号结尾的单行，而由其他语句（简单语句和复合语句）组成被称为复合语句。复合语句通常跨越多行，以单行头部（header）开始，并以冒号结尾，其中冒号标识语句的类型。头部和缩进的句体（suite）一起称为子句。复合语句由一个或多个子句组成：

<header>:
    <statement>
    <statement>
    ...
<separating header>:
    <statement>
    <statement>
    ...
...

选择

if <expression>:
    <suite>
elif <expression>:
    <suite>
else:
    <suite>

三个基本的逻辑运算符

>>> True and False
False
>>> True or False
True
>>> not False
True

循环

while <expression>:
    <suite>

测试
断言assert验证是否符合预期，后面是一个带引号的文本行（单引号或双引号都可以，但要保持一致），如果表达式的计算结果为假值，则显示该行。

>>> assert fib(8) == 13, '第八个斐波那契数应该是 13'

文档测试（Doctests）：Python 提供了一种方便的方法，可以将简单的测试直接放在函数的文档字符串中。文档字符串的第一行应该包含函数的单行描述，接着是一个空行，下面可能是参数和函数意图的详细描述。此外，文档字符串可能包含调用该函数的交互式会话示例：

>>> def sum_naturals(n):
        """返回前 n 个自然数的和。

        >>> sum_naturals(10)
        55
        >>> sum_naturals(100)
        5050
        """
        total, k = 0, 1
        while k <= n:
            total, k = total + k, k + 1
        return total

然后，可以通过 doctest 模块来验证交互，如下。

>>> from doctest import testmod
>>> testmod()
TestResults(failed=0, attempted=2)

如果仅想验证单个函数的 doctest 交互，我们可以使用名为  run_docstring_examples  的  doctest  函数。第一个参数是要测试的函数；第二个参数应该始终是表达式  globals()  的结果，这是一个用于返回全局环境的内置函数；第三个参数  True  表示我们想要“详细”输出：所有测试运行的目录。

>>> from doctest import run_docstring_examples
>>> run_docstring_examples(sum_naturals, globals(), True)
Finding tests in NoName
Trying:
    sum_naturals(10)
Expecting:
    55
ok
Trying:
    sum_naturals(100)
Expecting:
    5050
ok

当在文件中编写 Python 时，可以通过使用 doctest 命令行选项启动 Python 来运行文件中的所有 doctest：

python3 -m doctest <python_source_file>

高阶函数

可以操作函数的函数就叫做高阶函数（接收函数作为参数，或将函数作为返回值）

def summation(n, term):
	total, k = 0, 1
	while k <= n:
		total, k = total + term(k), k + 1
	return total
def identity(x):
	return x
def sum_naturals(n):
	return summation(n, identity)
sum_naturals(10)
55

迭代改进通用方法

def improve(update, close, guess=1):
	while not close(guess):
		guess = update(guess)
	return guess

嵌套定义
上面函数update只有一个参数，万一需要两个参数，该怎么办？
思考一个问题：计算一个数的平方根，通过以下更新，值会收敛为a的平方根

def sqrt_update(x, a):
     return average(x, a/x)

但这个函数有两个参数，无法直接套到improve函数中，因此需要嵌套定义：

def sqrt(a):
	def sqrt_update(x):
		return average(x, a/x)
	def sqrt_close(x):
		return approx_eq(x * x, a)
	return improve(sqrt_update, sqrt_close)

函数作为返回值
如果给了两个基础函数f(x)和g(x),我们想要h(x) = f(g(x))

def square(x):
    return x * x

def successor(x):
    return x + 1

def compose1(f, g):
    def h(x):
        return f(g(x))
    return h

square_successor = compose1(square, successor)
result = square_successor(12)

牛顿法
牛顿法是一种迭代改进算法，用于查找返回值为 0 的数学函数的参数，它会对所有可微函数的零点的猜测值进行改造
newton_update  表示函数及其导数沿着这条切线到 0 的计算过程。

def newton_update(f, df):
	def update(x):
		return x - f(x) / df(x)
	return update

def find_zero(f, df):
	def near_zero(x):
		return approx_eq(f(x), 0)
	return improve(newton_update(f, df), near_zero)

柯里化
给定一个函数  f(x, y)，我们可以定义另一个函数  g  使得  g(x)(y)  等价于  f(x, y)。在这里，g  是一个高阶函数，它接受单个参数  x  并返回另一个接受单个参数  y  的函数
例如：pow函数的柯里化版本

>>> def curried_pow(x):
        def h(y):
            return pow(x, y)
        return h
>>> curried_pow(2)(3)
8

Lambda 表达式
可以使用 lambda 表达式临时创建函数，返回类型是一个函数

def compose1(f, g):
	return lambda x: f(g(x))

结构：

lambda              x         :              f(g(x))
"A function that    takes x   and returns    f(g(x))"

特点：简洁、直观，但难以辨认

函数装饰器

>>> def trace(fn):
        def wrapped(x):
            print('-> ', fn, '(', x, ')')
            return fn(x)
        return wrapped

>>> @trace
    def triple(x):
        return 3 * x

>>> triple(12)
->  <function triple at 0x102a39848> ( 12 )
36

相当于：

>>> def triple(x):
        return 3 * x
>>> triple = trace(triple)

多参数
如果一个函数有多个参数，我们在嵌套一个高阶函数时，可以忽略具体参数，直接用*args代替

def higher(fn, x):
	def function(*args):
		return fn(*args)

递归函数

函数调用自身
示例：分割数
求正整数分割为每部分不大于 m 的方案数
将全方案划分为两部分讨论：

1. 使用最大数 m 分割整数 n-m
2. 使用最大数 m-1 分割整数 n

def count_partitions(n, m):
    """计算使用最大 m 的整数分割 n 的方式的数量"""
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        return count_partitions(n-m, m) + count_partitions(n, m-1)

Chapter 2: Building Abstractions with Data

引言

每个值都有一个类来确定他的类型
内置的type函数可以检查任何值的类

>>> type(2)
<class 'int'>

python 包含三种原始数字类型：整数（int）、浮点数（float）和复数（complex）

TIP

不同于其他编程语言，python3 中的int值是无界的

数据抽象

Chapter 3: Interpreting Computer Programs

Chapter 4: Data Processing