即時計算百分位數

Question

我使用Java編程。每隔100毫秒，我的程序就會獲得一個新號碼。

它有一個包含最後n = 180號碼的歷史記錄的緩存。 當我得到一個新號碼x我想計算緩存中有多少個號碼小於x。 之後我想刪除緩存中最早的號碼。

每隔100毫秒我想重複計算有多少個較小數字的過程，並刪除最早的數字。

我應該使用哪種算法？我想優化計算速度，因爲它不是計算這100毫秒的唯一值。

Answer 1

出於實際考慮和n合理值你與原始int S（跟蹤最老的條目的）的環形緩衝區最好的，以及確定多少值的線性掃描較小比x。

爲了這是在O(log n)你必須使用類似Guavas TreeMultiset。這是它看起來如何的輪廓。

class Statistics { 

    private final static int N = 180; 
    Queue<Integer> queue = new LinkedList<Integer>(); 
    SortedMap<Integer, Integer> counts = new TreeMap<Integer, Integer>(); 

    public int insertAndGetSmallerCount(int x) { 

     queue.add(x);        // O(1) 
     counts.put(x, getCount(x) + 1);    // O(log N) 

     int lessCount = 0;       // O(N), unfortunately 
     for (int i : counts.headMap(x).values())  // use Guavas TreeMultiset 
      lessCount += i;       // for O(log n) 

     if (queue.size() > N) {      // O(1) 
      int oldest = queue.remove();    // O(1) 
      int newCount = getCount(oldest) - 1;  // O(log N) 
      if (newCount == 0) 
       counts.remove(oldest);    // O(log N) 
      else 
       counts.put(oldest, newCount);  // O(log N) 
     } 

     return lessCount; 
    } 

    private int getCount(int x) { 
     return counts.containsKey(x) ? counts.get(x) : 0; 
    } 

} 

在我1。8 GHz筆記本電腦，該解決方案在約13秒內執行1,000,000次迭代（即一次迭代大約需要0.013 ms，遠低於100 ms）。

Answer 2

將您的號碼添加到列表中。如果大小> 180，請刪除第一個數字。計數只是迭代180個可能足夠快的元素。明智的表現難以超越。

Answer 3

讓緩存成爲一個列表，這樣你就可以在開始時插入並讓最早的最後一個被刪除。

然後每次插入後，只需掃描整個列表並計算出您需要的數字。

Answer 4

您可以使用LinkedList實現。

使用此結構，您可以輕鬆操縱列表的第一個和最後一個元素。 （addFirst，removeFirst，...） 對於算法（查找有多少個數字更低/更大），列表上的簡單循環就足夠了，並且會在180個元素列表中給出結果少於100ms。

Answer 5

你可以保持180號的數組和索引，這樣，當一個新的數字來在你的最古老指數覆蓋的數量和遞增指數模180（這是一個更復雜一點保存最古老的一個因爲你需要對前180個號碼進行特殊處理）。

至於計算有多少數字更小，我會使用蠻力的方式（迭代所有的數字和計數）。

---

編輯：我覺得很有趣地看到，"optimized" version運行速度比這個簡單的實現慢五倍（感謝@Eiko的分析）。我認爲這是因爲當你使用樹和地圖時，你失去了數據的局部性，並且有更多的內存錯誤（更不用說內存分配和垃圾收集了）。

Answer 6

您可以嘗試一個自定義鏈接列表數據結構，其中每個節點維護next/prev以及排序的next/prev引用。然後插入成爲一個兩階段過程，首先總是在尾部插入節點，然後插入排序，插入排序將返回小於x的數字的計數。刪除只是刪除頭部。

這裏是一個例子，注意：這是非常有趣 JAVA，它是一個示例代碼，可以完美演示創意。你明白了！ ;）另外，我只添加了一些項目，但它應該讓你知道它是如何工作的......最糟糕的情況是通過排序後的鏈表進行完整迭代 - 這並不比示例更差以上我猜？

import java.util.*; 

class SortedLinkedList { 

    public static class SortedLL<T> 
    { 
    public class SortedNode<T> 
    { 
     public SortedNode(T value) 
     { 
     _value = value; 
     } 

