《数据结构与算法之美》高级篇笔记

2021-05-01

摘要：极客时间《数据结构与算法之美》高级篇笔记，拓扑排序、最短路径算法、位图、概率统计、向量空间、B+ 树、A* 算法、索引、并行算法

拓扑排序（Topological Sorting）

拓扑排序本身就是基于有向无环图的一个算法。把源文件与源文件之间的依赖关系，抽象成一个有向图，同时还要是一个有向无环图。图可能不是连通的，由几个不连通的子图构成。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。a 先于 b 执行，也就是说 b 依赖于 a，那么就在顶点 a 和顶点 b 之间，构建一条从 a 指向 b 的边。

// 基础图类
public class Graph {
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) { // 每个顶点都可以指向其他顶点
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // s 先于 t，添加边 s->t
    adj[s].add(t);
  }
}

拓扑排序有两种实现方法：Kahn 算法和 DFS 深度优先搜索算法

Kahn 算法

Kahn 算法实际上用的是贪心算法思想，如果某个顶点的入度为 0，即没有其他顶点先于这个顶点执行，那么就可以从这个顶点开始执行，遍历该顶点所有的边。将所有入度为 0 的顶点都遍历一遍，即完成本次算法。个人感觉 Kahn 算法很像 BFS 算法，只是在一定条件下才将顶点入栈

public void topoSortByKahn() {
  int[] inDegree = new int[v]; // 统计每个顶点的入度
  for (int i = 0; i < v; ++i) {
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // 如果有 i->w
      inDegree[w]++;
    }
  }
  LinkedList<Integer> queue = new LinkedList<>();
  for (int i = 0; i < v; ++i) {
    if (inDegree[i] == 0) queue.add(i); // 链表中记录入度为 0 的顶点
  }
  while (!queue.isEmpty()) { // 按照链表顺序执行顶点
    int i = queue.remove(); // 从链表中移除该顶点
    System.out.print("->" + i);
    for (int j = 0; j < adj[i].size(); ++j) { // 遍历打印顶点所有的边
      int k = adj[i].get(j);
      inDegree[k]--;
      if (inDegree[k] == 0) queue.add(k); // 入度为 0 时加入队列，类似 BFS 算法
    }
  }
}

每个顶点被访问了一次，每个边也都被访问了一次，则其时间复杂度是 O(V+E)（V 表示顶点个数，E 表示边的个数）

DFS 算法

深度优先遍历思路：
1、先通过邻接表构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行；逆邻接表中，边 s->t 表示 s 依赖于 t，t 先于 s 执行
2、递归处理每个顶点。

public void topoSortByDFS() {
  // 先构建逆邻接表
  LinkedList<Integer> inverseAdj[] = new LinkedList[v];
  for (int i = 0; i < v; ++i) { // 申请空间
    inverseAdj[i] = new LinkedList<>();
  }
  for (int i = 0; i < v; ++i) { // 通过邻接表填充逆邻接表
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inverseAdj[w].add(i); // w->i
    }
  }
  boolean[] visited = new boolean[v];
  for (int i = 0; i < v; ++i) { // 深度优先遍历图，要遍历所有顶点
    if (visited[i] == false) {
      visited[i] = true;
      dfs(i, inverseAdj, visited);
    }
  }
}
// vertex：顶点索引；inverseAdj：逆邻接表；visited：是否访问的标识数组
private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
  for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
    int w = inverseAdj[vertex].get(i);
    if (visited[w] == true) continue; // 跳过访问过的顶点
    visited[w] = true;
    dfs(w, inverseAdj, visited); // 递归进入相连的顶点
  }
  // 把 vertex 这个顶点可达的所有顶点都打印出来之后，再打印它自己
  System.out.print("->" + vertex);
}

每个顶点被访问两次（去一次，来一次），每条边都被访问一次，所以时间复杂度也是 O(V+E)

最短路径算法（Shortest Path Algorithm）

如何在地图上规划一条最优出行路线？将岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度是边的权重，这样整个地图就抽象成一个有向有权图，将问题转化为：在一个有向有权图中，求两个顶点间的最短路径。

