Skip to content

Latest commit

 

History

History
209 lines (133 loc) · 6.06 KB

2.3SymbolicData.md

File metadata and controls

209 lines (133 loc) · 6.06 KB

2.3 Symbolic Data

原书目录

  • 2.3.1 Quotation
  • 2.3.2 Example: Symbolic Differentiation
  • 2.3.3 Example: Representing Sets
  • 2.3.4 Example: Huffman Encoding Trees

前面部分涉及到的全是数字类型的数据，这一节作者开始讲字符型数据了。

2.3.1 Quotation

这节就是字符串数据类型了，这个多数有点基础的都比较清楚的，要注意区分的是变量名和字符串。

如果我们要构建一个列表，里面包含字符 a, b

在python中，我们写

list a = ["a", "b"]

那如果再来一个list

list b = [a, "a"]

显然前面一个a是变量名，后面一个才是字符串值

lisp中，用'来区分是变量还是字符，但是如果写'(a, b)的话，这可是个列表

(list 'a 'b)
(a b)
(list 'a b)
(a 2)

练习

2.53
Exercise 2.53: What would the interpreter print in response
to evaluating each of the following expressions?
(list 'a 'b 'c)
(list (list 'george))
(cdr '((x1 x2) (y1 y2)))
(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))
(memq 'red '(red shoes blue socks))

(list 'a 'b 'c)

  • 这里的'a 'b 'c 都是字符，而非变量，所以结果是 '(a b c)

(list (list 'george))

  • 'george表示字符串，
  • (list 'george)则是一个包含该字符串的列表，
  • (list (list 'george)) 则是包含该列表的列表，'((george))

(cdr '((x1 x2) (y1 y2)))

  • '((x1 x2) (y1 y2)) 是一个列表，内包含两个列表(x1 x2), (y1 y2).
  • 该列表的cdr应该是第二个子列表(y1 y2) ——————————错！
  • 更正：cdr的返回值永远是列表，所以结果应该是'((y1 y2))'

(cadr '((x1 x2) (y1 y2)))

  • cadr是取列表最后一个元素的car
  • '((x1 x2) (y1 y2)) 是一个列表，内包含两个列表(x1 x2), (y1 y2).
  • 该列表的cdr是(y1 y2)
  • 再取其car，因为car的返回值是atom，所以结果是(y1 y2)

(pair? (car '(a short list)))

  • car的返回值永远是atom， 不是列表，所以结果是false

(memq 'red '((red shoes) (blue socks)))

  • '((red shoes) (blue socks)) 是列表，里面不包含字符串red, 所以结果是false

(memq 'red '(red shoes blue socks))

  • '(red shoes blue socks) 是包含red字符串的列表，所以结果是true
  • 更正：memq当包含字符串的时候，返回值是包含该字符串的列表（可能是原列表的子列表）

实际运行结果

(list 'a 'b 'c)
> '(a b c)
(list (list 'george))
> '((george))
(cdr '((x1 x2) (y1 y2)))
> '((y1 y2))
(cadr '((x1 x2) (y1 y2)))
> '(y1 y2)
(pair? (car '(a short list)))
> #f
(memq 'red '((red shoes) (blue socks)))
> #f
(memq 'red '(red shoes blue socks))
> '(red shoes blue socks)

2.3.2 Example: Symbolic Differentiation

这一节打算先跳过，因为看着满屏的数学公式有点吃不消，暂时静不下心来攻克之，但对作者的这段话很想认真理解一下，先记在这里，看看后面的几个例子能不能解释

we will first define a differentiation algorithm that operates on abstract objects such as “sums,” “products,” and “variables” without worrying about how these are to be represented. Only aerward will we address the representation problem.

先定义一些具体操作的算法，然后再考虑如何呈现。

目前的理解是，前者是一些小模块，后者（即呈现）是组合这些模块完成最终的procedure。

这是不是paul graham在Programming Bottom-up中提到的自下而上设计法？感觉自己理解的并不怎么清楚。回头细看。

2.3.3 Example: Representing Sets

提到Set，都知道表示集合，里面的值都是独一无二的(unique)。

作者从数据抽象的角度来定义set：

  • 通过对Set可能要做的**操作（operations）**来定义

有点像，想要了解锤子是什么，先看看要用锤子来做什么。

试着理解一下作者的这种定义：

假设已知的数据是：

  • 一堆员工记录，里面有：
    • 名字
    • 工资
    • 负责的项目

我们如何处理这些数据？如何在计算机中使用它们

我们可能要做的操作有：增删改查。

那这些操作要用到哪些数据上呢？显然是

  • 员工记录
  • 每个员工负责的项目

（名字和工资对于每个员工而言是无法增删改查全具备的）

这样，我们便可以将“负责的项目”从“一堆员工记录”中抽离出来，单独处理。

回到Set的例子，对于集合而言，可能要用到的操作包括：

  • 合并
  • 求交集
  • 判断元素是否在集合中
  • 添加元素等

如果我们要处理的数据要用到上面这些操作的时候，便可以考虑用Set来定义数据。

set的表示方式

如何来表示集合set，作者举了三种方式：

  • set as unordered list
  • set as ordered list
  • set as binary tree

设计表示方式的时候，需要注意的问题是执行效率(Efficiency)。

比如，判断一个元素是否在set中，最坏的情况是要遍历set中所有元素才能知道（如该元素恰巧在set的最后，或者根本不在set中）；求两个集合的交集，最坏情况是要遍历两个集合的所有元素。如何避免最坏情况发生可能需要点技巧，比如对集合进行一下改进（从无序->有序）等

set as unordered list

以无序列表的形式来表示，这个我们见得比较多了，Python中的list便是一个具体的例子。

分析一下list集合的执行效率

  • element in list?
    • 因为是无序列表，最坏情况是，如果list中有n个元素，需要跑遍历所有n个元素，Θ(n)
  • intersect
    • for loop: 最坏情况，遍历两个列表的所有元素，Θ(n*n)
    • set1.intersection(set2) 【python自带会快一些】
  • union
    • for loop: 同样Θ(n)
    • set1.union(set2)
  • append
    • 同样Θ(n)
set as ordered list
set as binary tree

reference:

as per https://blog.michelemattioni.me/2015/01/10/list-intersection-in-python-lets-do-it-quickly, 求交集的时候，先将list转换成set，然后再用set.intersection要比用for loop快得多。具体原因待解