Cálculo de percentiles sobre la marcha

Question

Estoy programando en Java. Cada 100 ms, mi programa obtiene un nuevo número.

Tiene un caché que contiene el historial de los últimos números n = 180. Cuando obtengo un número nuevo x quiero calcular cuántos números hay en la memoria caché que son menores que x. A continuación, deseo eliminar el número más antiguo de la caché.

Cada 100 ms Quiero repetir el proceso de cálculo de cuántos números más pequeños hay y eliminar el número más antiguo.

¿Qué algoritmo debo usar? Me gustaría optimizar para hacer el cálculo rápido, ya que no es lo único que se calculó en esos 100 ms.

Answer 1

Por razones prácticas y los valores razonables de que n mejor de con una memoria intermedia de primitivos int s (para no perder de entrada más antigua) lo son, y una exploración lineal para determinar cuántos valores son más pequeños que x.

Para que esté en O(log n) tendría que usar algo como Guavas TreeMultiset. Aquí hay un resumen de cómo se vería.

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

} 

En mi 1.Computadora portátil de 8 GHz, esta solución realiza 1,000,000 de iteraciones en aproximadamente 13 segundos (es decir, una iteración demora aproximadamente 0,013 ms, muy por debajo de 100 ms).

Answer 2

Agregue sus números a una lista. Si el tamaño es> 180, elimine el primer número. El recuento es solo iterar sobre los 180 elementos, que probablemente sea lo suficientemente rápido. Es difícil superar el rendimiento sabio.

Answer 3

Deje que la memoria caché sea una lista, para que pueda insertarla al principio y dejar que la más antigua esté al final y ser eliminada.

Luego, después de cada inserción, escanee toda la lista y calcule el número que necesita.

Answer 4

Puede utilizar una implementación LinkedList.

Con esta estructura, puede manipular fácilmente el primer y el último elemento de la lista. (addFirst, removeFirst, ...) Para el algoritmo (determine cuántos números son más bajos/más grandes), un bucle simple en la lista es suficiente y le dará el resultado en menos de 100ms en una lista de elementos de 180.

Answer 5

Usted puede mantener un conjunto de 180 números y guardar un índice para el más antiguo de modo que cuando un nuevo número viene en que sobrescribir el número en el índice más antiguo e incrementar el módulo de índice 180 (que es un poco más complejo que eso ya que necesitas un comportamiento especial para los primeros 180 números).

En cuanto al cálculo de cuántos números son más pequeños, usaría la fuerza bruta (iterar todos los números y contar).

---

Editar: me hace gracia ver que el "optimized" version corre cinco veces más lento que esta implementación trivial (gracias a @Eiko para el análisis). Creo que esto se debe al hecho de que cuando utiliza árboles y mapas, pierde la ubicación de los datos y tiene muchas más fallas de memoria (sin mencionar la asignación de memoria y la recolección de basura).

Answer 6

Puede probar una estructura de datos de listas vinculadas personalizada donde cada nodo mantiene las referencias next/prev así como las referencias next/prev ordenadas. Luego la inserción se convierte en un proceso de dos fases, primero siempre inserte el nodo en la cola, y el ordenamiento de inserción, y la clasificación de inserción devolverá el recuento de números menores que x. Eliminar es simplemente quitar la cabeza.

Aquí hay un ejemplo, NOTA: ESTO ES MUY DIFÍCIL JAVA, ES CÓDIGO EJEMPLO PARA DEMOSTRAR A PURO LA IDEA. ¡Entiendes la idea! ;) Además, solo estoy agregando algunos elementos, pero debería darle una idea de cómo funcionaría ... El peor caso para esto es una iteración completa a través de la lista de enlaces ordenados, que no es peor que los ejemplos arriba supongo?

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

Tome un vistazo a la aplicación de la commons-mathDescriptiveStatistics class (Percentile.java)

Answer 8

180 valores no es muchos y una matriz simple que una búsqueda de fuerza bruta y System.arraycopy() debe ser más rápido que 1 micro -segundo (1/1000 milli-segundo) y no genera GC. Podría ser más rápido jugar con colecciones más complejas.

Le sugiero que lo mantenga simple y mida cuánto tiempo toma antes de asumir que necesita optimizarlo.