// 地图抽象类
public class Graph { // 有向有权图的邻接表表示
  private LinkedList<Edge> adj[]; // 邻接表
  private int v; // 顶点个数
  public Graph(int v) {
    this.v = v;
    this.adj = new LinkedList[v];
    for (int i = 0; i < v; ++i) {
      this.adj[i] = new LinkedList<>(); // 记录该顶点的所有边
    }
  }
  // 添加一条边
  public void addEdge(int s, int t, int w) {
    this.adj[s].add(new Edge(s, t, w));
  }
  // 边辅助类 
  private class Edge {
    public int sid; // 边的起始顶点编号
    public int tid; // 边的终止顶点编号
    public int w; // 权重（两点之间的距离）
    public Edge(int sid, int tid, int w) {
      this.sid = sid;
      this.tid = tid;
      this.w = w;
    }
  }
  // dijkstra 顶点辅助类
  private class Vertex {
    public int id; // 顶点编号 id
    public int dist; // 从起始顶点到这个顶点的距离
    public Vertex(int id, int dist) {
      this.id = id;
      this.dist = dist;
    }
  }
}

Dijkstra 算法

Dijkstra 算法是最出名的单源最短路径算法，其核心逻辑：
1、用 vertexes 数组记录从起始顶点到每个顶点的距离 dist，起初 dist 都初始化为无穷大，起始顶点的 dist 为 0，然后将其放入队列中；
2、从优先级队列中取出 dist 最小的顶点 minVertex，然后找到这个顶点可达的所有顶点 nextVertex。如果 minVertex 的 dist 值加上 minVertex 与 nextVertex 之间边的权重 w 小于 nextVertex 当前的 dist 值，那么把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w 。
3、把 nextVertex 加入到优先级队列中，不断重复这个过程，直到找到终止顶点 t 或者队列为空。

// 从顶点 s 到顶点 t 的最短路径
public void dijkstra(int s, int t) {
  int[] predecessor = new int[this.v]; // 用来还原最短路径
  Vertex[] vertexes = new Vertex[this.v];
  for (int i = 0; i < this.v; ++i) { // 初始化距离为无穷大
    vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
  }
  PriorityQueue queue = new PriorityQueue(this.v); // 小顶堆
  boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
  vertexes[s].dist = 0; // 起始顶点的 dist 为 0
  queue.add(vertexes[s]); // 将起始点加入小顶堆
  inqueue[s] = true;
  while (!queue.isEmpty()) {
    Vertex minVertex= queue.poll(); // 取堆顶元素并删除
    if (minVertex.id == t) break; // 最短路径产生了
    for (int i = 0; i < adj[minVertex.id].size(); ++i) { // 遍历顶点所有边
      Edge e = adj[minVertex.id].get(i); // 取出一条 minVetex 相连的边
      Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
      if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist
        nextVertex.dist = minVertex.dist + e.w;
        predecessor[nextVertex.id] = minVertex.id; // 记录每个顶点的前驱顶点
        if (inqueue[nextVertex.id] == true) { // 顶点只需要进入一次，防止重复进入队列
          queue.update(nextVertex); // 更新队列中的 dist 值
        } else {
          queue.add(nextVertex);
          inqueue[nextVertex.id] = true;
        }
      }
    }
  }
  // 输出最短路径
  System.out.print(s);
  print(s, t, predecessor);
}
private void print(int s, int t, int[] predecessor) {
  if (s == t) return;
  print(s, predecessor[t], predecessor);
  System.out.print("->" + t);
}

