数据结构和算法笔记

我完全不懂数据结构和算法. 另外, 这里是一些关于数据结构和算法的笔记. 当我认为我懂了之后, 或许会写一本书.

什么是数据结构?

以下内容翻译自Purely Functional Data Structures.

任何对于数据结构的讨论都充斥着误解的潜在可能, 因为术语数据结构至少具有四个不同但相互关联的含义.

一个抽象数据类型 (即一个类型和一集该类型上的函数). 我们将会称其为一个抽象.
一个抽象数据类型的一个具体实现. 我们将会称其为一个实现, 但是注意一个实现未必要被具体化为代码——一个具体的设计就足够了.
一个数据类型的一个实例, 例如一个特定的列表或树. 我们将会称这样的一个实例为一个对象或者一个版本. 然而, 特定的数据类型可能有着它们自己的命名法. 例如, 我们将会直接称栈或队列对象为栈或队列.
一个在更新下保持不变的独特身份(identity). 例如, 在一个基于栈的解释器里, 我们经常非正式地说栈 (the stack), 就好像只存在一个栈似的, 而不是不同的时间有着不同的版本. 我们将会称这个身份为一个可持久化身份. 这个事项主要出现在可持久化数据结构的上下文中; 当我们言及相同数据结构的不同版本时, 我们的意思是这些不同版本共享着一个相同的可持久化身份.

大致说来, 抽象对应于Standard ML的签名, 实现对应于结构或函子, 对象或版本对应于值. 至于可持久化身份, Standard ML中没有贴切的对应概念 (good analogue).

IOI 1994 The Triangle

算是简单的动态规划问题.

(define ref
  (case-lambda
    ((v i) (vector-ref v i))
    ((v i . j*) (apply ref (vector-ref v i) j*))))
(define (solve-IOI94P1 T)
  (define N (vector-length T))
  (define S (make-vector N))
  (let iter ((i 0))
    (cond
      ((= i N) (apply max (vector->list S)))
      (else
       (let iter ((j i))
         (cond
           ((= j 0)
            (vector-set! S 0 (+ (ref T i 0) (ref S 0))))
           (else
            (vector-set! S j (+ (ref T i j)
                                (max (ref S (- j 1)) (ref S j))))
            (iter (- j 1)))))
       (iter (+ i 1))))))

