1.3 背包、队列和栈

研究方法:1)学习其 API 和用例;2)讨论数据类型的值和所有可能的表示方法;3)各种操作的实现。

1.3.1 API

每份 API 都含有一个无参数的构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。Stack 和 Queue 都含有一个能够删除集合中的特定元素的方法。

背包:

Bag() 创建一个空背包
void add(item) 添加一个空元素
bool isEmpty() 背包是否为空
int size() 背包中元素的数量

先进先出(FIFO)队列:

Queue() 创建空队列
void enqueue(item) 添加一个元素
Item dequeue() 删除最早添加的元素
bool isEmpty() 队列是否为空
int size() 队列中元素数量

下压(后进先出,LIFO)栈:

Stack() 创建一个空栈
void push(item) 添加一个元素
Item pop() 删除最近添加的元素
bool isEmpty() 栈是否为空
int size() 栈中的元素数量

1.3.1.1 泛型

因为这里使用的 Python 语言来实现书中的代码,所以不存在泛型的问题,Python 是鸭子类型。

1.3.1.2 自动装箱

自动讲一个原始数据类型转换为一个封装类型被称为自动装箱,自动将一个封装类型转换为原始数据类型被称为自动拆箱。

1.3.1.3 可迭代的几何类型

对应 Python 中的 Iterable 类型。

1.3.1.4 背包

背包是一种不支持从中删除元素的几何数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素。迭代的顺序不确定且与用例无关。

1.3.1.5 先进先出队列

先进先出队列(简称队列)是一种基于先进先出(FIFO)策略的集合类型。

1.3.1.6 下压栈

下压栈(简称栈)是一种基于后进先出(LIFO)策略的几何类型。典型例子:1)邮件系统;2)浏览器。

1.3.1.7 算数表达式求值

递归定义:算数表达式可能是一个数、或者是一个由左括号、一个算数表达式、一个运算符、另一个算数表达式和一个右括号组成的表达式。(简单起见,这里定义的是未省略括号的算数表达式)。

E.W.Dijkstra 在 20 世纪 60 年代发明了一个非常简单的算法,用两个栈(一个用于保存运算符,一个用于保存操作数)完成了这个任务。

我们根据以下 4 种情况从左到右逐个将这些实体送入栈处理:

  1. 将操作数压入操作数栈;
  2. 将运算符压入运算符栈;
  3. 忽略左括号;
  4. 在遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的运算结果压入操作数栈。

一个用栈实现的简单解释器例子:

def evaluate(expression):
    ops = Stack()
    vals = Stack()
    
    for s in expression:
        if s == '(':
            continue
        elif s == '+':
            ops.push(s)
        elif s == '-':
            ops.push(s)
        elif s == '*':
            ops.push(s)
        elif s == '/':
            ops.push(s)
        elif s == ')':
            op = ops.pop()
            v = vals.pop()
            if op == '+':
                v = vals.pop() + v
            elif op == '-':
                v = vals.pop() - v
            elif op == '*':
                v = vals.pop() * v
            elif op == '/':
                v = vals.pop() / v
            vals.push(v)
        else:
            vals.push(s)
    return vals[0]

1.3.2 集合数据类型的实现

1.3.2.1 定容栈

定容栈是一种表示容量固定的字符串栈的抽象数据类型,它的 API 和 Stack 的 API 有所不同:它只能处理 String 值,它要求用例制定一个容量且不支持迭代。实现一份 API 的第一步就是选择数据的表示方式,对于 FixedCapacityStackOfStrings,我们可以选用数组。

API:

FixedCapacityStackOfStrings(size) 创建一个容量为 size 的空栈
void push(item:str) 添加一个字符串
str pop() 删除最近添加的字符串
bool isEmpty() 栈是否为空
int size() 栈中字符串数量

数据类型的实现:

class FixedCapacityStackOfStrings:
    def __init__(self, size):
        _a = []     # stack entries
        _size = size
        N = 0      # stack index
        

    def isEmpty(self):
        return N == 0

    def size(self):
        return N
    
    def push(self, item):
        N += 1
        _a[N] = item

    def pop(self):
        N -= 1
        return _a[N]
  • 数组中的元素顺序和它们被插入的顺序相同
  • 当 N 为 0 时栈为空
  • 栈的顶部位于 _a[N-1]

1.3.2.2 泛型

如果上面代码是用 Java 写的话,确实只能处理 String 对象,但是 Python 是动态类型的语言,不存在泛型的问题。

