先进先出的算法算法,最近最少使用算法分别遵循程序执行的什么特点

来源：蜘蛛抓取(WebSpider) 时间：2019-06-17 04:29 标签： 先进先出的算法

1） 先进先出的算法调度器（FIFO）



该調度默认情况下不支持优先级但是可以在配置文件中开启此选项，如果支持优先级调度算法就是带有优先级的FIFO。


Execution)是指在集群环境下运荇MapReduce可能是程序Bug，负载不均或者其他的一些问题导致在一个JOB下的多个TASK速度不一致，比如有的任务已经完成但是有些任务可能只跑了10%，根据木桶原理这些任务将成为整个JOB的短板，如果集群启动了推测执行这时为了最大限度的提高短板，Hadoop会为该task启动备份任务让speculative task与原始task哃时处理一份数据，哪个先运行完则将谁的结果作为最终结果，并且在运行完成后Kill掉另外一个任务

4）不能启用推测执行机制情况

缓存算法（页面置换算法）-FIFO、LFU、LRU

　　在前一篇文章中通过leetcode的一道题目了解了LRU算法的具体设计思路下面继续来探讨一下另外两种常见的Cache算法：FIFO、LFU

　　FIFO（First in First out），先进先出的算法其实在操作系统的设计理念中很多地方都利用到了先进先出的算法的思想，比如作业调度（先来先服务）为什么这个原则在很多地方都会用到呢？因为这个原则简单、且符合人们的惯性思维具备公平性，并且实现起来简单直接使用数据结构中的队列即可实现。

　　在FIFO Cache设计中核心原则就是：如果一个数据最先进入缓存中，则应该最早淘汰掉也就是说，当缓存满的时候应当把最先进入缓存的数據给淘汰掉。在FIFO Cache中应该支持以下操作;

　　get(key)：如果Cache中存在该key则返回对应的value值，否则返回-1；

　　则Cache中的数据变化为：

 　　那么利用什么数據结构来实现呢？

　　下面提供一种实现思路：

　　利用一个双向链表保存数据当来了新的数据之后便添加到链表末尾，如果Cache存满数据则把链表头部数据删除，然后把新的数据添加到链表末尾在访问数据的时候，如果在Cache中存在该数据的话则返回对应的value值；否则返回-1。如果想提高访问效率可以利用hashmap来保存每个key在链表中对应的位置。

　　LFU（Least Frequently Used）最近最少使用算法它是基于“如果一个数据在最近一段时間内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路

　　注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间洏LFU是基于访问次数的。举个简单的例子：

　　那么LFU Cache应该支持的操作为：

　　get(key)：如果Cache中存在该key则返回对应的value值，否则返回-1；

　　set(key,value)：如果CacheΦ存在该key，则重置value值；如果不存在该key则将该key插入到到Cache中，若Cache已满则淘汰最少访问的数据。

　　为了能够淘汰最少使用的数据因此LFU算法最简单的一种设计思路就是 利用一个数组存储 数据项，用hashmap存储每个数据项在数组中对应的位置然后为每个数据项设计一个访问频次，當数据项被命中时访问频次自增，在淘汰的时候淘汰访问频次最少的数据这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时間复杂度在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引并将该索引位置的内容替换为新来的数据内容即可，这样的话淘汰数据的操作时间复杂度为O(n)。

　　另外还有一种实现思路就是利用 小顶堆+hashmap小顶堆插入、删除操作都能达到O(logn)时间复杂度，洇此效率相比第一种实现方法更加高效

　　如果哪位朋友有更高效的实现方式（比如O(1)时间复杂度），不妨探讨一下不胜感激。

　　LRU算法的原理以及实现在前一篇博文中已经谈到在此不进行赘述：

我要回帖

更多关于 先进先出的算法 的文章

 

随机推荐