題目24. LFU Cache
LFU是一個著名的緩存算法
對于容量為k的緩存，如果緩存已滿，并且需要逐出其中的密鑰，則最少使用的密鑰將被踢出。
實現(xiàn)LFU中的set 和 get操作
題目的內(nèi)容比較直觀就是設(shè)計一個LFU緩存淘汰算法的實現(xiàn)，下面我們先來看下LFU的基本流程
LFU
LFU算法中會記錄一定時間內(nèi)每個Key的被訪問次數(shù)，淘汰時會淘汰最近一段時間內(nèi)被訪問次數(shù)最少的key,當多個keys計數(shù)值為最小值時，按照LRU進行淘汰,如下圖所示：
其他常見緩存淘汰策略
FIFO
FIFO是最簡單的先進先出，使用Queue即可實現(xiàn)。
LRU
LRU是根據(jù)最近最少使用原則進行緩存淘汰的算法。顧名思義當需要進行頁置換或者緩存淘汰時將最近最少命中的頁或緩存剔除的算法，如下圖：
解題思路
HashMap + 小根堆
時間復雜度 get : O(1) set O(logk)
為了查詢速度將緩存已key-value的形式保存在hashMap中，同時使用數(shù)組實現(xiàn)的小根堆來記錄數(shù)據(jù)的訪問頻次情況，以便于淘汰策略進行淘汰操作。
java中優(yōu)先級隊列PriorityQueue解析
PriorityQueue是一個無界的按照給定的比較方式進行小根堆排序的隊列實現(xiàn)。
從類圖上我們可以看到，PriorityQueue的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)是Object[]，而通過comparator屬性提供個性化的排序要求。由于上文中提到過PriorityQueue中是通過比較實現(xiàn)的小根堆。
之后會把PriorityQueue簡稱為PQ
1. 構(gòu)造方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
PQ類提供了上面代碼中的構(gòu)造函數(shù)，從構(gòu)造方法中，可以發(fā)現(xiàn)PQ中有兩個比較重要的capacity和comparator屬性（上文中已經(jīng)提到過作用了）。capactity用來表示隊列的容量，可以上面的代碼中看到PQ的默認隊列容量為DEFAULT_INITIAL_CAPACITY(11)，同時還提供了動態(tài)擴容的實現(xiàn)；對于通過已有其他Collection的實現(xiàn)類構(gòu)造PQ隊列時，基本可以分為兩個步驟進行處理,首先將數(shù)據(jù)賦值給PQ的Object[]數(shù)組中，然后通過heapify方法對PQ Object[]數(shù)組的每個元素記性siftDown操作，來達到數(shù)據(jù)按照我們的約定的方式構(gòu)建成相應(yīng)的小根堆。
下面我們就來看看siftDown方法是怎么對已有數(shù)據(jù)進行堆排序的數(shù)據(jù)調(diào)整的,話不多說，代碼先行。
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
siftDown方法接收兩個參數(shù)，i為開始比較的位置，x為比較元素。上面沒有把siftDownUsingComparator方法代碼放上去，是因為兩者的邏輯不同處僅在于比較上的不同，整體邏輯是一樣的。由于PQ中的優(yōu)先級排序方式采用的是小根堆的排序方式，可以看到siftDownUsingComparator主要操作是隊列中的當前節(jié)點與其葉子節(jié)點的比較和交換操作?？傮w來說siftDown方法是對已有隊列進行在排序的操作，在removeAt和poll被調(diào)用。
2. 插入元素
Queue提供了add方法進行隊列的入隊操作，下面看看PQ中add的實現(xiàn)
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
代碼中可以看到，執(zhí)行add操作流程可以看到，PQ中不接受null值。在入隊前會先對隊列容量進行判定，如果容量不足，將會觸發(fā)擴容(grow方法)。擴容的代碼這里就不放出來了。從插入第二個元素開始就會調(diào)用siftUp方法,來進行元素的堆排序操作（如下代碼）。
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
擴容的操作中，當隊列當前容量小于64時，擴容為容量的兩倍，大于64時，擴容為當前容量的1.5倍，當容量超過
MAX_ARRAY_SIZE的時候，會觸發(fā)hugeCapacity進行擴容，如果需要的容量超過MAX_INTEGER會拋出oom異常，當所需容量大于MAX_ARRAY_SIZE時擴容為MAX_INTEGER。
PQ的總結(jié)
總的來說PQ是一個基于小根堆排序方式實現(xiàn)的優(yōu)先級隊列， 隊列中的第一個元素為當前排序方式中最小的元素，遍歷結(jié)果并不是完全有序的（堆排序特點）。PQ中操作的時間復雜度offer,add,poll,remove為o(logn);remove(item),contain操作為 o(n),peek,獲取某個元素,size為o(1)。根據(jù)以上特點我們可以在按照優(yōu)先級對任務(wù)進行分類執(zhí)行時，使用PQ來進行任務(wù)的接收；當然LFU也可以使用PQ來實現(xiàn)。
