《算法》笔记 7 - 符号表、顺序查找、二分查找

本是古典何须时尚 2023-06-04 10:54 32阅读 0赞

*  符号表
    
     *  API
     *  有序符号表
     *  成本模型  
        
 *  无序链表中的顺序查找
    
     *  实现
     *  性能
 *  有序数组中的二分查找
    
     *  实现
     *  性能

现代计算机和网络使人们能够访问海量的信息，而且各种计算设备正在源源不断地生成新的信息，高效检索这些信息的能力就成了处理它们的重要前提。接下来学习几种经典的查找算法。

### 符号表 ###

符号表指的是一张用于存储信息的抽象的表格，主要目的就是将一个键和一个值联系起来，可以将一个键值对插入到符号表，也可以从符号表的所有键值对中按照键直接找到对应的值，符号表也被称为字典。

#### API ####

符号表最基本的操作是：插入、查找，此外还包括几种方便算法实现的操作。要实现符号表，首先要定义其背后的数据结构，并指明创建并操作这种数据结构以进行插入、查找所需的算法。  
符号表的API如下：

public class ST<Key,Value>{
        ST() //创建一张符号表
        void put(Key key,Value val)  //将键值对存入表中（若值为空则将键Key从表中删除）
        Value get(Key key)  //获取键key对应的值(若键key不存在则返回null)
        void delete(Key key)  //从表中删除键key和其对应的值
        boolean contains(Key key)  //键key在表中是否有对应的值
        boolean isEmpty() //表是否为空
        int size()  //表中键值对的数量
        Iterable<Key> keys()  //表中所有键的集合
    }

设计的符号表将会遵循以下规则：符号表的实现使用了泛型；每个键只能对应一个值，如果向表中存入的键值对已经在表中存在，则用新的值覆盖旧值，所以表中不存在重复的键；也不允许存入空或空值，只有在表中找不到键对应的值时，get方法会返回null。

#### 有序符号表 ####

符号表根据其中键是否有序分为有序符号表和无序符号表，有序符号表中基于键的有序性可以实现更多有用的操作。

Key floor(Key key)  //获取小于等于key的最大键
    Key ceiling(Key key)  //获取大于等于Key的最小键
    int rank(Key key) //获取小于Key的键的数量
    Key select(int k)  //获取排名为k的键
    Key max()  //获取最大的键
    Key min()  //获取最小的键

获取最大、最小键的操作使得有序符号表具有了与优先队列类似的功能，不同的是优先队列中可以存在重复的键但符号表不行。  
rank和select方法可以用来检验一个新的键是否插入到合适的位置。对于0到size()-1中的所有i都有i=rank(select(i))，且key=select(rank(key))。floor和ceiling类似于对实数的向下取整、向上取整操作。

#### 成本模型 ####

符号表中插入、查找都需要将一个值与符号表中的键进行比较，在学习符号表的实现时，会统计比较的次数来分析一种实现的成本，如果一种实现的比较次数很少，便考虑其访问数据结构的次数。

### 无序链表中的顺序查找 ###

可以使用链表作为符号表的简单实现，每个结点存储一个键值对。get()方法会遍历链表，将要查找的键依次与链表中的结点比较，匹配成功就返回结点的值，否则返回null；put()方法也会遍历链表，如果找到匹配的结点，就用要插入的值覆盖匹配结点的值，否则就在链表头部添加一个新的结点。

#### 实现 ####

public class SequentialSearchST<Key, Value> {
        private Node first;
        private int n;
    
        private class Node {
            Key key;
            Value val;
            Node next;
    
            public Node(Key key, Value val, Node next) {
                this.key = key;
                this.val = val;
                this.next = next;
            }
        }
    
        public Value get(Key key) {
            if (key == null)
                throw new IllegalArgumentException("argument to get() is null");
            for (Node x = first; x != null; x = x.next) {
                if (key.equals(x.key)) {
                    return x.val;
                }
            }
            return null;
        }
    
        public void put(Key key, Value value) {
            if (key == null)
                throw new IllegalArgumentException("first argument to put() is null");
    
            for (Node x = first; x != null; x = x.next) {
                if (key.equals(x.key)) {
                     x.val=value;
                     return;
                }
            }
            first = new Node(key, value, first);
            n++;
        }
        
        ...
    }

#### 性能 ####

对于一个含有N个键值对的基于无序链表的符号表来说：  
未命中的查找，需要N次比较，因为要遍历并比较链表中的所有键；  
插入操作，如果待插入的元素没在符号表中，也需要N次比较；  
对于命中的查找，最坏情况为N次比较，但平均情况下，命中的查找不需要这么多次比较。可以通过计算查找表中每个键的总次数，将其除以N来估算一次命中查找的平均比较次数，这种方法假设对符号表中每个键进行查找的可能性都相同，也称为随机命中。虽然实际应用中，不可能做到完全随机，但也基本吻合。  
在随机命中模式下，查找的总次数=第一个键的比较次数+第二个键的比较次数+...+第N个键的比较次数=1+2+...+N=N*(N+1)/2;平均比较次数=(N+1)/2。相当于与一半的元素进行比较。  
向空表中插入N个不同的键时，每次插入都需与已经插入的所有键比较，所以也需要1+2+..+N=N*(N+1)/2次比较。增长数量级为平方级别。

