CS61a编程语言课自学历程————UC Berkeley(3)

UC Berkeley CS61a自学历程和学习总结 (3)

---

Part 10 Data

Data abstraction

数据抽象的特征类似于函数抽象。当我们创建函数抽象时，函数如何实现的细节被隐藏了，而且特定的函数本身可以被任何具有相同行为的函数替换。换句话说，我们可以构造抽象来使函数的使用方式和函数的实现细节分离。与之相似，数据抽象是一种方法论，使我们将复合数据对象的使用细节与它的构造方式隔离。

数据抽象的基本概念是构造操作抽象数据的程序。也就是说，我们的程序应该以一种方式来使用数据，对数据做出尽可能少的假设。同时，需要定义具体的数据表示，独立于使用数据的程序。我们系统中这两部分的接口是一系列函数，叫做选择器和构造器，它们基于具体表示实现了抽象数据。为了演示这个技巧，我们需要考虑如何设计一系列函数来操作有理数。

数据抽象的关键基本思想在于，你可以通过它的行为来识别某种数据，而不一定是通过你如何构建它或者实现构造函数和选择器的方式

数据抽象是一种方法论，函数通过其强制在数据的表示和使用之间建立一个抽象屏障。

• An abstract data type lets us manipulate compound objects as units

• Isolate two parts of any program that uses data

  1.How data are represented(as parts)

  2.How data are manipulated(as units)

---

Data Representations

# Rational arithmetic
def add_rational(x, y):
    """Add rational numbers x and y."""
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def mul_rational(x, y):
    """Multiply rational numbers x and y."""
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def rational_are_equal(x, y):
    """Return whether rational numbers x and y are equal."""
    return numer(x) * denom(y) == numer(y) * denom(x)

def print_rational(x):
    """Print rational x."""
    print(numer(x), "/", denom(x))

# Constructor and selectors
def rational(n, d):
    """Construct a rational number x that presents n/d"""
    def select(name):
        if name = 'n':
            return n
        elif name = 'd':
            return d
    return select

def numer(x):
    """Return the numerator of rational number x."""
    return x('n')

def denom(x):
    """Return the denominator of rational number x."""
    return x('d')

>>> x, y = rational(1, 2), rational(3, 8)
>>> print_rational(mul_rational(x, y))
3 / 16
>>> x
<function rational.<locals>.select at 0x10293e6a8>
>>>

一开始就看到了这个示例，的确会很痛苦，本人第一次看的时候纯纯一头雾水，但是这个例子很好地讲述了数据封装的一些思想，我谈谈我一些粗浅的理解：

这个代码是关于有理数算术的实现，通过数据抽象的方式，将有理数的操作封装了起来。

首先看 rational(n, d) 这个函数，它是一个构造函数，用于创建有理数对象 n/d。构造函数返回的是一个内部函数 select，而 select 是用来区分有理数的分子 n 和分母 d。rational(n, d) 返回一个函数 select，这个函数保存了 n（分子）和 d（分母），它通过传入 ‘n’ 或 ‘d’ 来分别获取分子和分母的值。这里的 select 函数隐藏了具体的分子和分母的存储方式，外界无法直接访问 n 和 d，只能通过选择器 numer 和 denom 来访问。

numer 和 denom 函数是用来获取有理数的分子和分母的选择器：numer(x) 会调用 x(‘n’)，即调用 rational 返回的 select 函数来获取分子 n。
denom(x) 类似地会获取分母 d。它让我们可以通过 numer 和 denom 来访问有理数的组成部分，而不必关心 rational 内部是如何存储这些信息的。

接下来，add_rational、mul_rational 和 rational_are_equal 是关于有理数的基本运算，它们都基于对分子和分母的操作，这个比较简单，但要记住返回值都要返回分子和分母的选择器。

print_rational(x) 是一个简单的打印函数，用来显示有理数的格式。

这个例子展示了数据抽象的关键思想：分离数据的表示和操作。通过 rational 函数创建有理数对象，隐藏了内部的实现细节（例如分子和分母的存储），而 numer 和 denom 这些选择器让我们可以在不关心细节的情况下操作有理数。这种抽象使得程序更加模块化，并且方便后续修改有理数的表示方式，而无需改变对它的操作。