1.3.2.3 调整数组的大小

选择用数组表示栈内容意味着用例必须预先估计栈的最大容量(在 Python 中数组是动态变化的,所以不需要,这里为了模拟)。在 Java 中,数组一旦创建,其大小是无法改变的,因此栈使用的空间只能是这个最大容量的一部分。选择大容量的用例在栈为空或几乎为空时会浪费大量的内存。push() 方法需要在代码中检测栈是否已满,我们的 API 中也应该含有一个 isFull() 的方法来允许用例检测栈是否已满。我们在此省略了它实现的代码,因为我们希望用例从处理栈已满的问题中解脱出来,如我们原始的 Stack API 所示。因此,我们修改了数组的实现,动态调整数组的大小,使得它既足以保存所有元素,又不至于浪费过多的空间。

首先,实现一个方法将栈移动到另一个大小不同的数组中:

def resize(self, max):
   temp = []
   _size = max
   for i in range(N):
       temp[i] = _a[i]
   a = temp

现在,在 push() 中,检查数组是否太小。具体来说,我们会通过检查栈代销 N 和数组大小 _size 是否相等来检查数组是否能容纳新的元素。如果没有多余的空间,我们会将数组的长度加倍,然后既可以和之前一样用 a[N++] = item 插入新元素了:

def push(self, item):
   if N == _size:
       self.resize(2*_size)
   N += 1
   _a[N] = item

类似,在 pop() 中,首先删除栈顶的元素,然后如果数组太大我们就将它的长度减半。只要稍加思考,技能明白正确的检测条件是栈大小是否小鱼数组的四分之一。在数组长度被减半之后,它的状态为半满,在下次需要改变数组大小之前人能够进行多次 push()pop() 操作。

def pop(self):
   N -= 1
   item = _a[N]
   _a[N] = None
   if N > 0 and N == _size/4:
       resize(_size/2)
   return item

在这个实现中,栈永远都不会溢出,使用率也永远不会低于四分之一。

1.3.2.4 对象游离

Java 的垃圾收集策略是回收所有无法被访问的对象的内存。在我们队 pop() 的实现中,被弹出的元素引用仍然存在于数组中。这个元素实际上已经是一个孤儿了——它永远不会被再访问了,但 Java 的垃圾收集器没法知道这一点,除非该引用被覆盖。即使用例已经不再需要这个元素了,数组中的引用仍然可以让它继续存在,这种情况(保存一个不需要的对象的引用)成为游离

1.3.2.5 迭代

集合类数据类型的基本操作之一就是,能够使用 Python 的 for-in 语句通过迭代遍历并处理集合中的每个元素。这种方式的代码既清晰又简介,且不依赖与集合数据类型的具体实现。

好处:1)我们无需改变任何用例代码就可以随意切换不同的表示方法;2)更重要的是,从用例的角度来说,无需知晓类的实现细节用例也能使用迭代。

在 Python 中,需要在类中实现 __iter__()__next__()

def __iter__(self):
     return self

def __next__(self):
     index = 0
     if index > _size:
         raise StopIteration
     else:
         index += 1
         return self._a[index-1]

例如,我们在实现 Queue 的 API 时,可以使用两个实例变量作为索引,一个变量 head 指向队列的开头,一个变量 tail 指向队列的结尾。在删除一个元素时,使用 head 访问它并将 head 加 1;在插入一个元素时,使用 tail 保存它并将 tail 加 1.如果某个索引在增加之后越过了数组的边界则将它重置为 0.

下压(LIFO)栈(能够动态调整数组大小的实现):

class ResizingArrayStack(object):
    a = []
    N = 0

    def isEmpty(self):
        return N == 0

    def size(self):
        return N

    def resize(self, max):
        temp = []
        for i in range(N):
            temp[i] = a[i]
        a = temp

    def push(self, item):
        if N == len(self.a):
            self.resize(2*len(self.a))
        N += 1
        a[N] = item

    def pop(self):
        N -= 1
        item = a[N]
        a[N] = None
        if N > 0 and N == len(self.a):
            self.resize(len(self.a)/2)

    def __iter__(self):
        return self

    def __next__(self):
        index = N - 1
        if index == 0:
            raise StopIteration
        else:
            index -= 1
            return a[index]

这份支持迭代的 Stack API 的实现是所有集合抽象数据类型实现的模板。它将所有元素保存在数组中,并动态调整数组大小以保持数组大小和栈大小之比小于一个常数。

1.3.3 链表

