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

Ответ 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> является дорогостоящим.

Ответ 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.
}

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

Ответ 3

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

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

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

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

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

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

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

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

В принципе, в псевдокоде:

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.

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 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];
            }
        }
    }

Ответ 7

Для 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