（总而言之我觉得这里是个难点了，我看视频看了好多遍）

---

Abstraction Barriers

Implementation of lists

Parts of the program that…	Treat rationals as…	Using
Use rational numbers to perform computation	whole data values	add_rationals, mul_rationals, rationals_are_equal, print_rational
Create rational or implement rational operations	numerators and denominators	rational, numer, denom
Implement selectors and constructor for rationals	two-element lists	list literals and element selection

---

Pairs

A pair consists of two values that joined together, bundled together in such a way that you can treat them as a unit, as a whole, even though there are two pairs.

Representing Pairs Using lists

• “Unpacking”a list

pair = [1, 2]
>>> pair
[1, 2]
>>> x, y = pair
>>> x
1
>>> y
2

• Element selection using the selection operator

>>> pair[0]
1
>>> pair[1]
2

• Element selection function

>>> from operator import getitem
>>> getitem(pair, 0)
1
>>> getitem(pair, 1)
2

---

Part 11: Trees

Trees are an important data abstraction for representing hierarchical relationships

树是表示层次关系的重要数据抽象

• Recursive description(wooden trees)

  1. A tree has a root label and a list of branches
  2. Each branch is a tree
  3. A tree with zero branches is called a leaf

• Relatiove desciption(famliy trees)

  1. Each location in a tree is called a node
  2. Each node has a label that can be any value
  3. One node can be the parent/child of another

---

Implementing the Tree Abstraction

# Trees

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree)：
    return tree[0]

def branches(tree)
    return tree[1:]

def is_tree:
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch)
            return False
    return True

def is_leaf(tree):
    return not branches(tree)

---

Tree Processing

Functions that take trees as input or return trees as output are often tree recursive themselves

作为输入或者输出的函数通常本身是tree递归的。

def fib_tree(n):
    if n <= 1:
        return tree(n)
    else:
        left, right = fib_tree(n-2), fib_tree(n-1)
        return tree(label(left) + label(right), [left, right])

def count_leaves(t):
    """Count the leaves of tree T."""
    if is_leaf(t):
        return 1
    else:
        return sum([count_leaves(b) for b in branches(t)])

---

Discussion Question

Implement leaves, which returns a list of the leaf lables of a tree

Hint: If you sum a list of lists, you get a list containing the elements of those lists

ex: sum的特性

>>> sum([ [1], [2, 3], [4]], [])
[1, 2, 3, 4]
>>> sum([ [1] ], [])
[1]

实施部分：不包含树的根标签

def leaves(tree):
    """Return a list containing the leaf lables of tree."""