// 使用小顶堆可以确保堆顶的节点都是目前阶段的最短路径的节点
private class PriorityQueue { // 根据 vertex.dist 构建小顶堆
  private Vertex[] nodes;
  private int count;
  public PriorityQueue(int v) { 
    this.nodes = new Vertex[v+1];
    this.count = v;
  }
  public Vertex poll() {
    Vertex v = nodes[1]; // 返回堆顶原始
    nodes[1] = nodes[count]; // 将最后一个元素添加到堆顶，自上而下堆化
    --count;
    heapifyUpToDown(1);//堆顶从上而下堆化
    return v;
  }
  public void add(Vertex vertex) {
    nodes[++count] = vertex;
    vertex.i = count;
    heapifyDownToUp(count); // 从下往上堆化
  }
  // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
  public void update(Vertex vertex) { 
    // 查找，并更新
    nodes[vertex.i].dist = vertex.dist;
    heapifyDownToUp(vertex.i); // 从下往上堆化
  } 
  public boolean isEmpty() { 
    return this.count == 0 ? true : false;
  }
  // 自上而下堆化
  private void heapifyUpToDown(int i) {
    while(i<=count){
      int maxPos = i;
      if((i*2)<=count && nodes[maxPos].dist > nodes[i*2].dist) maxPos = 2*i;
      else if((i*2+1)<=count && nodes[maxPos].dist > nodes[i*2+1].dist) maxPos = 2*i+1;
      else if(maxPos == i) break;
      swap(i, maxPos); // 交换
      i = maxPos;
    }
  }
  // 从下往上堆化
  private void heapifyDownToUp(int i) {
    while (i / 2 > 0 && nodes[i].dist < nodes[i / 2].dist) {
      swap(i, i/2); // 交换
      i = i / 2;
    }
  }
  // 数据交换
  private void swap(int i, int maxPos) {
    nodes[i].i = maxPos; // 下标交换记录
    nodes[maxPos].i = i;
    Vertex tmp = nodes[i];
    nodes[i] = nodes[maxPos];
    nodes[maxPos] = tmp;
  }
}

predecessor 数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。inqueue 数组是为了避免将一个顶点多次添加到优先级队列中
分析其时间复杂度，最复杂就是 while 循环嵌套 for 循环这部分代码。while 循环最多会执行 V 次（V 表示顶点的个数），内部的 for 循环的执行次数跟每个顶点相邻的边的个数有关，但总次数最大（遍历全部顶点）也不会超过图中所有边的个数 E（E 表示边的个数），同时 for 循环内部的代码涉及从优先级队列数据的添加、获取和更新这三种操作。而优先级队列是用堆来实现的，这些操作的时间复杂度都是 O(logV)（堆中的元素个数不会超过顶点的个数 V）。则综合而言，利用乘法原则，整个代码的时间复杂度就是 O(E*logV)

位图（BitMap）

位图通过数组下标来定位数据，因而访问效率非常高。而且每个数字用一个二进制位来表示，在数字范围不大的情况下，非常节省内存空间。

// Java 中 char 类型是 2 个字节占 16bit
public class BitMap {
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits; // 存储数据范围，最大值
    this.bytes = new char[nbits/16+1]; // 存储数据的数组
  }

  public void set(int k) {
    if (k > nbits) return; // 超出范围
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex); // 找到对应下标设置为 1，| 将两个数进行位于位的 或 操作，只要有一个为 1 就会得到 1，例如：11110000 | 00111100 => 11111100
  }

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0; // & 将两个数进行位于位的 与 操作，同位上的数值都为 1 才会得到 1 ，例如：00001111 & 00001000 => 00001000
  }
}

布隆过滤器（Bloom Filter）

当数字的范围很大的时候，位图可能会有很多空位，反而比其他数据结构占用更多内存。此时，就需要布隆过滤器。布隆过滤器是对位图的一种改进。
假设数据个数是 1 千万，数据的范围是 1 到 10 亿。布隆过滤器的做法是使用 K 个哈希函数，对同一个数字进行求哈希值，将这 K 个数字作为位图中的下标，位图中对应的元素都设置为 true，也就是说用这 K 个二进制来表示一个数子的存在。如果要判断某个数字是否存在，就要用这 K 个哈希函数分别得到对应的哈希值，如果这 K 个值在位图中都为 true，说明这个数字存在，如果任意一个不为 true，说明不存在。使用多个哈希函数使得哈希冲突降低了，但这容易造成误判的情况：数字一在 1，2，3 位上为 true，数字二在 4，5，6 位上为 true，如果数字三为 3，4，5，在数字三未操作的情况下会对其产生误判。它只会对存在的情况有误判，如果某个数字经过布隆过滤器判断不存在，那么它是真的不存在；如果判断存在，这有误判的可能。调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例可以降低误判的概率