定义:链表是一种递归的数据结构,它为空(None),或者是指向一个结点(node)的引用,该结点含有一个泛型的元素和一个指向另一条链表的引用。

在这个定义中,结点是一个可能含有任意类型数据的抽象实体,它所包含的指向结点的应用显示了它在构造链表之中的作用。

1.3.3.1 结点记录

class Node(object):
        def __init__(self, item):
             self.item = item
             self.next = None
             
        def get_item(self):
                return self.item
                
        def get_next(self):
                return self.next
                
        def set_item(self, item):
                self.item = item
                
        def set_next(self, next):
                self.next = next

1.3.3.8 栈的实现

下压堆栈(链表实现):

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None

class Stack(object):
    def __init__(self):
        self.first = None
        self.N = 0
        
    def isEmpty(self):
        return self.N == 0
    
    def size(self):
        return self.N
    
    def push(self, item):
        oldfirst = self.first
        self.first = Node(item)
        self.first.next = oldfirst
        self.N += 1
        
    def pop(self):
        item = self.first.item
        self.first = self.first.next
        self.N -= 1
        return item

1.3.3.9 队列的实现

基于链表数据结构实现 Queue API 也很简单。它将队列表示为一条从最早插入的元素到最近插入的元素的链表,实例变量 first 指向队列的开头,实例变量 last 指向 队列的结尾。这样,要讲一个元素入列(enqueue()),我们就将它添加到表尾(但是在链表为空时需要将 first 和 last 都指向新节点);要将一个元素出列(dequeue()),我们就删除表头的结点(代码和 Stack 的 pop() 相同,只是当链表为空时需要更新 last 的值)。size()isEmpty() 方法的实现和 Stack 相同。

和刚才一样,我们用链表达到了最优设计目标:它可以处理任意类型数据,所需的空间总是和集合大小成正比,操作所需时间总是和集合大小无关

先进先出队列的实现:

class Queue(object):
    def __init__(self):
        self.first = None  # 指向最早添加的结点的链接
        self.last = None  # 指向最近添加的结点的链接
        self.N = 0
        
    def isEmpty(self):
        return self.N == 0
    
    def size(self):
        return self.N
    
    def enqueue(self, item):
        oldlast = self.last
        self.last = Node(item)
        self.last.next = None
        if self.isEmpty():
            self.first = self.last
        else:
            oldlast.next = self.last
        self.N += 1
        
    def dequeue(self):
        item = self.first.item
        self.first = self.first.next
        if self.isEmpty():
            self.last = None
        self.N -= 1
        return item

在结构化存储数据集时,链表是数组的一种重要的替代方式。事实上,编程语言历史上的一块里程碑就是 McCathy 在 20 世纪 50 年代发明的 LISP 语言,而链表则是这种语言组织程序和数据的主要结构。

1.3.3.10 背包的实现

用链表数据结构实现我们的 Bag API 只需要将 Stack 中的 push() 方法改名为 add(),并去掉 pop() 的实现即可。

对于 Stack,链表的访问顺序是后进先出;对于 Queue,链表的访问顺序是先进先出;对于 Bag,它正好也是后进先出的顺序,但顺序并不重要。

背包的实现:

class Bag(object):
    def __init__(self):
        self.first = None
        self.N = 0
        
    def isEmpty(self):
        return self.first is None
    
    def add(self, item):
        oldfirst = self.first
        self.first = Node(item)
        self.first.next = oldfirst
        self.N += 1
        
    def __len__(self):
        return self.N
        
    def __iter__(self):
        return _BagIterator(self.first)

class _BagIterator(object):
    def __init__(self, listhead):
        self.current = listhead

    def __iter__(self):
        return self

    def __next__(self):
        if self.current is None:
            raise StopIteration
        item = self.current.item
        self.current = self.current.next
        return item

这份代码中实现了迭代器(可以使用 for-in 来遍历),Stack 和 Queue 可以使用同样的方法来实现。

1.3.4 综述

基础数据结构:

数据结构 优点 缺点
数组 通过索引可以直接访问任意元素 在初始化时就需要知道元素的数量
链表 使用的空间大小和元素数量成正比 需要通过引用访问任意元素

我们在本节中研究背包、队列和栈时描述数据结构和算法的方式是全书的原型。在研究一个新的应用领域时,我们将会按照以下步骤识别目标并使用数据抽象解决问题:

  1. 定义 API
  2. 根据特定的应用场景开发用例代码
  3. 描述一种数据结构(一组值得表示),并在 API 所对应的抽象数据类型的实现中根据它定义类的实例变量
  4. 描述算法(实现一组操作的方式),并根据它实现类中的实例方法
  5. 分析算法的性能特点

