Week9-Lecture22-24

2026-09-272026-09-27

Lecture 22 Composition¶

Lab 07 Linked list, Inheritance¶

Python
from __future__ import annotations


class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.first = 5
    >>> s.rest.first = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    (5 7 (8 9))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '('
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + ')'


class Account:
    """An account has a balance and a holder.

    >>> a = Account('John')
    >>> a.deposit(10)
    10
    >>> a.balance
    10
    >>> a.interest
    0.02
    >>> a.time_to_retire(10.25)  # 10 -> 10.2 -> 10.404
    2
    >>> a.balance                # Calling time_to_retire method should not change the balance
    10
    >>> a.time_to_retire(11)     # 10 -> 10.2 -> ... -> 11.040808032
    5
    >>> a.time_to_retire(100)
    117
    """
    max_withdrawal: int = 10
    interest: float = 0.02

    def __init__(self, account_holder: str):
        self.balance = 0
        self.holder = account_holder

    def deposit(self, amount: int) -> int:
        self.balance = self.balance + amount
        return self.balance

    def withdraw(self, amount: int) -> int | str:
        if amount > self.balance:
            return "Insufficient funds"
        if amount > self.max_withdrawal:
            return "Can't withdraw that amount"
        self.balance = self.balance - amount
        return self.balance

    def time_to_retire(self, amount: float) -> int:
        """Return the number of years until balance would grow to amount."""
        assert self.balance > 0 and amount > 0 and self.interest > 0
        years = 0
        b = self.balance
        while b < amount:
            b *= (1 + self.interest)
            years += 1
        return years


class FreeChecking(Account):
    """A bank account that charges for withdrawals, but the first two are free!

    >>> ch = FreeChecking('Jack')
    >>> ch.balance = 20
    >>> ch.withdraw(100)  # First one's free. Still counts as a free withdrawal even though it was unsuccessful
    'Insufficient funds'
    >>> ch.withdraw(3)    # Second withdrawal is also free
    17
    >>> ch.balance
    17
    >>> ch.withdraw(3)    # Now there is a fee because free_withdrawals is only 2
    13
    >>> ch.withdraw(3)
    9
    >>> ch2 = FreeChecking('John')
    >>> ch2.balance = 10
    >>> ch2.withdraw(3) # No fee
    7
    >>> ch.withdraw(3)  # ch still charges a fee
    5
    >>> ch.withdraw(5)  # Not enough to cover fee + withdraw
    'Insufficient funds'
    """
    withdraw_fee: int = 1
    free_withdrawals: int = 2

    def __init__(self, account_holder: str):
        super().__init__(account_holder)
        self.free = self.free_withdrawals

    def withdraw(self, amount: int) -> int | str:
        self.free -= 1
        if self.free < 0:
            amount += self.withdraw_fee
        return super().withdraw(amount)


def without(s: Link, i: int) -> Link:
    """Return a new linked list like s but without the element at index i.

    >>> s = Link(3, Link(5, Link(7, Link(9))))
    >>> without(s, 0)
    Link(5, Link(7, Link(9)))
    >>> without(s, 2)
    Link(3, Link(5, Link(9)))
    >>> without(s, 4)  # There is no index 4, so all of s is retained.
    Link(3, Link(5, Link(7, Link(9))))
    """
    def helper(s, index, i):
        if s is Link.empty:
            return s
        if index == i:
            return s.rest
        else:
            return Link(s.first, helper(s.rest, index + 1, i))
    return helper(s, 0, i)


def duplicate_link(s: Link, val: int) -> None:
    """Mutates s so that each element equal to val is followed by another val.

    >>> x = Link(5, Link(4, Link(5)))
    >>> duplicate_link(x, 5)
    >>> x
    Link(5, Link(5, Link(4, Link(5, Link(5)))))
    >>> y = Link(2, Link(4, Link(6, Link(8))))
    >>> duplicate_link(y, 10)
    >>> y
    Link(2, Link(4, Link(6, Link(8))))
    >>> z = Link(1, Link(2, Link(2, Link(3))))
    >>> duplicate_link(z, 2) # ensures that back to back links with val are both duplicated
    >>> z
    Link(1, Link(2, Link(2, Link(2, Link(2, Link(3))))))
    """
    if s is Link.empty:
        return
    elif s.first == val:
        s.rest = Link(s.first, s.rest)
        duplicate_link(s.rest.rest, val)
    else:
        duplicate_link(s.rest, val)
    # 已经完全适应递归了

Lecture 23 Decomposition¶

Disc 08 Linked list¶

Python
from __future__ import annotations


class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    >>> s = Link(2, Link(3, Link(4)))
    >>> s.first = 5
    >>> s.rest.first = 6
    >>> s.rest.rest = Link.empty
    >>> s                                    # Displays the contents of repr(s)
    Link(5, Link(6))
    >>> s.rest = Link(7, Link(Link(8, Link(9))))
    >>> s
    Link(5, Link(7, Link(Link(8, Link(9)))))
    >>> print(s)                             # Prints str(s)
    (5 7 (8 9))
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '('
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + ')'

def strange_loop():
    """Return a Link s for which s.rest.first.rest is s.

    >>> s = strange_loop()
    >>> s.rest.first.rest is s
    True
    """
    s = Link(1, Link(Link(2)))
    s.rest.first.rest = s
    return s