>>> leaves(fib_tree(5))
[1, 0, 1, 0, 1, 1, 0, 1]
"""
    if is_leaf(tree):
        return [label(tree)]
    else:
        return sum(leaves(b) for b in branches(tree), [])

---

Creating Trees

A function that creates a tree from another tree is typically also recursive

def increment_leaves(t):
    """Return a tree like t but with leaf lables incremented."""
    if is_leaf(t):
        return tree(label(t) + 1)
    else:
        bs = [increment_leaves(b) for b in branches(t)]
        return tree(label(t), bs)

def increment(t):
    """Return a tree like t but with all labels incremented"""
    return tree(label(t) + 1, [increment(b) for b in branches(t)])

这是一行代码，返回一棵树，其中我们已经递增了标签，并且递增了所有分支中的所有标签。

关于树的内容就写到这里吧，这部分对我而言目前有点困难，浅尝辄止了属于是。

---

Part 12: Mutablity

object

• Objects represent information
• They consist of data and behavior, bundled together to create abstractions
• Objects can represent things, but also properties, interactions, & processes.
• A type of object is called a class; classes are first-class values in Python.
• Object-oriented programming:
  1. A metaphor for organizing large programs
  2. Special syntax that can improve the composition of programs
• In Pyhon, every value is an object
  1. All objects have attributes
  2. A lot of data manipulation happens through object methods
  3. Functions do one thing; objects do many related things

ex: Strings:

>>> s = 'Hello'
>>> s.upper()
'HELLO'
>>> s.lower()
'hello'
>>> s.swapcase()
'hELLO'
>>> s
'Hello'
>>>

原课程中还讲到了一些编码的知识，如果ASCII码和Unicode，包括一些相关的编程语法，如

from unicodedata import name, lookup

在此省略

---

Mutation Operations –变异算子

ex: 一个关于扑克牌的故事

• Some Object Can Change

>>> suits = ['coin', 'string', 'myriad']
>>> original_suits = suits
>>> suits.pop
<built-in method pop of list object at 0x000002501097D1C0>
>>> suits.pop()
'myriad'
>>> suits.remove('string')
>>> suits
['coin']
>>> suits.append('cup')
>>> suits.extend(['sword', 'club'])
>>> suits
['coin', 'cup', 'sword', 'club']
>>> suits[2] = 'spade'
>>> suits[0:2] = ['heart', 'diamond']
>>> suits
['heart', 'diamond', 'spade', 'club']
>>> original_suits
['heart', 'diamond', 'spade', 'club']
>>>

• This is the first example in the course of an object changing state

• The same object can change in value throughout the course of computation

• All name that refer to the same object are affected by a mutation

• Only objects of mutable types can change: list & dictionaries

• ps: 在计算机科学中，变异是一个词，它在对象发生变化的时候使用

ex: dictionary

>>> numerals = {'I' : 1, 'V' : 5, 'X' : 10}
>>> numerals
{'I': 1, 'V': 5, 'X': 10}
>>> numerals['X'] 
10
>>> numerals['X'] = 11
>>> numerals['X']      
11
>>> numerals      
{'I': 1, 'V': 5, 'X': 11}
>>> numerals['L'] = 50
>>> numerals      
{'I': 1, 'V': 5, 'X': 11, 'L': 50}
>>> numerals['L']      
50
>>> numerals.pop('X')
11
>>> numerals.get('X') 
>>> numerals          
{'I': 1, 'V': 5, 'L': 50}
>>>

Mutation Can Happen Within a Function Call

• A function can change the value of any object in its scope

---

Tuples – 元组

元组是序列，但它们是不可变的序列，意味着它们无法再被更改

Immutable values are protected from mutation

>>> turtle = (1, 2, 3)
>>> ooze() #Next lecture: ooze can change turtle's binding
>>> turtle
(1, 2, 3)

字符串，元组都是不可改变的值，唯一可变的值是列表

---

Mutable Function

withdraw from bank

def make_withdraw_list(balance):
    b = [balance]
    def withdraw(amount):
        if amount > b[0]
            return 'Insufficient funds'
    b[0] = b[0] - amount
    return b[0]
return withdraw

withdraw = make_withdraw_list(100)
withdraw(25)

---

Part 13 Iterators

A container can provide an iterator that provides access to its elements in some order

iter(iterable):Return an iterator over the elements of an iterable value.

next(iterator):Return the next element in an iterator

>>> s = [[1, 2], 3, 4, 5]
>>> s
[[1, 2], 3, 4, 5]
>>> next(s)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'list' object is not an iterator
>>> t = iter(s)
>>> next(t)
[1, 2]
>>> next(t)
3
>>> list(t)
[4, 5]
>>> next(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

---

Dictionary iteration

>>> d = {'one': 1, 'two': 2, 'three': 3}
>>> d['zero'] = 0
>>> k = iter(d.key()) # or iter(d)
>>> v = iter(d.values())
>>> i = iter(d.items())

然后我们就可以通过next函数，分别来遍历字典的键、值、键值对这些内容。补充一点，如果我们已经构建了迭代器，如果我们在这个字典中新增或删减一个键值对(item),那么我们将无法进行next的遍历，因为整个字典的结构已经被破坏了，我们必须构造一个新的字典迭代器。但是如果我们只是改变了字典当中某一个键的值，我们依然可以使用这个字典迭代器进行next的遍历，因为整个字典的结构没有发生变化。

---

For Statements

先说结论，如果我在for语句中使用迭代器，我仍然可以遍历所有元素直达到末尾，但这会推进迭代器，使得我不能再次使用它，另外一方面，如果我使用的是可迭代对象，比如范围本身，在for语句中每次使用它时，我可以从头到尾遍历整个内容而不用担心任何的变化

>>> r = range(3, 6)
>>> ri = iter(r)
>>> for i in ri:
...     print(i)
...
3
4
5
>>> for i in r:
...     print(i)
...
3
4
5
>>> for i in ri:
...     print(i)
...
>>>

---

Built-In Iterator Function

Many built-in Python sequence operations return iterators that compute results lazily

都不会直接返回所有的值，而是会返回一个迭代器

• map(func, iterable): Iterate over func(x) for x in iterable
• filter(fun, iterable): Iterate over x in iterable if func(x)
• zip(first_iter, second_iter): Iterate over co-indexed (x, y) pairs
• reversed(sequence): Iterate over x in a sequence in reverse order

To view the contents of an iterator, place the resulting elements into a container

• list(iterable): Create a list containing all x in iterable
• tuple(iterable): Create a tuple containing all x in iterable
• sorted(iterable): Create a sorted list containing x in iterable

>>> def double(x):
...     print('**', x, '=>', 2*x, '**')
...     return 2*x
...
>>> m = map(double, range(3, 7))
>>> f = lambda y: y >= 10
>>> t = filter(f, m)
>>> next(t)
** 3 => 6 **
** 4 => 8 **
** 5 => 10 **
10
>>> next(t)
** 6 => 12 **
12
>>> list(t)
[]
>>> list(filter(f, map(double, range(3, 7))))
** 3 => 6 **
** 4 => 8 **
** 5 => 10 **
** 6 => 12 **
[10, 12]

• map(double, range(3, 7)) 是惰性迭代器，只有在需要时才会逐个计算。
• filter(f, m) 通过 f 来筛选 m 中符合条件的值，也是惰性求值的。
• 当通过 next() 消费迭代器时，元素是逐个计算并传递的。
• 当 list() 被调用时，迭代器会被完全消费，所有值都被计算。
• 在list(filter(f, map(double, range(3, 7))))中，map(double, range(3, 7)) 和 filter(f, …) 是一条连续的管道，直接将所有结果都传递给 list()。由于 list() 会遍历所有元素，map 和 filter 都会立即完全计算。与之前的操作不同，这次 list() 强制计算所有元素，结果是 [10, 12]，符合 f(y) 的条件的值会被保留

懒惰计算主要是为了方便，因为它允许你指定如何计算大量的值，但如果你实际上不需要所有这些值，那么你就不必计算它们

The Zip function

>>> list(zip([1, 2], [3, 4]))
[(1, 3), (2, 4)]
>>> list(zip([1, 2], [3, 4, 5]))  
[(1, 3), (2, 4)]
>>> list(zip([1, 2], [3, 4, 5], [6, 7])) 
[(1, 3, 6), (2, 4, 7)]

Implement palindrome, which returns whether s is the same forward and backward

有两种方法可以实现

def palindrome(s):
    """Return whether s is the same backward and forward.

    >>> palindrome([3, 1, 4, 1, 5])
    False
    >>> palindrome([3, 1, 4, 1, 3])
    True
    >>> palindrome('seveneves')
    True
    >>> palindrome('seven eves')
    False
    """
    return list(s) == list(reversed(s))

def palindrome(s):
    """Return whether s is the same backward and forward.

    >>> palindrome([3, 1, 4, 1, 5])
    False
    >>> palindrome([3, 1, 4, 1, 3])
    True
    >>> palindrome('seveneves')
    True
    >>> palindrome('seven eves')
    False
    """
    return all([a == b for a, b in zip(s, reversed(s))])

---

Generators

A generator is a special kind of iterator,just like a map object is a special kind of iterator.

def plus_minus(3):
    yield x
    yield -x

>>> t = plus_minus(x)
>>> next(t)
3
>>> next(t)
-3

When a generator function is called, it returns a generator, and that generator iterates over the yields of the function.

A yield from statement yields all values from an iterator or iterable.

>>> list(a_then_b([3, 4], [5, 6]))
[3, 4, 5, 6]

def a_then_b(a, b):
    yield from a
    yield from b

def countdown(k):
    if k > 0:
        yield k
        yield from countdown(k-1)
    else:
        yield 'Blast off'

def prefixex(s):
    if s:
        yield from prefixex(s[:-1])
        yield s

def subsrings(s):
    if s:
        yield from profixex(s)
        yield from substrings(s[1:])

Part 14: Object-Oriented Programming–面向对象编程

前面在讲述变异这一章节的时候，就已经谈到过对象了，但是由于面向对象编程太重要了，还是有必要单独拿一个章节来讲

我们需要将非常复杂的大型程序组织成为很小的模块化组件，这样就可以分别编写、测试和思考，因为人类一次只能处理这么多的复杂性问题。

A method for organizing programs

• Extends data abstraction
• Bundles together information and related behavior

A metaphor for computation using distributed state

• Each object has its own local state
• Each object also knows how to manage its own local state
• Interact with an object using its methods
• Several objects may all be instances of a common class
• Different classes may relate to each other

Specialized syntax & vocabulary to support this metaphor

• A class defines how objects of a particular type behave
• A objects is an instance of a class; the class is its type
• A method is a function called on an object using a dot expression: s.append(5)

Example:Lists

The built-in list function is a class

>>> list
<class 'list'>

Calling list on an iterable creates a new list object

>>> s = list(range(3))
>>> s
[0, 1, 2]
>>> types(s)
<class 'list'>

The list class defines how everything about how lists work:

• Methods append, extend, insert, pop, remove, etc
• Addition and multiplication: s + t
• Item lookup and assignment: s[0] = s[3]

---

Class Statements

A class describes the behavior of its instances

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

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

    def withdraw(self, amount):
        if amount > self.balance:
            return 'Insufficient funds'
        self.balance = self.balance - amount
        return self.balance

---

Object Identity

Every object that is an instance of a user-defined class has a unique identity

>>> a = Account('John')
>>> b = Account('Jack')
>>> a.balance
0
>>> b.holder
'Jack'

Identity operators “is” and “is not” test if two expressions evaluate to the same object

>>> a is a
True
>>> a is not b
True

Binding an object to a new name using assignment does not create a new project.

---

Class Attributes

A class statement creates a new class and binds that class to name in the first frame of the current environment.

class <name>:
    <suite>

Assignment & def statements in suite creat attributes of the class(not names in frames)

Class attributes are “shared” across all instances of a class because they are attributes of the class, not the instance.

---

Attribute Lookup

Both instances and classes have attributes that can be looked up by dot expressions.

To evaluate a dot expression:

• Evaluate the expression to the left of the dot, which yields the object of the dot expression
• name is matched against the instance attributes of that object; if can attribute with that name exists, its value is returned
• If not, name is looked up in a class, which yields a class attribute value
• That value is returned unless it is a function, in which case a bound method is returned instead

>>> tom_account.balance
10
>>> getattr(tom_account, 'balance')
10
>>> hasattr(tom_account, 'deposit')
True

---

Attribute assignment

这一部分的核心在于你要搞清楚你是对整个类的属性进行更改还是对实例的属性进行更改。实例属性更改的优先级更高。

---

Method Calls

Calling or invoking a method on an object is the primary way to interact with an object

在对象上调用或调用方法是与对象交互的主要方式。

---

Bound Methods

Object + Function = Bound Method

>>> type(Account.deposit)
<class 'function'>
>>> type(tom_account.deposit)
<class 'method'>

>>> Account.deposit(tom_account, 1001)
1011
>>> tom_account.deposit(1007)
2018

-------------本文结束感谢您的阅读-------------

本文作者： Arua
本文链接： https://blog.visionary-5.top/2024/09/06/CS61A%E7%BC%96%E7%A8%8B%E8%AF%AD%E8%A8%80%E8%AF%BE%E8%87%AA%E5%AD%A6%E5%8E%86%E7%A8%8B(3)/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

如果给你带来一点启发，可以请我喝一杯下午茶吗？

支付宝