¿Cómo guardo una lista de solo los últimos n objetos?

Question

Quiero medir el rendimiento de un método en particular, pero me gustaría promediar el tiempo que lleva completarlo. (Esta es una aplicación C# Winforms, pero esta pregunta podría aplicarse a otros frameworks.)

Tengo un cronómetro que reinicio al inicio del método y me detengo al final. Me gustaría almacenar los últimos 10 valores en una lista o matriz. Cada nuevo valor agregado debe sacar el valor más antiguo de la lista.

Periódicamente llamaré a otro método que promediará todos los valores almacenados.

¿Estoy en lo cierto al pensar que esta construcción es una memoria intermedia circular?

¿Cómo puedo crear un buffer de este tipo con un rendimiento óptimo? En este momento tengo lo siguiente:

List<long> PerfTimes = new List<long>(10); 

// ... 

private void DoStuff() 
{ 
    MyStopWatch.Restart(); 
    // ... 
    MyStopWatch.Stop(); 
    PerfTimes.Add(MyStopWatch.ElapsedMilliseconds); 
    if (PerfTimes.Count > 10) PerfTimes.RemoveAt(0); 
} 

Esto parece ineficiente de alguna manera, pero tal vez no lo es.

Sugerencias?

Answer 1

Se puede crear una colección personalizada:

class SlidingBuffer<T> : IEnumerable<T> 
{ 
    private readonly Queue<T> _queue; 
    private readonly int _maxCount; 

    public SlidingBuffer(int maxCount) 
    { 
     _maxCount = maxCount; 
     _queue = new Queue<T>(maxCount); 
    } 

    public void Add(T item) 
    { 
     if (_queue.Count == _maxCount) 
      _queue.Dequeue(); 
     _queue.Enqueue(item); 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return _queue.GetEnumerator(); 
    } 

    IEnumerator IEnumerable.GetEnumerator() 
    { 
     return GetEnumerator(); 
    } 
} 

Su solución actual funciona, pero es ineficiente, porque quitando el primer elemento de un List<T> es caro.

Answer 2

Me parece bien. ¿Qué pasa con el uso de una LinkedList en su lugar? Al usar una Lista, si quita el primer elemento, todos los demás artículos tienen que retroceder un elemento. Con LinkedList, puede agregar o eliminar elementos en cualquier lugar de la lista a muy bajo costo. Sin embargo, no sé cuánta diferencia haría, ya que solo estamos hablando de diez elementos.

El compromiso de una lista vinculada es que no se puede acceder de manera eficiente a los elementos aleatorios de la lista, porque la lista vinculada debe esencialmente "caminar" a lo largo de la lista, pasando cada elemento, hasta que llegue al que necesitar. Pero para el acceso secuencial, las listas vinculadas están bien.

Answer 3

Para un rendimiento óptimo, probablemente solo pueda utilizar una serie de largos en lugar de una lista.

Tuvimos un requisito similar en un punto para implementar un estimador de tiempo de descarga, y utilizamos un buffer circular para almacenar la velocidad sobre cada uno de los últimos N segundos.

No nos interesaba la velocidad de la descarga durante todo el tiempo, aproximadamente el tiempo que se esperaba según la actividad reciente, pero no por lo que reciente las cifras estarían saltando por todas partes (como si hubiéramos usado el último segundo para calcularlo).

La razón por la que no estábamos interesados ​​en el intervalo de tiempo completo fue que una descarga podría ser de 1M/s durante media hora y luego cambiar a 10M/s durante los siguientes diez minutos. Esa primera media hora arrastrará la velocidad promedio bastante severamente, a pesar de que ahora está descargando bastante rápido.

Creamos un búfer circular con cada celda conteniendo la cantidad descargada en un período de 1 segundo. El tamaño del búfer circular era 300, lo que permite 5 minutos de datos históricos, y cada celda se inicializó a cero. En su caso, solo necesitaría diez celdas.

También mantuvimos un total (la suma de todas las entradas en el búfer, así que también inicialmente cero) y el recuento (inicialmente cero, obviamente).

Cada segundo, queremos averiguar cómo se habían descargado la cantidad de datos desde el último segundo y luego:

• restar la celda actual del total.
• ponga la cifra actual en esa celda y avance el puntero de la celda.
• suma esa cifra actual al total.
• aumentar el recuento si no era ya 300.
• actualizar la figura que se muestra al usuario, en función del total/recuento.

Básicamente, en pseudo-código:

def init (sz): 
    buffer = new int[sz] 
    for i = 0 to sz - 1: 
     buffer[i] = 0 
    total = 0 
    count = 0 
    index = 0 
    maxsz = sz 

def update (kbps): 
    total = total - buffer[index] + kbps # Adjust sum based on deleted/inserted values. 
    buffer[index] = kbps     # Insert new value. 
    index = (index + 1) % maxsz   # Update pointer. 
    if count < maxsz:      # Update count. 
     count = count + 1 
    return total/count     # Return average. 

Eso debería ser fácilmente adaptable a sus propios requisitos. La suma es una buena característica para "caché" de información que puede hacer que su código sea aún más rápido. Con eso quiero decir: si necesita calcular la suma o el promedio, puede resolverlo solo cuando los datos cambien y utilizando los cálculos mínimos necesarios.

La alternativa sería una función que sumara los diez números cuando se solicite, algo que sería más lento que el simple restar o agregar al cargar otro valor en el búfer.

Answer 4

Es posible que desee utilizar la estructura de datos de cola en su lugar. Podría usar una lista lineal simple, pero es completamente ineficiente. Se podría usar una matriz circular, pero luego debes redimensionarla constantemente. Por lo tanto, te sugiero que vayas con la cola.

Answer 5

private int ct = 0; 
private long[] times = new long[10]; 

void DoStuff() 
{ 
    ... 
    times[ct] = MyStopWatch.ElapsedMilliseconds; 
    ct = (ct + 1) % times.Length; // Wrap back around to 0 when we reach the end. 
} 

Aquí hay una estructura circular simple. Esto no requiere ninguna copia de matriz o recolección de basura de nodos de lista vinculados que tengan las otras soluciones.

Answer 6

Necesitaba mantener 5 últimos puntajes en una matriz y se me ocurrió esta sencilla solución. Espero que ayude a alguien.

void UpdateScoreRecords(int _latestScore){ 
     latestScore = _latestScore; 
     for (int cnt = 0; cnt < scoreRecords.Length; cnt++) { 
      if (cnt == scoreRecords.Length - 1) { 
       scoreRecords [cnt] = latestScore; 
      } else { 
       scoreRecords [cnt] = scoreRecords [cnt+1]; 
      } 
     } 
    }