本书中所给出的数据结构举例:

数据结构 抽象数据类型 数据表示
父链接数 UnionFind 整形数组
二分查找树 BST 含有两个链接的结点
字符串 String 数组、偏移量和长度
二插堆 PQ 对象数组
散列表(拉链法) SeparateChainingHashST 链表数组
散列表(线性探测法) LinerProbingHashST 两个对象数组
图的邻接链表 Graph Bag 对象数组
单词查找树 TrieST 含有链接数组的结点
三向单词查找树 TST 含有三个链接的结点

1.4 算法分析

1.4.1 科学方法

科学家用来理解自然世界的方法对于研究计算机程序的运行时间同样有效:

  • 细致地观察真实世界的特点,通常还要有精确的测量
  • 根据观察结果提出假设模型
  • 根据模型预测未来的事件
  • 继续观察并核实预测的准确性
  • 如此反复直到确认预测和观察一致

1.4.3 数学模型

一个程序运行的总时间主要和两点有关:

  • 执行每条语句的耗时
  • 执行每条语句的频率

1.4.4 增长数量级的分类

对增长数量级常见假设的总结:

描述 增长的数量级 说明 举例
常数级别 1 普通语句 将两个数相加
对数级别 \(logN\) 二分策略 二分查找
线性级别 \(N\) 循环 找出最大元素
线性对数级别 \(NlogN\) 分治 归并排序
平方级别 \(N^2\) 双层循环 检查所有元素对
立方级别 \(N^3\) 三层循环 检查所有三元组
指数级别 \(2^N\) 穷举查找 检查所有子集

1.4.5 设计更快的算法

学习程序的增长数量级的一个重要动力就是为了帮助我们为同一个问题设计更快地算法。

1.4.7 注意事项

1.4.7.1 大常数

在首项近似中,我们一般会忽略低级项中的常数系数,但这可能是错的。例如,当我们取函数 \(2N^2+cN\) 的近似为 ~\(2N^2\) 时,我们的假设是 c 很小。如果事实不是这样(比如 c 可能是 \(10^6\)),该近似就是错误的。因此,我们要对可能的大常数保持敏感。

1.4.7.2 非决定性的内循环

内循环是决定性因素的假设并不是总正确的。错误的成本模型可能无法得到真正的内循环,问题规模 \(N\) 也许没有大到对指令的执行频率的数学描述中的首项大大超过其他低级项并可以忽略它们的程度。有些程序在内循环之外也有大量指令需要考虑。

1.4.7.3 指令时间

每条指令执行所需的时间总是相同的假设并不总是正确的。例如,大多数现在计算机系统都会使用缓存技术来组织内存,在这种情况下访问大数组中的若干个并不相邻元素所需的时间可能很长。

1.4.8 处理对于输入的依赖

1.4.8.1 输入模型

一种方法是更加小心地对我们所要解决的问题所处理的输入建模。使用这种方法的困难主要有两点:

  1. 输入模型可能是不切实际的
  2. 对输入的分析可能极端困难

1.4.8.3 随机化算法

为性能提供保证的一种重要的方法是引入随机性。例如,快速排序算法在最坏情况系的性能是平方级别的,但通过随机打乱输入,根据概率我们能够保证它的性能是线性对数的。每次运行该算法,它所需的时间均不相同,但它的运行时间超过超过线性对数级别的可能性小到可以忽略。与此类似,用于符号表的散列算法在最坏情况下的性能是线性级别的,但根据概率我们可以保证它的运行时间是常数级别的。

1.4.8.5 均摊分析

相应地,提供性能保证的另一种方法是通过记录所有操作的总成本并除以操作总数来将成本均摊。在这里,我们可以允许执行一些昂贵的操作,但保持所有操作的平均数成本较低。

1.5 案例研究:union-find 算法

为了说明我们设计和分析算法的基本方法,我们现在来学习一个具体的例子。我们的目的是强调以下几点:

  • 优秀的算法因为能够解决实际问题而变得更为重要;
  • 高效算法的代码也可以很简单;
  • 理解某个实现的性能特地拿是一项有趣而令人满足的挑战;
  • 在解决同一个问题的多种算法之间进行选择时,科学方法是一种重要的工具;
  • 迭代式改进能够让算法的效率越来越高。