概率统计（probability statics）

可以通过黑名单来过滤短信和电话，号码的黑名单可以由用户主动标记，使用布隆过滤器可以大大减少存储使用的内存空间。如果把黑名单存储到服务器端，每次来信都将号码发送到服务器端进行判断，这样更节省内存但必须联网且耗时。如果有大量的样本，可以进行分词处理，找到垃圾短信中出现频率远超正常短信中的单词，那么这个特殊单词就可以用来过滤垃圾短信。还可以预设一些规则来过滤垃圾短信，比如有敏感信息、固定模板词汇等，但这些都很容易被不怀好意者规避掉。基于朴素贝叶斯算法的概率统计方式过滤短信可以更高效。

把短信抽象成一组计算机可以理解并且方便计算的特征项，用这一组特征项全权代表这个短信。把一个短信分割成 w1、w2、…、wn 这 n 个单词，这 n 个单词就是一组特征项。判定一个短信是否是垃圾短信这个问题，就变成了判定同时包含这几个单词的短信是否是垃圾短信，即求概率P(短信是垃圾短信|w1,w2,...,wn 同时出现)。短信样本中同时出现这 n 个单词的样本极少，概率不可算，不好实践。但应用朴素贝叶斯公式得到P(短信是垃圾短信|w1,w2,...,wn 同时出现)=P(w1,w2,...,wn 同时出现|短信是垃圾短信)*P(短信是垃圾短信)/P(w1,w2,...,wn 同时出现)。其中P(w1,w2,...,wn 同时出现|短信是垃圾短信)同样不好算，但使用条独立事件发生概率的计算公式P(A*B)=P(A)*P(B)，可以将其分解P(w1,w2,...,wn 同时出现|短信是垃圾短信)=P(w1出现|短信是垃圾短信)*P(w2出现|短信是垃圾短信)*..*P(wn出现|短信是垃圾短信)。这样，计算出每个单词在垃圾短信的出现概率即可得到P(w1,w2,...,wn 同时出现|短信是垃圾短信)，把样本中垃圾短信的个数除以总样本短信个数即可得到P(短信是垃圾短信)，但P(w1,w2,...,wn 同时出现)仍无法计算。但实际上没必要非得计算这一部分的概率值：可以同时计算包含这 n 个单词的短信是垃圾短信和非垃圾短信的概率。假设它们分别是 p1 和 p2，不是单纯的通过p1 的值的大小判断是否是垃圾短信，而是通过对比 p1 和 p2 的值的大小来判断短信是否为垃圾短信。
p1/p2
求解 p1/p2 也就不需要计算P(w1,w2,...,wn 同时出现)，如果 p1/p2 很大，那么大概率是垃圾短信。实际上，可以综合黑名单、制定规则、概率统计等多种方式的判断结果来提高拦截的准确率。

向量空间（Vector Space）

推荐可能会喜爱的音乐思路：
1、找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；
2、找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你。

基于相似用户做推荐

简单的方法是遍历所有的用户，对比每个用户和目标有共同喜爱的歌曲个数，并且设置一个阈值，如果目标和某个用户共同喜爱的歌曲个数超过这个阈值，说明两者的口味相似。
基于相似用户做推荐简单方法
复杂些的方法是计算欧几里得距离。欧几里得距离计算公式：
EuclideanDistance
给分享、收藏、点赞等行为定义一个分数，分析所有用户对每首歌曲的喜爱程度（总分），用一个向量表示。两个向量之间的欧几里得距离，作为两个用户的口味相似程度的度量。距离越近则口味越相似
基于相似用户做推荐复杂方法

基于相似歌曲做推荐