     T _value; 

     SortedNode<T> prev; 
     SortedNode<T> next; 

     SortedNode<T> sortedPrev; 
     SortedNode<T> sortedNext; 
    } 

    public SortedLL(Comparator comp) 
    { 
     _comp = comp; 
     _head = new SortedNode<T>(null); 
     _tail = new SortedNode<T>(null); 
     // Setup the pointers 
     _head.next = _tail; 
     _tail.prev = _head; 
     _head.sortedNext = _tail; 
     _tail.sortedPrev = _head; 
     _sortedHead = _head; 
     _sortedTail = _tail;  
    } 

    int insert(T value) 
    { 
     SortedNode<T> nn = new SortedNode<T>(value); 

     // always add node at end 
     nn.prev = _tail.prev; 
     nn.prev.next = nn; 
     nn.next = _tail; 
     _tail.prev = nn; 

     // now second insert sort through.. 
     int count = 0; 
     SortedNode<T> ptr = _sortedHead.sortedNext; 
     while(ptr.sortedNext != null) 
     { 
     if (_comp.compare(ptr._value, nn._value) >= 0) 
     { 
      break; 
     } 
     ++count; 
     ptr = ptr.sortedNext; 
     } 

     // update the sorted pointers.. 
     nn.sortedNext = ptr; 
     nn.sortedPrev = ptr.sortedPrev; 
     if (nn.sortedPrev != null) 
     nn.sortedPrev.sortedNext = nn; 
     ptr.sortedPrev = nn; 

     return count;    
    } 

    void trim() 
    { 
     // Remove from the head... 
     if (_head.next != _tail) 
     { 
     // trim. 
     SortedNode<T> tmp = _head.next; 
     _head.next = tmp.next; 
     _head.next.prev = _head; 

     // Now updated the sorted list 
     if (tmp.sortedPrev != null) 
     { 
      tmp.sortedPrev.sortedNext = tmp.sortedNext; 
     } 
     if (tmp.sortedNext != null) 
     { 
      tmp.sortedNext.sortedPrev = tmp.sortedPrev; 
     } 
     } 
    } 

    void printList() 
    { 
     SortedNode<T> ptr = _head.next; 
     while (ptr != _tail) 
     { 
     System.out.println("node: v: " + ptr._value); 
     ptr = ptr.next; 
     }  
    } 

    void printSorted() 
    { 
     SortedNode<T> ptr = _sortedHead.sortedNext; 
     while (ptr != _sortedTail) 
     { 
     System.out.println("sorted: v: " + ptr._value); 
     ptr = ptr.sortedNext; 
     }  
    } 

    Comparator _comp; 

    SortedNode<T> _head; 
    SortedNode<T> _tail;  

    SortedNode<T> _sortedHead; 
    SortedNode<T> _sortedTail;  

    } 

    public static class IntComparator implements Comparator 
    { 
    public int compare(Object v1, Object v2){ 
     Integer iv1 = (Integer)v1; 
     Integer iv2 = (Integer)v2; 
     return iv1.compareTo(iv2); 
    } 
    } 


    public static void main(String[] args){ 

    SortedLL<Integer> ll = new SortedLL<Integer>(new IntComparator()); 
    System.out.println("inserting: " + ll.insert(1)); 
    System.out.println("inserting: " + ll.insert(3)); 
    System.out.println("inserting: " + ll.insert(2)); 
    System.out.println("inserting: " + ll.insert(5)); 
    System.out.println("inserting: " + ll.insert(4)); 
    ll.printList(); 
    ll.printSorted();  

    System.out.println("inserting new value"); 
    System.out.println("inserting: " + ll.insert(3)); 
    ll.trim(); 
    ll.printList(); 
    ll.printSorted();  
    } 
} 

Answer 7

看一看的commons-math實施DescriptiveStatistics class（Percentile.java）的

Answer 8

180值不是許多和一個簡單的陣列，其蠻力搜索和System.arraycopy（）應該是快於1個微秒（1/1000毫秒）並且不產生GC。玩更復雜的收藏品可能會更快。

我建議你保持簡單，並在假設你需要優化之前測量ti需要多長時間。