大四临近毕业，为了将来留美找工作，我准备跟一些比较著名的CS神课，来打下CS基础。目前在跟的是UCBerkely CS61A，这门课是为CS初学者准备的，不过没一点基础可能接受起来比较吃力，使用语言为Python。现在开始写一些课堂笔记之类的，巩固知识用，主要是一些Python的奇技淫巧。
Lecture 1
What is this course about?
A course about managing complexity:
§ Mastering abstraction: Giving a complex system a name and thinking it as a whole without worrying about details.
§ Programming paradigms
operator (operand, operand)
>>> add (2, 3)
# 长度为四，正反相同的单词
>>> {w for w in words if w == w [::-1] and len(w) ==4}
Lecture 2
# swap(a, b) can be written as:
>>> a, b = 1, 2
>>> a, b = b, a
(a, b) = (2, 1)
Every expression is evaluated in the context of an environment.
So far, the current environment is either:
• The global frame alone, or
• A local frame, followed by the global frame.
An environment is a sequence of frames.
A name evaluates to the value bound to that name in the earliest frame of the current environment in which that name is found.
>>> def square(square):
>>> return mul(square, square)
>>> square(4)
16
Pure Functions & Non-Pure Functions
Some functions just return values, for which we call Pure-Function. Some not, they have "side effects" like "print", we call them Non-Pure Function.
# print() function returns None
>>> print (print(1), print(2))
1
2
None, None
Lecture 3
In Python, there is an easy way to diff global and local frame:
stuff not indented -> global frame
stuff indented -> local frame
>>> 2 + 3 * 4 + 5
>>> add(add(2, mul(3, 4)), 5)
>>> (2 + 3) * (4 + 5)
>>> mul(add(2, 3), add(4, 5))
Python的一些除法运算：
>>> 2015 / 10 # truediv
201.5
>>> 2015 // 10 # floordiv
201
>>> 2015 % 10 # mod
5
这是一个很好的方法用来展示函数的功能，开头写一串示例，这个蛮神奇的。
def divide_exact(n, d):
"""Return the quotient and remainder of dividing N by D.
>>> q, r = divide_exact(2015, 10)
>>> q
201
>>> r
5
"""
return n // d, n % d
然后在终端调试，如果正确，终端就pass；如果错误，会报错：
''' ex.py is the filename of divide_exact '''
python -i ex.py # Python interactive model
python -m doctest ex.py
Lecture 4
Fibonacci sequence, which is one of the most famous example for iteration.
''' Compute the nth Fibonacci number, for N >= 1. '''
def fib(n):
pred, curr = 0, 1
k = 1
while k < n:
pred, curr = curr, pred + curr
return curr
A Guide to Designing Function:
•Give each function exactly one job. If a function has two jobs, it should be two functions.
•Don’t repeat yourself (DRY). Implement a process just once, but execute it many times.
•Define functions generally. The function shouldn't solve all problems but problem that are the same kind.
Generalization.
Generalizing patterns with arguments: Finding common structure allows for shared implementation.
def area(r, shape_constant):
# if r <= 0, the terminal will report error
assert r > 0, 'A length must be positive'
return r * r * shape_constant
def area_square(r):
return area(r, 1)
def area_circle(r):
return area(r, pi)
Generalizing over computational processes: The common structure among functions may be a computational process, rather than a number.
def identity(k):
return k
def cube(k):
return pow(k, 3)
def summation(n, term):
total, k = 0, 1
while k <= n:
total, k = total + term(k), k + 1
return total
Locally Defined Functions
Functions defined within other function bodies are bound to names in a local frame.
def make_adder(n):
def adder(k):
return n + k
return adder
>>> f = make_adder(3)
>>> f(4)
7
>>> make_adder(2010)(5)
2015
Lecture 5
Environments Enable Higher-Order Functions
Functions are first-class: Functions are values in our programming language
Higher-order function: A function that takes a function as an argument value or A function that returns a function as a return value
def apply_twice(f, x):
return f(f(x))
def square(x):
return x * x
>>> apply_twice(square, 4)
256
Local Names are not Visible to Other (Non-Nested) Functions:
def f(x, y):
return g(x)
def g(a):
return a + y
>>> f(1, 2)
Error: 'y' is not defined.
Function Composition
def square(x):
return x * x
def make_adder(n):
def adder(k):
return k + n
return adder
def compose(f, g):
def h(x):
return f(g(x))
return h
>>> compose(square, make_adder(2))(3)
25
Lambda Expressions
>>> square = lambda x: x * x
>>> square(10)
100
Lecture 6
Recursion
Sum digits without a while statement
def split(n):
return n // 10, n % 10 # split(2015) -> 201, 5
def sum_digits(n):
if n < 10: # base case
return n
else:
all_but_last, last = split(n)
return sum_digits(all_but_last) + last # recursive calls
Iteration vs Recursion
The recursion uses less names than the iteration function
def fact_iter(n): # using while
total, k = 1, 1
while k <= n:
total, k = total * k, k + 1
return total
def fact(n): # using recursion
if n == 0:
return 1
else:
return n * fact(n - 1)
The Luhn Algorithm
An algorithm to check whether a credit card number is right
def luhn_sum(n):
if n < 10:
return n
else:
all_but_last, last = split(n)
return luhn_sum_double(all_but_last) + last
def luhn_sum_double(n):
all_but_last, last = split(n)
luhn_digit = sum_digits(last * 2)
if n < 10:
return luhn_digit
else:
return luhn_sum(all_but_last) + luhn_digit
Lecture 7
The Cascade Function: Figure out the orders of function call
def cascade(n):
if n < 10:
print(n)
else:
print(n)
cascade(n // 10)
print(n)
>>> cascade(123)
123
12
1
12
123
Inverse Cascade
def inverse_cascade(n):
grow(n)
print(n)
shrink(n)
def f_then_g(f, g, n):
if n:
f(n)
g(n)
grow = lambda n: f_then_g(grow, print, n // 10)
shrink = lambda n: f_then_g(print, shrink, n //10)
>>> inverse_cascade(123)
1
12
123
12
1
Tree Recursion
from ucb import trace
# This is a function decorator.
# @trace can show every step when the function calls.
@trace
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
Counting Partitions
The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.
def count_partition(n, m):
if n == 0:
return 1
elif n < 0:
return 0
elif m == 0:
return 0
else:
with_m = count_partition(n - m, m)
without_m = count_partition(n, m -1)
return with_m + without_m
Lecture 10
Sequence Unpacking in For Statements
>>> pairs = [[1, 2], [2, 2], [3, 2], [4, 4]]
for x,y in pairs: # x,y = 1,2; 2,2; 3,2; 4,4
if x == y:
count += 1
def cheers():
# '_' tells other programmers that the name doesn't matter
for _ in range(3):
print('Cheers!')
>>>cheers()
'Cheers!'
'Cheers!'
'Cheers!'
List Comprehensions
>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'm', 'n', 'o', 'p']
>>> [letters[i] for i in [3, 4, 6, 8]]
['d', 'e', 'm', 'o']
def divisors(n):
return [1] + [x for x in range(2, n) if n % x == 0]
String
>>> 'curry = lambda f: lambda x: lambda y: f(x, y)'
# 'exec' function:
>>> exec('curry = lambda f: lambda x: lambda y: f(x, y)')
>>> curry(pow)(2)(4)
16
Dictionary
>>> dict([('X', 10), ('V', 5)])
{'X': 10, 'V': 5}
Lecture 11
Tree Abstraction
def tree(root, branches=[]):
for branch in branches:
assert is_tree(branch):
return [root] + list(branches)
>>> tree(3, [tree(1, tree(2, [tree(1), tree(1)])])
>>> [3, [1], [2, [1], [1]]]
def root(tree):
return tree[0]
def branches(tree):
return tree[1:]
def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(trees):
if not is_tree(branch):
return False
return True
def is_leaf(tree);
return not branches(tree)
Fibonacci Tree
def fib_tree(n):
if n == 0 or n == 1:
return tree(n)
else:
left, right = fib_tree(n-1), fib_tree(n - 2)
fib_n = root(left) + root(right)
return tree(fib_n, [left, right])
Tree Processing Using Recursion
def count_leaves(tree):
"""Count the leaves of a tree."""
if is_leaf(tree):
return 1
else:
branch_counts = [count_leaves(b) for b in tree]
return sum(branch_counts)
def leaves(tree):
"""Return a list containing the leaves of a tree."""
if is_leaf(tree):
return [root(tree)]
else:
return sum([leaves(b) for b in branches(tree)], [])
Partition Tree
def partition_tree(n, m):
if n == 0:
return tree(True)
elif n < 0 or m == 0:
return tree(False)
else:
left = partition_tree(n - m, m)
right = partition_tree(n, m - 1)
return tree(m, [left, right])
def print_parts(tree, partition= []):
if is_leaf(tree):
if root(tree):
print(partition)
else:
left, right = branches(tree)
print_parts(left, partition+[root(tree)])
print_parts(right, partition)
To be continued...
