Как мне сохранить список только последних n объектов?

Question

Я хочу сделать некоторые измерения производительности конкретного метода, но я бы хотел усреднить время, необходимое для завершения. (Это приложение C # Winforms, но этот вопрос вполне может относиться к другим фреймворкам.)

У меня есть секундомер, который я сбрасываю в начале метода и останавливаю в конце. Я хотел бы сохранить последние 10 значений в списке или массиве. Каждое новое добавленное значение должно выталкивать самое старое значение из списка.

Периодически я буду вызывать другой метод, который будет усреднять все сохраненные значения.

Правильно ли я считаю, что эта конструкция представляет собой кольцевой буфер?

Как я могу создать такой буфер с оптимальной производительностью? Прямо сейчас у меня есть следующее:

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

Это кажется каким-то неэффективным, но, возможно, это не так.

Предложения

Answer 1

Вы можете создать собственную коллекцию:

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

Ваше текущее решение работает, но оно неэффективно, потому что удаление первого элемента из List<T> стоит дорого.

Answer 2

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

Вот простая круговая структура.Для этого не требуется ни копирование массива, ни сборка мусора узлов связанного списка, которые есть в других решениях.

Answer 3

Для оптимальной производительности вы, вероятно, можете просто использовать массив long, а не список.

В какой-то момент у нас было аналогичное требование для реализации оценщика времени загрузки, и мы использовали кольцевой буфер для храненияскорость в течение каждой из последних N секунд.

Нас не интересовало, как быстро выполнялась загрузка в течение всего времени, лишь приблизительно, сколько времени она ожидала, основываясь на недавней активности, но не так недавно, что цифры будут прыгать повсюду (например, если бы мы просто использовали последнюю секунду, чтобы вычислить его).

Причина, по которой нас не интересовали все временные рамкиБыло то, что загрузка могла составлять 1 М / с в течение получаса, а затем переключаться на 10 М / с в течение следующих десяти минут.Эти первые полчаса довольно сильно замедляют среднюю скорость, несмотря на то, что вы сейчас загружаете довольно быстро.

Мы создали кольцевой буфер, в каждой ячейке которого содержится количество загруженного за 1-секундный период.Размер циклического буфера составлял 300, что позволяло хранить 5 минут исторических данных, и каждая ячейка была инициализирована нулем.В вашем случае вам потребовалось бы всего десять ячеек.

Мы также поддерживали итоговую сумму (сумму всех записей в буфере, поэтому также изначально равную нулю) и счетчик (изначально равный нулю, очевидно).

Каждую секунду мы выясняем, сколько данных было загружено с последней секунды, а затем:

• вычитаем текущую ячейку из общей суммы.
• помещаем текущую цифрув эту ячейку и продвиньте указатель ячейки.
• добавьте эту текущую цифру к итогу.
• увеличьте счет, если его еще не было 300.
• обновите отображаемую фигурупользователю, исходя из общего количества / количества.

В основном в псевдокоде:

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.

Это должно быть легко адаптировано к вашим собственным требованиям.Эта сумма - хорошая функция для «кеширования» информации, которая может сделать ваш код еще быстрее.Под этим я подразумеваю: если вам нужно вычислить сумму или среднее значение, вы можете вычислить это только при изменении данных, используя минимальные необходимые вычисления.

Альтернативой может быть функция, которая суммирует вседесять чисел по запросу, что будет медленнее, чем одно вычитание / сложение при загрузке другого значения в буфер.

Answer 4

Вместо этого вы можете захотеть использовать структуру данных Queue.Вы можете использовать простой линейный список, но он совершенно неэффективен.Можно использовать круговой массив, но тогда вы должны постоянно изменять его размер.Поэтому я предлагаю вам пройти с очередью.

Answer 5

Для Java это может быть так

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class SlidingBuffer<T> implements Iterable<T>{
    private Queue<T> _queue;
    private int _maxCount;

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

    public void Add(T item) {
        if (_queue.size() == _maxCount)
            _queue.remove();
        _queue.add(item);
    }

    public Queue<T> getQueue() {
        return _queue;
    }

    public Iterator<T> iterator() {
        return  _queue.iterator();
    }
}

Это может быть начато таким образом

public class ListT {

    public static void main(String[] args) {
        start();
    }

    private static void start() {
        SlidingBuffer<String> sb = new SlidingBuffer<>(5);
        sb.Add("Array1");
        sb.Add("Array2");
        sb.Add("Array3");
        sb.Add("Array4");
        sb.Add("Array5");
        sb.Add("Array6");
        sb.Add("Array7");
        sb.Add("Array8");
        sb.Add("Array9");

        //Test printout
        for (String s: sb) {
            System.out.println(s);
        }
    }
}

Результат

Array5

Array6

Array7

Array8

Array9

Answer 6

Мне нужно было сохранить 5 последних результатов в массиве, и я нашел это простое решение. Надеюсь, это кому-нибудь поможет.

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

Answer 7

Кажется, хорошо для меня.Как насчет использования LinkedList вместо этого?При использовании списка, если вы удалите первый элемент, все остальные элементы должны быть возвращены на один элемент назад.С помощью LinkedList вы можете добавлять или удалять элементы в любом месте списка с минимальными затратами.Однако я не знаю, насколько это может измениться, поскольку речь идет только о десяти элементах.

Компромисс связанного списка заключается в том, что вы не можете эффективно получить доступ к случайным элементамсписок, потому что связанный список должен по существу «ходить» по списку, пропуская каждый элемент, пока не дойдет до того, который вам нужен.Но для последовательного доступа можно использовать связанные списки.