### 有序数组中的二分查找 ###

基于有序数组的符号表，这里使用的数据结构是一对平行的数组，一个存储键，一个存储值；也可以用一个由键值对构成的数据来实现。

#### 实现 ####

public class BinarySearchST<Key extends Comparable<Key>, Value> {
        private Key[] keys;
        private Value[] vals;
        private int N;
    
        public BinarySearchST(int capacity) {
            keys = (Key[]) new Comparable[capacity];
            vals = (Value[]) new Object[capacity];
        }
    
        public Value get(Key key) {
            if (isEmpty())
                return null;
            int i = rank(key);
            if (i < N && keys[i].compareTo(key) == 0) {
                return vals[i];
            } else {
                return null;
            }
        }
    
        public void put(Key key, Value val) {
            int i = rank(key);
            if (i < N && keys[i].compareTo(key) == 0) {
                vals[i] = val;
                return;
            }
            for (int j = N; j > i; j--) {
                keys[j] = keys[j - 1];
                vals[j] = vals[j - 1];
            }
            keys[i] = key;
            vals[i] = val;
            N++;
        }
    
        public int rank(Key key) {
            // return rankRecursion(key, 0, N - 1);
            return rankIteration(key, 0, N - 1);
        }
    
        public int rankRecursion(Key key, int lo, int hi) {
            // if (hi <= lo)
            if (hi < lo)
                return lo;
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) {
                return rankRecursion(key, lo, mid - 1);
            } else if (cmp > 0) {
                return rankRecursion(key, mid + 1, hi);
            } else {
                return mid;
            }
        }
    
        public int rankIteration(Key key, int lo, int hi) {
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int cmp = key.compareTo(keys[mid]);
                if (cmp < 0) {
                    hi = mid - 1;
                } else if (cmp > 0) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }
            return lo;
        }
    
        public Iterable<Key> keys() {
            return keys(keys[0], keys[N - 1]);
        }
    
        public Iterable<Key> keys(Key lo, Key hi) {
            if (lo == null)
                throw new IllegalArgumentException("first argument to keys() is null");
            if (hi == null)
                throw new IllegalArgumentException("second argument to keys() is null");
    
            Queue<Key> queue = new Queue<Key>();
            if (lo.compareTo(hi) > 0)
                return queue;
            for (int i = rank(lo, false); i < rank(hi, false); i++)
                queue.enqueue(keys[i]);
            if (get(hi) != null)
                queue.enqueue(keys[rank(hi, false)]);
            return queue;
        }
    }

这份实现的核心是rank方法，它返回表中小于给定键的键的数量。对于get方法，只要给定的键存在于表中，根据rank方法就可以知道去哪儿找到它；对于put方法，如果给定的键存在于表中，根据rank方法就可以知道去哪儿更新键对应的值，如果键不在表中，根据rank方法也可以知道应该将新的键值插入什么位置。插入的时候，会先将所有更大的键向后移动一格来腾出位置。

由于使用了有序数组，rank方法可以通过二分查找快速地找到键的位置。在查找时，先将被查找的键和子数组的中间键比较，如果被查找的键小于中间键，就在左子数组中继续查找，如果大于中间键，就在右子数组中继续查找，否则中间键就是被命中的键。  
rankRecursion和rankIteration分别用递归和迭代实现了这种算法。put方法在插入键值对时，由于使用了rank方法拿到待插入键的排序位置，可以保证符号表一直是有序的。

#### 性能 ####

在N个键的有序数组中进行二分查找时，先找到1个中间元素，然后在剩下的(N-1)/2个元素中继续二分查找，由此可得比较次数的关系式：  
C(N)<=C((N-1)/2)+1，其中1为与中间元素的1次比较；  
于是C(N)<=C(N/2)+1;  
而且有C(0)=0,C(1)=1;  
假设N的个数刚好为2的幂，即N=2^n, n=LgN;  
则：C(2^n)<=C(2^(n-1))+1;  
继续迭代直到n=0，可得：C(2^n)<=C(2^0)+n;  
将N=2^n, n=LgN代入上式可得：  
C(N)<=1+LgN。  
即N的个数刚好为2的幂时，最多需要LgN+1次比较；  
推广到一般的情况，可知查找的增长数量级为对数级别。  
查找操作的性能在对数级别，是非常快的，但插入操作的性能如何呢？  
在最坏的情况下，插入的位置在数组的最开头，所以插入前需要将所有的元素向后移动一格，键、值各一个数组，共需要2N次数组访问，插入前调用rank方法进行了LgN次比较，LgN相比2N较小可忽略，所以插入操作需要访问数组~2N次；  
向一个空符号表中插入N个元素，在最坏的情况下，每次都要插入数组的开头，共需2*N*(N-1)/2，约为~N^2次数组访问，所以插入操作的增长数量级为线性的，构建一个有序符号表则需要平方级别的时间，线性、平方级别的算法无法用于解决大规模的问题。

转载于:https://www.cnblogs.com/zhixin9001/p/11574407.html