Calcolo dei percentili al volo

Question

Sto programmando in Java. Ogni 100 ms il mio programma ottiene un nuovo numero.

Ha una cache con la cronologia degli ultimi numeri n = 180. Quando ottengo un nuovo numero x Voglio calcolare quanti numeri ci sono nella cache che sono più piccoli di x. Successivamente voglio cancellare il numero più vecchio nella cache.

Ogni 100 ms Voglio ripetere il processo di calcolo di quanti più piccoli numeri ci sono ed eliminare il numero più vecchio.

Quale algoritmo dovrei usare? Vorrei ottimizzare per rendere il calcolo veloce in quanto non è l'unica cosa che ha calcolato su quei 100 ms.

Answer 1

Per ragioni pratiche e valori ragionevoli di n si sta meglio di un anello-buffer dei primitivi int s (per tenere traccia dei dati più vecchi), e una scansione lineare per determinare quanti valori sono più piccoli di x.

Per poter essere in O(log n), è necessario utilizzare qualcosa come Guavas TreeMultiset. Ecco una descrizione di come sarebbe.

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; 
    } 

} 

Sul mio 1.Computer portatile da 8 GHz, questa soluzione esegue 1.000.000 iterazioni su circa 13 secondi (vale a dire che un'iterazione richiede circa 0,013 ms, ben al di sotto dei 100 ms).

Answer 2

Aggiungi i tuoi numeri a un elenco. Se la dimensione> 180, rimuovere il primo numero. Il conteggio è solo un'iterazione dei 180 elementi che è probabilmente abbastanza veloce. È difficile battere le prestazioni.

Answer 3

Lascia che la cache sia una lista, in modo da poter inserire all'inizio e lasciare che il più vecchio sia alla fine e venga rimosso.

Quindi dopo ogni inserimento è sufficiente scansionare l'intero elenco e calcolare il numero necessario.

Answer 4

È possibile utilizzare un'implementazione di LinkedList.

Con questa struttura, è possibile modificare facilmente il primo e l'ultimo elemento della lista. (addFirst, removeFirst, ...) Per l'algoritmo (trova quanti numeri sono più bassi/maggiori), è sufficiente un semplice ciclo nell'elenco e ti darà il risultato in meno di 100ms su un elenco di elementi di 180.

Answer 5

È possibile mantenere una matrice di 180 numeri e salvare un indice per la più antica in modo che quando un nuovo numero arriva in voi sovrascrivere il numero alla più antica dell'indice e incrementare il modulo indice 180 (è un po 'più complessa di quello in quanto hai bisogno di un comportamento speciale per i primi 180 numeri).

Come per calcolare quanti numeri sono più piccoli userei il modo forza bruta (itera tutti i numeri e conta).

---

Edit: Trovo divertente vedere che la "optimized" version corre cinque volte più lento rispetto a questo banale applicazione (grazie a @Eiko per l'analisi). Penso che questo sia dovuto al fatto che quando si usano alberi e mappe si perde la località dei dati e si verificano molti più errori di memoria (per non parlare dell'assegnazione della memoria e della garbage collection).

Answer 6

Si può provare una struttura di dati dell'elenco collegato personalizzato in cui ogni nodo mantiene next/prev e ordinati next/prev riferimenti. Quindi l'inserimento diventa un processo a due fasi, prima sempre inserire il nodo alla coda e l'ordinamento dell'inserto e l'ordinamento dell'inserto restituirà il conteggio dei numeri inferiore a x. Cancellare è semplicemente rimuovere la testa.

Ecco un esempio, Nota: Questo è molto brutto Java, è il codice di esempio per dimostrare PURAMENTE L'IDEA. Hai capito l'idea! ;) Inoltre, sto solo aggiungendo alcuni elementi, ma dovrebbe darti un'idea di come funzionerebbe ... Il caso peggiore per questo è una completa iterazione attraverso l'elenco collegato ordinato - che non è peggio degli esempi sopra immagino?

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

Date un'occhiata al commons-math attuazione del DescriptiveStatistics class (Percentile.java)

Answer 8

180 valori è non molti e un semplice array, che una ricerca forza bruta e System.arraycopy() dovrebbe essere più veloce di 1 micro -secondo (1/1000 milli-secondi) e non causa GC. Potrebbe essere più veloce giocare con raccolte più complesse.

Suggerisco di mantenerlo semplice e misurare quanto tempo ci vuole prima di assumere che è necessario ottimizzarlo.