滑動視窗分位數
滑動視窗分位數
分位數計算公式
分位數的計算公式有PERCETILE.INC和PERCENTILE.EXC兩種，兩個公式的計算邏輯是完全一樣的，僅僅取數的範圍大小不一樣，這裡我們使用PERTILE.INC來完成分位數的計算，具體的分位數計算邏輯不是本文的重點，這裡就不贅述了。
分位數的題目要求
給你一個陣列 List<Element> elements，有一個長度為 windowSize 的視窗從最左端滑動到最右端。視窗中有 windowSize 個數，每次視窗向右移動 1 位。你的任務是找出每次視窗移動後得到的新視窗中元素的分位數。
由於在具體的業務中，每一條資料除了數值以外，還有其他的業務屬性，所以我在此頂一個了一個計算使用的抽象類PercentilePriorityQueueElement，僅有需要計算的值，而Element是自定義的業務元素物件，可以包含具體的業務屬性。
PercentilePriorityQueueElement類如下
public abstract static class PercentilePriorityQueueElement implements Comparable<PercentilePriorityQueueElement> {
private final long id;
private final double value;
protected PercentilePriorityQueueElement(double value) {
this.id = IdWorker.getId();
this.value = value;
}
/**
* 獲取計算值
*
* @return double
*/
public double getValue() {
return this.value;
}
Element類如下
class Element extends PercentileFinder.PercentilePriorityQueueElement {
Element(double v) {
super(v);
}
}
分位數計算思考
我們首先思考一下計算分位數需要做那些事情
-
序：我們都知道，PERCENTILE.INC計算需要兩個引數，一個是需要計算的元素的陣列elements，另一個是百分位數percent，這裡我們用取值範圍為[0,1]的小數來表示。
-
1：初始時，我們需要將陣列elements的前windowSize個元素放入滑動視窗中，然後對所有的這些元素排序
-
2：找出兩個分為點所在的位置，(windowSize−1)∗p=i+j （其中windowSize為陣列元素的個數，也即是視窗大小，將計算結果的整數部分用i表示，小數部分用j來表示，p是百分位數，如90%的話就是0.9）
-
3：找出這些元素的兩個分位點元素smallElement和largeElement，其中smallElement是大於等於所有左邊的元素，largeElement是小於等於所有右邊的元素。
-
4：ans=(1−j)∗elements[i]+j∗elements[i+1] （ans就是我們所需要的百分位數）
-
5: 移除視窗的第一個元素,將一個新的元素放入視窗中,重複上述步驟
用圖表示的話,其中smallElement和largeElement的位置就是如下圖所示的位置
滑動視窗分位數的演演算法設計
考慮到我們是使用滑動視窗計算的分位數，則必然包含一下三個過程
-
1：向滑動視窗中放入資料
-
2：將滑動的首元素移除出視窗
-
3：計算視窗的分位數
根據以上三個過程，我們設計出三個介面，如下：
public void addElement(E element);//將一個元素加入資料結構
private void erase(E element);//將一個元素移除資料結構
public Double getPercentInc();//計算分位數
-
1：根據以上對分位數計算的思考,我們考慮設計一個計算分位數的資料結構,考慮到smallElement元素左邊的元素都小於等於smallElement,而largeElement元素右邊的元素都大於等於largeElement,我們可以使用兩個堆來保證這一要求,其中smallElement元素及其左邊的元素使用一個大頂堆,而largeElement及其右邊的元素使用一個小頂堆,這樣就可以滿足我們的要求。
-
2：堆資料結構的缺點
-
2.1：考慮到堆這一資料結構的設計不支援刪除非堆頂元素，即使Java的PriorityQueue提供了remove()方法來移除非堆頂元素，呼叫removeAt()也能保證堆這一資料結構的要求，但是其remove的時候呼叫的indexOf()方法為線性查詢，其複雜度為O(n)，n為視窗大小，所以相對來說複雜度還是很高的，這就違背了我們這一資料結構的初衷。（如果呼叫PriorityQueue的remove方法不如我們使用氣泡排序中的一次冒泡更加高效，因為移除視窗的第一個元素之後整體還是有序的，所以加入元素的時候最多需要一個遍歷就可以滿足我們的要求，複雜度也是O(n)，n為視窗大小）。
-
2.2：我們再仔細思考一下整個流程，發現如果一個元素在視窗的之外，但是該元素不在堆頂的時候，它並不影響我們的計算，因為我們的計算僅需要兩個堆頂的元素，所以我們可以不立即刪除該元素，等到該元素到達之後，再將該元素移除出堆中。所以我們還需要一個集合來儲存這些元素，我們稱刪除這些元素的設計為延遲刪除。
-
-
3：由於我們在加入元素的時候可能會破壞大頂堆SmallQ和小頂堆LargeQ的數量，所以我們需要在每一次加入元素之後，需要平衡兩個堆中元素的數量以保證兩個堆中的元素的數量始終是我們的需要的數量。
-
4：當我們加入元素的時候，我們需要根據加入元素的大小判斷該元素是要放入大頂堆還是小頂堆中，由於加入元素會破壞堆中元素的數量，所以我們需要線調整元素的位置，因此我們設計一個平衡函數makeBalance()用於調整大頂堆和小頂堆的資料，調整之後，資料多出的堆由於延遲刪除的原因堆頂元素有可能不是視窗之內的元素，所以我們設計一個輔助函數prune(heap)用於刪除不在視窗之內的堆頂元素。由於兩個堆頂的元素交換的原因，所以當兩個元素的值相同的時候，可能會出現我們需要刪除的元素在小頂堆，但是該元素在大頂堆中，於是我們設計一個嘗試交換並刪除待刪除元素的函數trySwapHeapElement(PriorityQueue<E> opsHeap, PriorityQueue<E> willRemoveHeap)以幫助我們解決在調整兩個堆頂元素相同的時候會出現的問題。
完整程式碼
import com.baomidou.mybatisplus.core.toolkit.IdWorker;
import lombok.EqualsAndHashCode;
import javax.annotation.Nullable;
import java.util.*;
import java.util.stream.Collectors;
/**
* <h2>分位數計算</h2>
* <p>formula: PERCENTILE.INC</p>
*
* @author philosophy
*/
public class PercentileFinder<E extends PercentileFinder.PercentilePriorityQueueElement> {
private static final double MAX_PERCENT = 1.00;
private static final double MIN_PERCENT = 0.00;
/**
* 滑動視窗大小
*/
private final int slidingWindowSize;
/**
* 延遲刪除的元素集合
*/
private final Set<E> delayed;
/**
* 待刪除元素的佇列
*/
private final Queue<E> todoRemoveQueue;
/**
* 大於 {分位數} 的優先順序佇列
*/
private final PriorityQueue<E> smallQ;
/**
* 大於 {分位數} 的優先順序佇列
*/
private final PriorityQueue<E> largeQ;
/**
* {smallQ}的最大數量
*/
private final int smallQueueMaxSize;
/**
* {largeQ}的最大數量
*/
private final int largeQueueMaxSize;
/**
* {largeQ}的元素數量
*/
private int largeQueueSize;
/**
* {smallQ}的元素數量
*/
private int smallQueueSize;
/**
* 分為數比例（用小數標識） 取值範圍 [0,1]
*/
private double quantileScale;
/**
* 當資料總數小於視窗大小時，臨時儲存資料
*/
private List<E> tempDataList;
private boolean flag = false;
/**
* 分位數計算
*
* @param windowSize windowSize
* @param percent percent
*/
public PercentileFinder(int windowSize, double percent) {
check(windowSize, percent);
this.slidingWindowSize = windowSize;
//初始化分位點
int index