Как перемещать элементы?

Question

Скажем, у вас есть экземпляр очереди в .NET (Systems.Generic.Collections.Queue). В очереди есть 10 элементов, где элемент 9 (считая от 0) является последним добавленным элементом в очереди.

Так что очередь может выглядеть следующим образом:

{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0} 

где 0,1 является следующим элементом, который будет выскочил на DEQUEUE и 1,0 является наиболее недавно добавленным элементом.

Я хотел бы отказаться от наиболее недавно добавленных пунктов 5, так что очередь заканчивает тем, как это (мне нужно поддерживать одинаковое количество элементов в очереди, поэтому размер не уменьшается):

{0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.2, 0.3, 0.4, 0.5} 

Какой самый быстрый способ выполнения, что в .NET

Разъяснение:

т = 0: Очередь инициализируется

{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0} 

т = 1: Один элемент добавляется

{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1} 

т = 2: добавляется один элемент

{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.2} 

т = 3: Один элемент добавляется

{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.2, 0.3} 

т = 4: Два из последних добавленных элементов «отбрасываются» (перематываются во времени)

{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1} 

Справочная информация:

я выдвигаю образцы в буфер. Буфер в основном представляет собой скользящее окно над длинным потоком образцов. Иногда я хочу «перемотать» окно; то есть: переместите его назад во времени, потому что образцы, которые я нажал, должны быть отброшены. Я не знаю, должны ли образцы отбрасываться раньше времени. Я должен нажать образцы, выполнить некоторые вычисления на образцах в «окне», а затем решить, нужно ли во время резервного копирования окна.

ОБНОВЛЕНИЕ

Требования:

1. Реализовать буфера X, который имеет фиксированный размер N элементов. Самый старший элемент в буфере находится в индексе 0 (X [0]). Новейший элемент в буфере находится в индексе N-1 (X [N-1])

2. Внедрите метод «Write», который записывает образец, s, в буфер. Когда образец записывается в буфер, выборки в буфере смещаются так, что , что X [j] = X [j + 1] для j = 0 - j = N-2 и X [N-1] = s.

3. В любой данный момент времени, способ для должны быть доступны следующие:

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

4. «Перемотка назад»: реализовать метод, который копирует элементы K, начиная с индекса 0, до индекса K-1 и помещает их в конец буфера. Таким образом, образец, который первоначально был включен в индекс K-1, был перенесен на индекс N-1, а образец, который первоначально был в индексе 0, был перенесен в индекс (N-1) - (K-1). Затем образцы с индексом 0 до индекса K-1 устанавливаются равными 0.

Надеюсь, что вышеизложенное разъясняет, что я хочу. Благодарю.

Answer 1

Я закончил с использованием регулярных массивов и копировать методы этих массивов для реализации требуемой функциональности

Answer 2

Таким образом, учитывая ваши новые требования, я бы реализовать этот класс:

public class Buffer 
{ 
    public Buffer(int N) { } 
    public void Write(double value) { } 
    public double Maximum { get { return 0.0; } } 
    public double Minimum { get { return 0.0; } } 
    public double Average { get { return 0.0; } } 
    public double this[int n] { get { return 0.0; } } 
    public void Rewind(int k) { } 
} 

Этот код явно только оболочка - Я оставил внутреннюю работу для вас код.

Я точно следовал структуре ваших требований.

Код в настоящее время компилируется, что должно помочь сделать его хорошей отправной точкой.

Я предлагаю вам реализовать это сначала, используя массив в качестве вашей базовой структуры данных (то есть double[N]). Если вы реализуете этот код, и он достаточно эффективен, вы закончите. Если нет, попробуйте использовать LinkedList<double> - этого будет сложнее закодировать, но он должен быть быстрее, хотя без запуска вашего кода против него нет никакого способа рассказать.

Answer 3

Кажется, вам нужно что-то вроде фиксированного размера ring buffer, хотя ожидаемое поведение для операции Rewind остается несколько неясным. Поэтому, если я неправильно понял, как это должно работать, прошу прояснить это дальше в вашем вопросе.

public class RewindableRingBuffer<T> 
{ 
    private readonly T[] _values; 
    private int _head; // index of oldest value 
    private int _count; // number of elements 

    public RewindableRingBuffer(int capacity) 
    { 
     _values = new T[capacity]; 
     _head = 0; 
     _count = 0; 
    } 

    public int Count { get { return _count; } } 

    public T this[int index] 
    { 
     get 
     { 
      if ((uint)index >= (uint)_count) 
       throw new IndexOutOfRangeException("index"); 
      return _values[(_head + index) % _values.Length]; 
     } 
    } 

    public void Add(T value) 
    { 
     var tail = (_head + _count) % _values.Length; 
     if (_count < _values.Length) 
      _count++; // was not yet filled to capacity. 
     else 
      _head = (_head + 1) % _values.Length; // remove oldest. 
     _values[tail] = value; 
    } 

    public T Min 
    { 
     get { return Enumerate().Min(); } 
    } 

    public T Max 
    { 
     get { return Enumerate().Max(); } 
    } 

    public IEnumerable<T> Enumerate() 
    { 
     // enumerates oldest to newest. 
     for (var i = 0; i < _count; i++) 
      yield return _values[(_head + i) % _values.Length]; 
    } 

    public void RewindBy(int num) 
    { 
     // Goes back in history, by removing the 'num' 
     // most recent values. 
     _count = Math.Max(0, _count - num); 
    } 
}