对于两首歌，如果喜欢听的人群都是差不多的，那侧面就可以反映出，这两首歌比较相似。基于相似用户的推荐方法中，针对每个用户，将对各个歌曲的喜爱程度作为向量。基于相似歌曲的推荐思路中，针对每个歌曲，将每个用户的打分作为向量(把歌曲和用户主次颠倒了一下)。这样就有了每个歌曲的向量表示，通过计算向量之间的欧几里得距离，来表示歌曲之间的相似度。距离越小说明相似度越高
基于相似歌曲做推荐

B+ 树

m 阶 B+ 树的特点：
1、每个节点中子节点的个数不能超过 m，也不能小于 m/2；
2、根节点的子节点个数可以不超过 m/2，这是一个例外；
3、m 叉树只存储索引，并不真正存储数据，这个有点儿类似跳表；
4、通过链表将叶子节点串联在一起，这样可以方便按区间查找；
5、一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。
B+ 树是 B 树的改进版，B- 树就是 B 树，这里的“-”是连接符。B 树跟 B+ 树的不同点主要集中在这几点：
1、B 树中间结点的元素个数比子结点数少 1，B+ 树中间结点的元素个数与子结点数一样；
2、B 树中的节点存储数据，而 B+ 树中的节点只存索引；
3、B 树中的叶子节点并不需要链表来串联。

A* 算法

Dijkstra 算法十分耗时，在权衡路线规划质量和执行效率的情况下，只需要寻求一个次优解就足够了。A* 算法是对 Dijkstra 算法的优化和改造，它利用估价函数判断哪个顶点优先出列，短时间内找到一个次优解。估价函数f(i)=g(i)+h(i)，其中 g(i)（i 表示顶点编号）是从起点走到这个顶点的路径长度，h(i)（i 表示这个顶点的编号）是启发函数。启发函数是顶点跟终点之间的直线距离，即欧几里得距离。但欧几里得距离计算时涉及到比较耗时的根号开方计算，一般使用曼哈顿距离（两点之间横纵坐标的距离之和）代替。

// 曼哈顿距离
int hManhattan(Vertex v1, Vertex v2) { 
  // Vertex表示顶点，后面有定义 
  return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}

A* 算法与 Dijkstra 算法主要有三点区别：
1、优先级队列构建的方式不同。A* 算法是根据 f 值（g(i)+h(i)），Dijkstra 算法是根据 dist 值（g(i)）；
2、A* 算法在更新顶点 dist 值的时候，会同步更新 f 值；
3、循环结束的条件也不一样。A* 算法是一旦遍历到终点就结束，Dijkstra 算法是在终点出队列的时候才结束。

// 地图抽象类
public class Graph { // 有向有权图的邻接表表示
  private LinkedList<Edge> adj[]; // 邻接表
  private int v; // 顶点个数
  public Graph(int v) {
    this.v = v;
    this.adj = new LinkedList[v];
    for (int i = 0; i < v; ++i) {
      this.adj[i] = new LinkedList<>(); // 记录该顶点的所有边
    }
  }
  // 添加一条边
  public void addEdge(int s, int t, int w) {
    this.adj[s].add(new Edge(s, t, w));
  }
  // 边辅助类 
  private class Edge {
    public int sid; // 边的起始顶点编号
    public int tid; // 边的终止顶点编号
    public int w; // 权重（两点之间的距离）
    public Edge(int sid, int tid, int w) {
      this.sid = sid;
      this.tid = tid;
      this.w = w;
    }
  }
  // 顶点辅助类
  private class Vertex {
    public int id; // 顶点编号ID
    public int dist; // 从起始顶点，到这个顶点的距离，也就是g(i)
    public int f; // 新增：f(i)=g(i)+h(i)
    public int x, y; // 新增：顶点在地图中的坐标（x, y）
    public Vertex(int id, int x, int y) {
      this.id = id;
      this.x = x;
      this.y = y;
      this.f = Integer.MAX_VALUE;
      this.dist = Integer.MAX_VALUE;
    }
  }
  // Graph类的成员变量，在构造函数中初始化
  Vertex[] vertexes = new Vertex[this.v];
  // 新增一个方法，添加顶点的坐标
  public void addVetex(int id, int x, int y) {
    vertexes[id] = new Vertex(id, x, y)
  }