> (solve-IOI94P1
   '#(#(7)
      #(3 8)
      #(8 1 0)
      #(2 7 4 4)
      #(4 5 2 6 5)))
30

题解网上很容易找到, 也没有必要再写什么. 注意make-vector默认将每个元素置为0.

辅助过程

(define (vector-swap! v i j)
  (define t (vector-ref v i))
  (vector-set! v i (vector-ref v j))
  (vector-set! v j t))

插入排序

插入排序相当简单 (但实际上对于没有接触过的人而言又不那么简单), 但也相当重要. 在数组长度比较短的时候, 插入排序往往是效率最高的.

(define (insertion-sort! v)
  (define l (vector-length v))
  (unless (< l 2)
    (let iter ((i 1))
      (unless (= i l)
        (insert! v i)
        (iter (+ i 1))))))
(define (insert! v i)
  (define x (vector-ref v i))
  (let iter ((j (- i 1)))
    (cond
      ((= j -1) (vector-set! v 0 x))
      ((> (vector-ref v j) x)
       (vector-set!
        v (+ j 1) (vector-ref v j))
       (iter (- j 1)))
      (else
       (vector-set! v (+ j 1) x)))))

插入排序的时间复杂度估计非常简单, 每次插入最坏的情况就是移动到开头, 并且插入次数大致上是 $n$ , 故上界为 $O (n^{2})$ .

归并排序

注意一下, (merge-sort! v lo hi)排序的是v从lo到hi的部分, 包含lo但不包含hi.

(define (merge-sort! v lo hi)
  (unless (<= (- hi lo) 1)
    (define mi (quotient (+ lo hi) 2))
    (merge-sort! v lo mi)
    (merge-sort! v mi hi)
    (merge! v lo mi hi)))
(define (merge! v lo mi hi)
  (define l (vector-copy v lo mi))
  (define r (vector-copy v mi hi))
  (define a (- mi lo))
  (define b (- hi mi))
  (let iter ((k lo) (i 0) (j 0))
    (cond
      ((and (< i a) (< j b))
       (cond
         ((< (vector-ref l i)
             (vector-ref r j))
          (vector-set! v k (vector-ref l i))
          (iter (+ k 1) (+ i 1) j))
         (else
          (vector-set! v k (vector-ref r j))
          (iter (+ k 1) i (+ j 1)))))
      ((= i a)
       (let iter ((k k) (j j))
         (unless (= k hi)
           (vector-set! v k (vector-ref r j))
           (iter (+ k 1) (+ j 1)))))
      ((= j b)
       (let iter ((k k) (i i))
         (unless (= k hi)
           (vector-set! v k (vector-ref l i))
           (iter (+ k 1) (+ i 1))))))))

归并排序的时间复杂度估计不难理解, 大致上每个层次归并所用的时间是 $O (n)$ , 而大约有 $\log_{2} (n)$ 层, 故上界估计为 $O (n \log_{2} (n))$ .

冒泡排序

不知道为什么, 编写冒泡排序是一件很有压力的事情, 而实际上我的确也写了很长时间. 在编写冒泡排序的时候, 我的脑子里的所思所想是这样的: 后段已排序, 后段的每个元素都大于等于前段的所有元素, 每轮交换可以将前段的最大元素移至最后的位置, 如果在一轮中没有发生交换, 则说明整个数组是已排序好了的. 当然, 也可以从逆序归约的角度思考问题.

(define (bubble-sort! v)
  (define l (vector-length v))
  (let loop ((i 1))
    (unless (>= i l)
      (let iter ((j 0) (flag #f))
        (cond
          ((= j (- l i))
           (when flag
             (loop (+ i 1))))
          ((> (vector-ref v j)
              (vector-ref v (+ j 1)))
           (vector-swap! v j (+ j 1))
           (iter (+ j 1) #t))
          (else
           (iter (+ j 1) flag)))))))

快速排序

这里的约定和归并排序那里一致. 主元的选取是任意的, 我只是选取了第一个元素.

(define (quick-sort! v lo hi)
  (unless (<= (- hi lo) 1)
    (define p (partition! v lo hi))
    (quick-sort! v lo p)
    (quick-sort! v (+ p 1) hi)))
(define (partition! v lo hi)
  (define pivot (vector-ref v lo))
  (let iter ((left (+ lo 1)) (right hi))
    (cond ((= left right)
           (vector-swap! v lo (- left 1))
           (- left 1))
          ((> (vector-ref v left) pivot)
           (vector-swap! v left (- right 1))
           (iter left (- right 1)))
          (else
           (iter (+ left 1) right)))))

根据原地 (in-place) 的定义的不同, 快速排序可以是原地的, 也可以不是原地的, 因为它的确要消耗栈的空间.

二分搜索

据说二分搜索很少有人能够书写正确, 即便是算法研究者也不例外. 这里仍然遵循着左闭右开的原则, 以后不再赘述.

(define (binary-search x v lo hi)
  (if (>= lo hi)
      #f
      (let ((mi (quotient (+ lo hi) 2)))
        (cond
          ((= (vector-ref v mi) x) mi)
          ((> (vector-ref v mi) x)
           (binary-search x v lo mi))
          (else
           (binary-search x v (+ mi 1) hi))))))

杂凑 (哈希)

3SUM问题

3SUM的前条件是v已从小到达排序且元素互异.

(define (3SUM v)
  (define l (vector-length v))
  (let loop ((i 0) (result '()))
    (cond ((= i l) result)
          ((>= (vector-ref v i) 0) result)
          (else
           (let iter ((j (+ i 1)) (k (- l 1)) (r '()))
             (if (< j k)
                 (let* ((a (vector-ref v i))
                        (b (vector-ref v j))
                        (c (vector-ref v k))
                        (s (+ a b c)))
                   (cond
                     ((= s 0) (iter (+ j 1)
                                    (- k 1)
                                    (cons (list a b c) r)))
                     ((< s 0) (iter (+ j 1) k r))
                     (else (iter j (- k 1) r))))
                 (loop (+ i 1) (append r result))))))))

parallel和concurrent的区别

parallel指的是一种同时运行多个任务的实际能力, 而concurrent是一种编程抽象, 它维护了一种同时运行多个任务的illusion. concurrent的程序可能的确以parallel的方式运行, 但也可能只是以顺序运行的方式来模拟parallelism.

以上是一种实用的表面说法, 在某种意义上其实有点似是而非. concurrency的本质在于一种不确定性, 我们无法控制事件发生的时间和顺序, 但仍然企图获得对于这样的物理本性的一种(可复合的)控制. parallelism和concurrency不同的地方在于, 它强调的同时运行的能力可以从一开始得到控制, 而且我们从一开始的企图就是从中获得效率和性能. 当然, 或许我需要说明的是, 并行不是自然或者天生就是可控的, 而是我们希望去控制而可以控制, 因而这里重要的事情是确定子计算的依赖关系.

zipper

zipper可以有多种理解, 但是从具体的数据结构来说, zipper可以理解为附加了历史记录的各种各样的数据结构. 这个历史记录描述了我们是以何种方式进入相应的数据结构的. 通过历史(和现在), 我们也可以还原本来数据结构的面貌.

关于 $d$ 叉树的基本事实

若以数组存储 $d$ 叉树 (且根结点的下标为 $1$ ), 那么下标为 $k$ 的结点的子结点的下标范围是 $[d (k - 1) + 2, d k + 2),$ 而下标为 $k$ (其中 $k > 1$ ) 的结点的父结点的下标为 $⌊ \frac{k + d - 2}{d} ⌋ .$ 具有 $n$ 层的满 $d$ 叉树的元素总数为 $d^{0} + d^{1} + \dots + d^{n - 1} = \frac{d^{n} - 1}{d - 1} .$ 具有 $n + 1$ 层 (即高度为 $n$ ) 的完全 $d$ 叉树的元素数目范围是 $[\frac{d^{n} - 1}{d - 1} + 1, \frac{d^{n + 1} - 1}{d - 1}] 或者写成 [\frac{d^{n} + d - 2}{d - 1}, \frac{d^{n + 1} + d - 2}{d - 1}) .$ 给这闭区间的左右范围乘上 $d - 1$ , 那么可以得到 $[d^{n} + d - 2, d^{n + 1} - 1] \subseteq [d^{n}, d^{n + 1}),$ 这暗示了具有 $k$ 个元素的完全 $d$ 叉树的高度可以表示为 $⌊ \log_{d} ((d - 1) k) ⌋ .$

堆排序

堆排序分为两个阶段, 第一阶段自底而上建最大堆, 第二阶段不断地将最大元素和未排序部分的最后一个元素交换 (相当于取出最大元素放在堆的后面), 并仍然需要维护堆的性质.

自底而上建堆可以被称为Floyd的技巧, 它比起逐个将数组元素加入堆中具有显然的性能优势. 当然了, 另外一个可以被称为Floyd技巧的东西出现在取出堆的优先元素时, 其需要将堆的最后元素放到堆顶, 然后通过下沉维护堆的性质. 既然最后的元素可以想见优先级非常低, 所以说一般而言其会沉到相当深的位置. Floyd的想法是, 不如先将其沉到底部, 然后再上浮, 如此可以减少比较次数. 若比较代价很大, 那么性能提升会比较明显. 不过, 我没有在这里的堆排序里实现后一个Floyd技巧.

(define (left-child lo k)
  (- (+ (* 2 k) 1) lo))
(define (heap-sort! v lo hi)
  (unless (<= (- hi lo) 1)
    (let iter ((i (quotient (+ lo hi -1) 2)))
      (unless (< i lo)
        (sink! v lo hi i)
        (iter (- i 1))))
    (let iter ((i (- hi 1)))
      (unless (< i lo)
        (vector-swap! v lo i)
        (sink! v lo i lo)
        (iter (- i 1))))))
(define (sink! v lo hi i)
  (let iter ((i i))
    (define l (left-child lo i))
    (unless (>= l hi)
      (define j
        (cond ((>= (+ l 1) hi) l)
              ((< (vector-ref v l)
                  (vector-ref v (+ l 1)))
               (+ l 1))
              (else l)))
      (unless (>= (vector-ref v i)
                  (vector-ref v j))
        (vector-swap! v i j)
        (iter j)))))

自底而上建堆时, 无需从最后一个元素开始, 因为它们都是叶子, 第一个不是叶子的位置是(quotient (+ lo hi -1) 2).

对于(sink! v lo hi i)而言, lo主要是为了确定后继的位置, 而hi当然是为了划定堆的范围.

minimax

对于两人回合制完美信息零和游戏而言, 形容minimax的最简明扼要的语言大概是事后诸葛. 假设现在我们拥有一个终局评估函数, 其给出了一局游戏的结果, 以数值表示. 例如, 对于 $A$ 和 $B$ 参与的一局游戏, 或许 $0$ 表示 $B$ 赢, $1$ 表示 $A$ 赢 (假设这种游戏没有平局或者其他终局情况). 那么, 以正常人的角度来看, $A$ 肯定是希望最大化终局函数的值, $B$ 肯定是希望最小化终局函数的值. 如果我们扩展整个游戏树, 包含所有可能的对局情况, 那么倒着看游戏, 就很容易理解 $A$ 或者 $B$ 该采取什么样的策略. 也就是说, 它们都应该采取对于自己最有利的策略. 再换句话说, 假设每个人都下最优的步骤且当前局面下所有步骤的未来结果已知 (也就是一个终局函数的值), 那么 $A$ 只需要选择最大的一步就行, 而 $B$ 则需要选择最小的一步. 以这种方式, 我们可以自后往前地构建出对于 $A$ 和 $B$ 而言的任何局面下的最佳步骤.