基于数据结构和算法的业务应用(一)数据结构、算法到底什么？算法如何再业务中应用？
一 概述
1.1 数据结构的概述
1.1.1 概述
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
1.1.2 划分
数据结构我们关注的维度不一样，划分的方式不一样。数据结构可以分为逻辑结果和物理结构。
- 逻辑结构 逻辑结构，反应元素之间的逻辑关系。逻辑关系是指元素之间的前后间是什么形式关联，这与他们在计算机中的存储位置无关。类型如下：
线性结构：一对一关联，队形
树形结构：一对多关联，树形
图形结构：多对多关联，网状
数据物理结构指的是逻辑结构在计算机存储空间中的存放形式(也称为存储结构)。一般来说，一种数据结构的
逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。- 物理结构 数据在计算机存储位置
顺序存储：用一组地址连续的存储单元依次存储集合的各个数据元素，可随机存取，但增删需要大批移动
链式存储：不要求连续，每个节点都由数据域和指针域组成，占据额外空间，增删快，查找慢需要遍历
索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。检索快，空间占用大
哈希存储：将数据元素的存储位置与关键码之间建立确定对应关系，检索快，存在映射函数碰撞问题1.1.3 程序中常见数据结构
每一种数据结构都在上述的逻辑结构和物理结构找到对应。
代码语言：javascript复制数组(Array)：连续存储，线性结构，可根据偏移量随机读取，扩容困难
栈( Stack)：线性存储，只允许一端操作，先进后出，类似水桶
队列(Queue)：类似栈，可以双端操作。先进先出，类似水管
链表( LinkedList)：链式存储，配备前后节点的指针，可以是双向的
树( Tree)：典型的非线性结构，从唯一的根节点开始，子节点单向执行前驱（父节点）
图(Graph)：另一种非线性结构，由节点和关系组成，没有根的概念，互相之间存在关联
堆(Heap)：特殊的树，特点是根结点的值是所有结点中最小的或者最大的，且子树也是堆
散列表(Hash)：源自于散列函数，将值做一个函数式映射，映射的输出作为存储的地址1.2 算法的概述
算法指的是基于存储结构下，采用什么方式可以更有效的处理数据。数据的 运算是定义在数据结构的逻辑上，但是运算的具体实现要做存储结构上进 一般涉及操作有以下几种：
代码语言：javascript复制检索：在数据结构里查找满足一定条件的节点。
插入：往数据结构中增加新的节点，一般有一点位置上的要求。
删除：把指定的结点从数据结构中去掉，本身可能隐含有检索的需求。
更新：改变指定节点的一个或多个字段的值，同样隐含检索。
排序：把节点里的数据，按某种指定的顺序重新排列，例如递增或递减。1.3 复杂度
1.3.1 时间复杂度
为了某种运算而花费的时间，使用大写O表示。一般来讲，时间是一个不太容易计量的维度，而为了计算时间复杂度，通常会估计算法的操作单元数量，而假定每个单元运行的时间都是相同的。一般来讲，常见时间复杂度有以下几种：
- 常数阶O(1)：时间与数据规模无关，如交换两个变量值
int i=1,j=2,k
k=i;i=j;j=k;- 线性阶O(n)：时间和数据规模呈线性，可以理解为n的1次方，如单循环里的操作
for(i=1;i<=n;i ){
do();
}- k次方阶O(nk)：执行次数是数量的k次方，如多重循环，以下为2次方阶(n2)实例
for(i=1;i<=n;i ){
for(j=1;j<=n;j ){
do();
}
}- 指数阶O(2n)：随着n的上升，运算次数呈指数增长
for(i=1;i<= 2^n;i ){
do();
}- 对数阶O(log2n)：执行次数呈对数缩减，如下
for(i=1;i<=n;){
i=2^i;
do();
}- 线性对数阶O(nlog2n)：在对数阶的基础上，进行线性n倍乘积
for(i=1;i<=2^n;i ){
for(j=1;j<=n;j ){
do();
}
}- 总结
时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)<...＜Ο(nk)＜Ο(2n)＜Ο(n!)
1.3.2 空间复杂度()
空间复杂度是对一个算法在运行过程中占用内存空间大小的度量。一个程序执行时除了需要存 储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的辅助空间。而空间复杂 度主要指的是这部分空间的量级。
- 固定空间
主要包括指令空间、常量、简单变量等所占的空间，这部分空间的大小与运算的数据多少无关，属于静态空间。- 可变空间
主要包括运行期间动态分配的临时空间，以及递归栈所需的空间等，这部分的空间大小与算法有
很大关系。- 空间复杂度的分类 同样，空间复杂度也用大写O表示，相比时间复杂度场景相对简单，常见级别为O(1)和O(n)，以数组逆序为例： 1）O(1)：常数阶，所占空间和数据量大小无关。
//定义前后指针，和一个临时变量，往中间移动
//无论a多大，占据的临时空间只有一个temp
int[] a={1,2,3,4,5};
int i=0,j=a.length‐1;
while (i<=j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
i ;
j‐‐;
}2）O(n)：线性阶，与数据量大小呈线性关系
代码语言：javascript复制//定义一个和a同等大小的数组b，与运算量a的大小呈线性关系
//给b赋值时，倒序取a
int[] a={1,2,3,4,5};
int[] b=new int[a.length];
for (int i = 0; i < a.length; i ) {
b[i]=a[a.length‐1‐i];
}1.3.3 类比
代码语言：javascript复制对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。时间复杂度低可能借助占用大的存储空间来弥补，
反之，某个算法所占据空间小，那么可能就需要占用更多的运算时间。两者往往需要达到一种权衡。
在特定环境下的业务，还需要综合考虑算法的各项性能，如使用频率，数据量的大小，所用的开发语言，运行的机
器系统等。两者兼顾权衡利弊才能设计出最适合当前场景的算法。
1.4 算法思想
1.4.1 分而治之
把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题小到可 以简单的直接求解，原问题的解即子问题的解的合并。
- 分治法对问题有一定的要求：
该问题缩小到一定程度后，就可以轻松解决
问题具有可拆解性，不是一团无法拆分的乱麻
拆解后的答案具有可合并性。能组装成最终结果
拆解的子问题要相互独立，互相之间不存在或者很少有依赖关系1.4.2 动态规划
将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的 解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有 可能达到最优的局部解，丢弃其他。依次解决各子问题，最后一个子问题就是初始问题的解。
- 动态规划算法同样有一定的适用性场景要求：
最优化解：拆解后的子阶段具备最优化解，且该最优化解与追踪答案方向一致
流程向前，无后效性：上一阶段的解决方案一旦确定，状态就确定，只会影响下一步，而不会反向影响
阶段关联：上下阶段不是独立的，上一阶段会对下一阶段的行动提供决策性指导。这不是必须的，但是如果
具备该特征，动态规划算法的意义才能更大的得到体现1.4.3 贪心算法
同样对问题要求作出拆解，但是每一步，以当前局部为目标，求得该局部的最优解。那么最终问题解决时，得到完 整的最优解。也就是说，在对问题求解时，总是做出在当前看来是最好的选择，而不去从整体最优上加以考虑。从 这一角度来讲，该算法具有一定的场景局限性。
- 使用场景
要求问题可拆解，并且拆解后每一步的状态无后效性（与动态规划算法类似）
要求问题每一步的局部最优，与整体最优解方向一致。至少会导向正确的主方向。1.4.4 回溯算法
回溯算法实际上是一个类似枚举的搜索尝试过程，在每一步的问题下，列举可能的解决方式。选择某个方案往深度 探究，寻找问题的解，当发现已不满足求解条件，或深度达到一定数量时，就返回，尝试别的路径。回溯法一般适 用于比较复杂的，规模较大的问题。有“通用解题法”之称。
代码语言：javascript复制问题的解决方案具备可列举性，数量有限
界定回溯点的深度。达到一定程度后，折返1.4.5 分支限界
与回溯法类似，也是一种在空间上枚举寻找最优解的方式。但是回溯法策略为深度优先。分支法为广度优先。分支 法一般找到所有相邻结点，先采取淘汰策略，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从存活表 中选择一个结点作为下一个操作对象。
二 失效算法与应用
失效算法常见于缓存系统中。因为缓存往往占据大量内存，而内存空间是相对昂贵，且空间有限的，那么针对一部 分值，就要依据相应的算法进行失效或移除操作。
2.1 先来先淘汰（FIFO）
- 概述 First In First Out，先来先淘汰。这种算法在每一次新数据插入时，如果队列已满，则将最早插入的数据移除。
- 实现 可以方便的借助LinkedList来实现
public class FIFO {
LinkedList<Integer> fifo = new LinkedList<Integer>();
int size = 3;
//添加元素
public void add(int i) {
fifo.addFirst(i);
if (fifo.size() > size) {
fifo.removeLast();
}
print();
}
//缓存命中
public void read(int i) {
Iterator<Integer> iterator = fifo.iterator();
while (iterator.hasNext()) {
int j = iterator.next();
if (i == j) {
System.out.println("find it!");
print();
return;
}
}
System.out.println("not found!");
print();
}
//打印缓存
public void print() {
System.out.println(this.fifo);
}
//测试
public static void main(String[] args) {
FIFO fifo = new FIFO();
System.out.println("add 1‐3:");
fifo.add(1);
fifo.add(2);
fifo.add(3);
System.out.println("add 4:");
fifo.add(4);
System.out.println("read 2:");
fifo.read(2);
System.out.println("read 100:");
fifo.read(100);
System.out.println("add 5:");
fifo.add(5);
}
}- 结果展示和分析
总结： 实现容易。但是不管元素的使用情况，哪怕有些被频繁使用的数据也会被踢掉。
2.2 最久未用淘汰(LRU)
LRU全称是Least Recently Used，即淘汰最后一次使用时间最久远的数值。下面仍然以链表为例：新加入的数据放在头部，最近访 问的，也移到头部，空间满时，将尾部元素删除。
代码语言：javascript复制public class LRU {
LinkedList<Integer> lru = new LinkedList<Integer>();
int size = 3;
//添加元素
public void add(int i) {
lru.addFirst(i);
if (lru.size() > size) {
lru.removeLast();
}
print();
}
//缓存命中
public void read(int i) {
Iterator<Integer> iterator = lru.iterator();
int index = 0;
while (iterator.hasNext()) {
int j = iterator.next();
if (i == j) {
System.out.println("find it!");
lru.remove(index);
lru.addFirst(j);
print();
return;
}
index ;
}
System.out.println("not found!");
print();
}
//打印缓存
public void print() {
System.out.println(this.lru);
}
//测试
public static void main(String[] args) {
LRU lru = new LRU();
System.out.println("add 1‐3:");
lru.add(1);
lru.add(2);
lru.add(3);
System.out.println("add 4:");
lru.add(4);
System.out.println("read 2:");
lru.read(2);
System.out.println("read 100:");
lru.read(100);
System.out.println("add 5:");
lru.add(5);
}
}- 结果分析
2.3 最近最少用淘汰（LFU）
- 概述
Least Frequently Used，即最近最少使用。它要淘汰的是最近一段时间内，使用次数最少的值。- 实现 可以认为比LRU多了一重判断。LFU需要时间和次数两个维度的参考指标。需要注意的是，两个维度就可能涉及到同一时间段内， 访问次数相同的情况，就必须内置一个计数器和一个队列，计数器算数，队列放置相同计数时的访问时间。
public class Dto implements Comparable<Dto> {
private Integer key;
private int count;
private long lastTime;
public Dto(Integer key, int count, long lastTime) {
this.key = key;
this.count = count;
this.lastTime = lastTime;
}
@Override
public int compareTo(Dto o) {
int compare = Integer.compare(this.count, o.count);
return compare == 0 ? Long.compare(this.lastTime, o.lastTime) : compare;
}
@Override
public String toString() {
return String.format("[key=%s,count=%s,lastTime=%s]", key, count, lastTime);
}
public Integer getKey() {
return key;
}
public void setKey(Integer key) {
this.key = key;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public long getLastTime() {
return lastTime;
}
public void setLastTime(long lastTime) {
this.lastTime = lastTime;
}
}public class LFU {
private final int size = 3;
private Map<Integer, Integer> cache = new HashMap<>();
private Map<Integer, Dto> count = new HashMap<>();
//投放
public void put(Integer key, Integer value) {
Integer v = cache.get(key);
if (v == null) {
if (cache.size() == size) {
removeElement();
}
count.put(key, new Dto(key, 1, System.currentTimeMillis()));
} else {
addCount(key);
}
cache.put(key, value);
}
//读取
public Integer get(Integer key) {
Integer value = cache.get(key);
if (value != null) {
addCount(key);
return value;
}
return null;
}
//淘汰元素
private void removeElement() {
Dto dto = Collections.min(count.values());
cache.remove(dto.getKey());
count.remove(dto.getKey());
}
//更新计数器
private void addCount(Integer key) {
Dto Dto = count.get(key);
Dto.setCount(Dto.getCount() 1);
Dto.setLastTime(System.currentTimeMillis());
}
//打印缓存结构和计数器结构
private void print() {
System.out.println("cache=" cache);
System.out.println("count=" count);
}
public static void main(String[] args) {
LFU lfu = new LFU();
//前3个容量没满，1,2,3均加入
System.out.println("add 1‐3:");
lfu.put(1, 1);
lfu.put(2, 2);
lfu.put(3, 3);
lfu.print();
//1,2有访问，3没有，加入4，淘汰3
System.out.println("read 1,2");
lfu.get(1);
lfu.get(2);
lfu.print();
System.out.println("add 4:");
lfu.put(4, 4);
lfu.print();
//2=3次，1,4=2次，但是4加入较晚，再加入5时淘汰1
System.out.println("read 2,4");
lfu.get(2);
lfu.get(4);
lfu.print();
System.out.println("add 5:");
lfu.put(5, 5);
lfu.print();
}
}- 结果分析
2.4 应用案例
- redis属于缓存失效的典型应用场景，常见策略如下：
noeviction: 不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息（ 比较危险）。
allkeys-lru：对所有key，优先删除最近最少使用的 key (LRU)。
allkeys-random： 对所有key， 随机删除一部分（听起来毫无道理）。
volatile-lru：只限于设置了 expire 的key，优先删除最近最少使用的key (LRU)。
volatile-random：只限于设置了 expire 的key，随机删除一部分。
volatile-ttl：只限于设置了 expire 的key，优先删除剩余时间(TTL) 短的key。三 调度算法与应用
调度算法常见于操作系统中，因为系统资源有限，当有多个进程（或多个进程发出的请求）要使用这些资源时，就 必须按照一定的原则选择进程（请求）来占用资源。这就是所谓的调度。
3.1 先来先服务（FCFS）
- 概念 按照服务提交申请的顺序，依次执行。
- 实现 定义一个Task类作为任务实例，BlockingQueue作为服务队列
public class Task {
//任务名称
private String name;
//任务提交的时间
private Long addTime;
//任务的执行时间长短
private int servTime;
public Task(String name, int servTime) {
this.name = name;
this.servTime = servTime;
this.addTime = System.currentTimeMillis();
}
public void execute() {
try {
// ！重点：执行时睡眠，表示该任务耗时servTime毫秒
Thread.currentThread().sleep(servTime);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(String.format("execute:name=%s,addTime=%s,servTime=%s", name,
addTime, servTime));
}
}public class FCFS {
public static void main(String[] args) throws InterruptedException {
//阻塞队列，FCFS的基础
final LinkedBlockingQueue<Task> queue = new LinkedBlockingQueue(5);
//服务线程，任务由该线程获取和执行
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
queue.take().execute();
} catch (Exception e) {
e.printStackTrace();
}
}
}
}).start();
//向队列中放入一个任务
for (int i = 0; i < 5; i ) {
System.out.println("add task:" i);
queue.put(new Task("task" i, new Random().nextInt(1000)));
}
}
}
3. 优缺点
代码语言：javascript复制多应用于cpu密集型任务场景，对io密集型的不利。
时间相对均衡的业务可以排队处理，比如现实中排队打卡进站。
如果业务需要依赖大量的外部因素，执行时间片长短不一，FCFS算法不利于任务的整体处理进度，可能会因
为一个长时间业务的阻塞而造成大量等待。3.2 短作业优先 （SJF）
- 概念 执行时间短的优先得到资源。即执行前申报一个我需要占据cpu的时间，根据时间长短，短的优先被调度。我不占 时间所以我先来。
- 实现 使用TreeMap可以实现优先级的任务排序。
public class SJF {
public static void main(String[] args) throws InterruptedException {
//有序Map，将服务时间作为key排序
final TreeMap<Integer, Task> treeMap = new TreeMap();
//向队列中放入5个任务
for (int i = 0; i < 5; i ) {
System.out.println("add task:" i);
int servTime = new Random().nextInt(1000);
//注意，key是servTime，即执行预估时间
treeMap.put(servTime, new Task("task" i, servTime));
}
//服务线程，任务由该线程获取和执行
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
//有序Map中，服务时间短的，置于顶部，那么自然就会优先被取出
Map.Entry<Integer, Task> entry = treeMap.pollFirstEntry();
if (entry == null) {
Thread.currentThread().sleep(100);
} else {
entry.getValue().execute();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
}).start();
}
}- 结果分析
- 优缺点
适用于任务时间差别较大的场景，仍然以进站为例，拿出公交卡的优先刷卡，还没办卡的让一让。
解决了FCFS整体处理时间长的问题，降低平均等待时间，提高了系统吞吐量。
未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理
对长作业的不利，可能等待很久而得不到执行
时间基于预估和申报，主观性因素在内，无法做到100%的精准3.3 时间片轮转（RR）
- 概念 时间片逐个扫描轮询，轮到谁谁执行。类似一个圆转盘在周围能存若干个元素，元素新增的时候随机的,哪里有位置放哪里。在执行的时候，转动转盘来执行，转盘上每个存放元素的位置都能轮上。
- 实现 基于数组做为数据插槽方式实现。
public class RR {
//定义数组作为插槽，每个插槽中可以放入任务
Integer[] integers;
//length插槽的个数
public RR(int length) {
integers = new Integer[length];
}
//将任务放入插槽
public void addTask(int value) {
int slot = 0;
//不停查找空的插槽
while (true) {
//发现空位，将当前任务放入
if (integers[slot] == null) {
integers[slot] = value;
System.out.println(String.format("‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐>add task index = % s, value = % s ",slot,value));
break;
}
//如果当前位置有任务占用，看下一个位置
slot ;
//如果插槽遍历完还是没有空位置，那么从头开始再找，继续下一个轮回
if (slot == integers.length) {
slot = 0;
}
}
}
//执行任务。轮询的策略就在这里
public void execute() {
//开启一个线程处理任务。在现实中可能有多个消费者来处理
new Thread(new Runnable() {
@Override
public void run() {
int index = 0;
while (true) {
//指针轮询，如果到达尾部，下一步重新转向开头
// 数据物理结构是一个数组，逻辑上是一个环
if (index == integers.length) {
index = 0;
}
//如果当前位置没有任务，轮询到下一个插槽
if (integers[index] == null) {
index ;
continue;
} else {
//随机等待，表示模拟当前任务有一个执行时间
try {
Thread.currentThread().sleep(new Random().nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
//模拟任务执行的内容，也就是打印一下当前插槽和里面的值
System.out.println(String.format("executeindex = % s, value = % s ",index,integers[index]));
//执行完，将当前插槽清空，腾出位置来给后续任务使用
integers[index] = null;
}
}
}
}).start();
}
public static void main(String[] args) {
//测试开始，定义3个插槽
RR rr = new RR(3);
//唤起执行者线程，开始轮询
rr.execute();
//放置10个任务
for (int i = 0; i < 10; i ) {
rr.addTask(i);
}
}
}- 结果分析
- 优缺点
做到了机会的相对平均，不会因为某个任务执行时间超长而永远得不到执行
缺乏任务主次的处理。重要的任务无法得到优先执行，必须等到时间片轮到自己，着急也没用3.4 优先级调度（HPF）
- 概述 进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式 最高优先级算法和不可抢占式最高优先级算法。
- 实现 在Task类中新增一个属性level作为优先级标识
public class Task {
//任务名称
private String name;
//任务提交的时间
private Long addTime;
//任务的执行时间长短
private int servTime;
public Task(String name, int servTime) {
this.name = name;
this.servTime = servTime;
this.addTime = System.currentTimeMillis();
}
public void execute() {
try {
// ！重点：执行时睡眠，表示该任务耗时servTime毫秒
Thread.currentThread().sleep(servTime);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(String.format("execute:name=%s,addTime=%s,servTime=%s", name,
addTime, servTime));
}
}依然使用TreeMap实现排序，注意的是，key要取优先级
代码语言：javascript复制public class HPF {
public static void main(String[] args) throws InterruptedException {
//有序Map，将服务优先级作为key排序
final TreeMap<Integer, Task> treeMap = new TreeMap();
//向队列中放入5个任务
for (int i = 0; i < 5; i ) {
System.out.println("add task:" i);
int servTime = new Random().nextInt(1000);
//注意放入的key，是优先级，这里用i标识
treeMap.put(i, new Task("task" i, servTime, i));
}
//服务线程，任务由该线程获取和执行
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
try {
//有序Map中，优先级最高的，在底部部，那么自然就会优先被取出
Map.Entry<Integer, Task> entry = treeMap.pollLastEntry();
if (entry == null) {
Thread.currentThread().sleep(100);
} else {
entry.getValue().execute();
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
}).start();
}
}- 结果分析
3.4 应用案例
代码语言：javascript复制CPU资源调度
云计算资源调度
容器化Docker编排与调度