  // A* 算法
  public void astar(int s, int t) { // 从顶点 s 到顶点 t 的路径
    int[] predecessor = new int[this.v]; // 用来还原路径
    // 按照 vertex 的 f 值构建的小顶堆，而不是按照 dist
    PriorityQueue queue = new PriorityQueue(this.v);
    boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
    vertexes[s].dist = 0;
    vertexes[s].f = 0;
    queue.add(vertexes[s]);
    inqueue[s] = true;
    while (!queue.isEmpty()) {
      Vertex minVertex = queue.poll(); // 取堆顶元素并删除
      for (int i = 0; i < adj[minVertex.id].size(); ++i) {
        Edge e = adj[minVertex.id].get(i); // 取出一条 minVetex 相连的边
        Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
        if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist,f
          nextVertex.dist = minVertex.dist + e.w;
          nextVertex.f = nextVertex.dist + hManhattan(nextVertex, vertexes[t]);
          predecessor[nextVertex.id] = minVertex.id;
          if (inqueue[nextVertex.id] == true) {
            queue.update(nextVertex);
          } else {
            queue.add(nextVertex);
            inqueue[nextVertex.id] = true;
          }
        }
        if (nextVertex.id == t) { // 只要到达 t 就可以结束 while
          queue.clear(); // 清空 queue，才能推出 while 循环
          break; 
        }
      }
    }
    // 输出路径
    System.out.print(s);
    print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
  }
}

索引

设计索引的过程中，需要考虑到的一些因素：
1、功能性需求：数据是格式化数据还是非格式化数据；数据是静态数据还是动态数据；索引存储在内存还是硬盘；单值查找还是区间查找；单关键词查找还是多关键词组合查找。
2、非功能性需求：不管是存储在内存中还是磁盘中，索引对存储空间的消耗不能过大；在考虑索引查询效率的同时，我们还要考虑索引的维护成本。
构建索引常用的数据结构：散列表、红黑树、B+ 树、跳表、位图、布隆过滤器、有序数组。前四个利用快速增删改查构建索引；位图和布隆过滤器占用内存少，当两者判断数据不存在时不需要进行查询，只有判断存在时会进行查询，提高查询效率；存储静态数据时不存在插入、删除、更新操作，可以用有序数组存储关键词，然后用二分法进行快速查找。

并行算法

当算法无法再继续优化的情况下，提高执行效率：
1、并行排序：
对归并排序并行化处理。将大块数据分割成多个小块数据，然后多个线程对小块数据进行排序，最后再将多个有序集进行合并
对快速排序并行化处理。遍历数据，找到合适的区间进行分割，分割后多线程进行并行排序
两个方法都是利用分治的思想，对数据进行分片，然后并行处理。第一种处理思路是，先随意地对数据分片，排序之后再合并。第二种处理思路是，先对数据按照大小划分区间，然后再排序，排完序就不需要再处理。如果数据非常大，还要减少磁盘 IO 操作
2、并行查找
将数据分割成 k 份进行存储，构建的索引也将是原来的 1/k。即使对某个索引进行扩容，也会比原来消耗的更少，查找时 k 个线程并行查找数据，比起一个大散列表的做法，性能也并不会下降。
3、并行字符串匹配
当处理超级大的文本时，可以将字符串分割成多个小块。假设关键词的长度是 m，小块文本的起止可以多取 m 个字符，然后多个线程并行匹配文本
4、并行搜索
利用两个队列 A 和 B 优化广度优先搜索算法：多线程并行处理队列 A 中的顶点，并将扩展得到的顶点存储在队列 B 中。等队列 A 中的顶点都处理完成，队列 A 被清空。此时，再并行地扩展队列 B 中的顶点，并将扩展出来的顶点存储在队列 A。循环使用两个队列，加快执行速度。