向量

向量

到目前为止，我们的程序基本建立在序对之上，并用序对构造出链表。我们用列表来表示序列（sequence）这一抽象数据类型。列表虽然好用，却有一个很大的缺点：引用列表的第 $n$ 个元素需要 $\Theta(n)$ 时间，因为必须调用 $n$ 次 cdr。

我们希望有一种办法，能在常数（$\Theta(1)$）时间内引用序列的第 $n$ 个元素。在 Scheme 中，向量（vector）提供了这样的机制。如果你用 Java 或其他类 C 语言编程过，就会发现它本质上就是数组。

可惜向量也有短板。在链表（也就是你这学期一直在用的列表结构）中，往末尾添加元素只需在表尾 cons 一下，耗时 $\Theta(1)$；而往向量里添加元素却要 $\Theta(n)$ 时间，其中 $n$ 是向量的长度。

向量如何工作

向量是怎么工作的？究竟是什么「黑魔法」让元素访问变成常数时间？事实证明，那并不是什么黑魔法。

创建向量时，你必须指定它的大小。创建大小为 $n$ 的向量，会一次性划出长度为 $n$ 的一块内存。既然我们知道第一块内存的地址，只要把这个地址加上 $k$，就能得到向量的第 $k$ 个元素。正是这一点，让我们可以在常数时间内访问任意元素。

代价在于：为了把所有元素放进一整块连续内存，我们必须一次性分配整块空间。这就是往向量里添加元素需要 $\Theta(n)$ 时间的原因——我们不得不重新分配一块新内存（即创建新数组），并把旧元素全部复制过去。

向量基本操作

也就是说，第一个元素称为第 0 个元素。在向量 #(1 2 3 4) 中，1 位于第 0 个索引，2 位于第 1 个索引，依此类推。

向量的一些基本操作与列表的基本操作类似：

向量	列表
(vector a b c d ...)	(list a b c d ...)
(vector-ref vec n)	(list-ref lst n)
(vector-length vec)	(length lst)

那 cons 和 append 呢？由于往向量里添加元素需要 $\Theta(n)$ 时间，向量没有在尾部追加元素的基本操作，但有另外一些构造函数。

如前所述，向量的主要弱点之一是创建时就必须声明长度。因此，创建长度为 len 的空向量用 (make-vector len)；如果希望所有元素初始化为某个特定值，可以写成 (make-vector len val)。

到目前为止，我们只能创建元素全为空或全为同一值的向量，这不太实用。那么怎样改变向量的元素？用变动！具体来说，用 (vector-set! vec n value) 把向量的第 $n$ 个元素设为某个值。这与 set-car!、set-cdr! 类似。

向量编程

用向量编程时，通常会用迭代过程来遍历向量。下面看几个例子热热身。

先看列表的 map 函数：

(define (map fn lst)
    (if (null? lst)
        '()
        (cons (fn (car lst))
              (map (cdr lst)))))

现在为向量写一个对应的函数，叫 vector-map：

(define (vector-map fn v)
    (define (loop newvec i)
        (if (< i 0)
            newvec
            (begin (vector-set! newvec i (fn (vector-ref v i)))
                   (loop newvec (- i 1)))))
    (loop (make-vector (vector-length v))
          (- (vector-length v) 1)))

它比列表的 map 复杂多了！一来，我们的 vector-map 多了一个索引变量 i，随时记录当前在向量中的位置；二来，我们必须知道向量的长度，函数才能判断何时停下。

列表的 map 用递归实现，而 vector-map 用迭代实现。学期初我们说过，递归通常被认为比迭代更优雅。现在你大概明白为什么了。

检验理解

写一个函数 vector-addup，接受一个数字向量，返回所有数字之和。放到 STk 里验证你的答案。

向量与列表对比

下面是列表和向量各操作运行时间的对比。

操作	列表	向量
查找第 $n$ 个元素	(list-ref lst n)：$\Theta(n)$	(vector-ref vec n)：$\Theta(1)$
添加元素	cons：$\Theta(1)$	无对应操作：$\Theta(n)$
求长度	(length lst)：$\Theta(n)$	(vector-length vec)：$\Theta(1)$

表示序列没有哪种方式是最好的——向量和列表各有长处。如果你的序列需要频繁地增删元素，最好用列表，因为 cons 只需常数时间；反过来，如果元素个数固定，但要大量修改，向量更合适，因为 vector-ref 只需常数时间。

示例：洗牌

假设我们有一副牌，想把它打乱。用什么序列来表示最好呢？

先用列表，用变动来洗牌：

(define (list-shuffle! lst)
    (if (null? lst)
        '()
        (let ((index (random (length lst))))
            (let ((pair ((repeated cdr index) lst))
                  (temp (car lst)))
                (set-car! lst (car pair))
                (set-car! pair temp)
                (list-shuffle! (cdr lst))
                lst))))

这确实能满足需求，但非常慢——$\Theta(n^2)$ 时间。事实上，任何基于列表的解法都要 $\Theta(n^2)$ 时间，因为找一个随机元素要 $\Theta(n)$ 时间，而这样的操作要做 $n$ 次。

换成向量试试：

(define (vector-shuffle! vec)
    (define (loop n)
        (if (= n 0)
            vec
            (let ((index (random n))
                  (temp (vector-ref vec (- n 1))))
                (vector-set! vec (- n 1) (vector-ref vec index))
                (vector-set! vec index temp)
                (loop (- n 1)))))
    (loop (vector-length vec)))

本质上还是同一个算法，只是作用在向量上。由于 vector-ref 是常数时间，这里执行 $n$ 次常数时间的操作，总时间降到 $\Theta(n)$。

测验小贴士

刚接触向量可能会有点不适应，尤其是多了不少新函数。强烈建议你在小抄纸上记下我们用到的各种函数原语（如 make-vector、vector-ref 等），以及作业里要定义的辅助过程（如 vector-append），还有这份讲义里的内容（如 vector-map）。