def sum_rec(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_rec(a, 2)
    7
    >>> sum_rec(a, 5)
    15
    >>> sum_rec(Link.empty, 1)
    0
    """
    # Use a recursive call to sum_rec; don't call sum_iter
    if s is Link.empty:
        return 0
    if k == 0:
        return 0
    else:
        return s.first + sum_rec(s.rest, k - 1)


def sum_iter(s, k):
    """Return the sum of the first k elements in s.

    >>> a = Link(1, Link(6, Link(8)))
    >>> sum_iter(a, 2)
    7
    >>> sum_iter(a, 5)
    15
    >>> sum_iter(Link.empty, 1)
    0
    """
    result = 0
    while k != 0 and s is not Link.empty:
        result += s.first
        k -= 1
        s = s.rest
    return result

def overlap(s, t):
    """For increasing s and t, count the numbers that appear in both.

    >>> a = Link(3, Link(4, Link(6, Link(7, Link(9, Link(10))))))
    >>> b = Link(1, Link(3, Link(5, Link(7, Link(8)))))
    >>> overlap(a, b)  # 3 and 7
    2
    >>> overlap(a.rest, b)  # just 7
    1
    >>> overlap(Link(0, a), Link(0, b))
    3
    """
    total = 0
    while s is not Link.empty and t is not Link.empty:
        if s.first == t.first:
            total += 1
            s = s.rest
            t = t.rest
        elif s.first > t.first:
            t = t.rest
        else:
            s = s.rest

    return total

def iterate_in_order(s, t):
    """For increasing s and t, yields the elements in s and t, in non-decreasing order.

    >>> a = Link(3, Link(4, Link(6, Link(7, Link(9, Link(10))))))
    >>> b = Link(1, Link(3, Link(5, Link(7, Link(8)))))
    >>> t = iterate_in_order(a, b)
    >>> for item in t:
    ...     print(item)
    1
    3
    3
    4
    5
    6
    7
    7
    8
    9
    10
    >>> t = iterate_in_order(Link.empty, b)
    >>> for item in t:
    ...      print(item)
    1
    3
    5
    7
    8
    """
    while s is not Link.empty or t is not Link.empty:
        if s is Link.empty:
            yield t.first
            t = t.rest
        elif t is Link.empty or s.first <= t.first:
            yield s.first
            s = s.rest
        else:
            yield t.first
            t = t.rest

Lecture 24 Efficiency¶

Reading 2.8 Efficiency¶

2.8.1 Measuring efficiency¶

更可靠的描述程序效率的方法是测量某个事件发生的次数

Python
>>> def fib(n): # 又回到最初的起点
        if n == 0:
            return 0
        if n == 1:
            return 1
        return fib(n-2) + fib(n-1)

>>> fib(5)
5

>>> def count(f): # 一个度量函数调用次数的高阶函数
        def counted(*args):
            counted.call_count += 1
            return f(*args)
        counted.call_count = 0
        return counted
        
>>> fib = count(fib)
>>> fib(19)
4181
>>> fib.call_count
13529

另一方面，我们还有知道函数调用占用的空间

Python
>>> def count_frames(f):
        def counted(*args):
            counted.open_count += 1
            counted.max_count = max(counted.max_count, counted.open_count)
            result = f(*args)
            counted.open_count -= 1
            return result
        counted.open_count = 0
        counted.max_count = 0
        return counted
        
>>> fib = count_frames(fib)
>>> fib(19)
4181
>>> fib.open_count
0
>>> fib.max_count
19
>>> fib(24)
46368
>>> fib.max_count
24

2.8.2 Memorization¶

记忆化函数会存储它之前接收过的任何参数对应的返回值。

Python
# 记忆化很容易写成高阶函数/装饰器
>>> def memo(f):
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized

>>> counted_fib = count(fib)
>>> fib  = memo(counted_fib)
>>> fib(19)
4181
>>> counted_fib.call_count
20
>>> fib(34)
5702887
>>> counted_fib.call_count
35

2.8.3 Orders of Functions¶

我们很难精确描述一个函数需要调用的次数和占用的空间，因此我们使用增长阶描述。我们只关注它怎么增长（增长的数量级）

R(n) 可以衡量所使用的内存量、执行的基本机器步骤数
Θ 表示法。设 n 是衡量某个过程输入规模的参数，并设 R(n) 是该过程处理规模为 n 的输入时所需的某种资源的量。

2.8.4 Example: Exponentiation¶

Python
>>> def exp(b, n):
        if n == 0:
            return 1
        return b * exp(b, n-1)

# 线性递归的过程，可以转化成循环，需要 Θ(n) 步和 Θ(n) 空间
>>> def exp_iter(b, n):
        result = 1
        for _ in range(n):
            result = result * b
        return result

# 优化, Θ(logn) 增长
>>> def square(x):
        return x*x
>>> def fast_exp(b, n):
        if n == 0:
            return 1
        if n % 2 == 0:
            return square(fast_exp(b, n//2))
        else:
            return b * fast_exp(b, n-1)

2.8.5 Growth Categories¶

了解并识别常见增长阶是很重要的。

常数项不影响过程的增长量级。
对数的底不影响过程的增长量级。
嵌套。当一个内层计算过程在外层过程的每一步中重复时，整个过程的增长量级是外层过程与内层过程步数的乘积。

Python
# 该函数的总增长阶为 Θ(m⋅n)
>>> def overlap(a, b):
        count = 0
        for item in a:
            if item in b:
                count += 1
        return count

>>> overlap([1, 3, 2, 2, 5, 1], [5, 4, 2])
3

在一个求和中，除增长最快的项外，其他所有项都可以省略，而不会改变增长阶。

Category	Theta Notation	Growth Description	Example
Constant	Θ(1)	Growth is independent of the input	abs
Logarithmic	Θ(logn)	Multiplying input increments resources	fast_exp
Linear	Θ(n)	Incrementing input increments resources	exp
Quadratic	Θ(n2)	Incrementing input adds n resources	one_more
Exponential	Θ(bn)	Incrementing input multiplies resources	fib