如何移动元素？

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 是要在出队时弹出的下一个元素，1.0 是最近添加的项目。

我想删除最近添加的 5 个项目，以便队列最终看起来像这样（我需要在队列中保持相同数量的元素，这样大小就不会减小）：

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

在 .NET 中完成此操作的最快方法是什么

澄清：

t = 0: 队列已初始化

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

t = 1: 添加一个元素

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

t = 2: 添加一个元素

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

t = 3: 添加一个元素

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

t = 4：最近添加的两个元素是 "dropped"（时间倒带）

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

背景信息：

我正在将示例推送到缓冲区。缓冲区基本上是在一长串样本上滑动 window。有时我想 "rewind" window;那就是：及时将它移回过去，因为我推送的样本应该被丢弃。我不知道样本是否应该提前丢弃。我必须推送样本，对 "window" 中的样本进行一些计算，然后决定 window 是否应该及时 "backed up"。

更新

要求：

实现一个具有固定大小的 N 个元素的缓冲区 X。缓冲区中最早的元素位于索引 0 (X[0]) 处。缓冲区中的最新元素位于索引 N-1 (X[N-1])
实现一个方法 'Write' 将样本 s 写入缓冲区。将样本写入缓冲区时，缓冲区中的样本会移位，因此 X[j] = X[j+1] for j = 0 to j = N-2 and X[N-1] = s.
在任何给定时间，都应提供以下方法：
- 查找缓冲区中的最大样本值
- 查找缓冲区中的最小样本值
- 求缓冲区中样本值的平均值
- 读取缓冲区中任意位置的样本值
"Rewind"：实现一个方法，从索引0开始复制K个元素到索引K-1，并将它们放在缓冲区的末尾。因此，最初位于索引 K-1 的样本将移动到索引 N-1，而最初位于索引 0 的样本将移动到索引 (N-1) - (K-1)。索引 0 到索引 K-1 的样本随后设置为 0.

我希望以上说明了我想要的。谢谢。

Answer 1

因此，鉴于您的新要求，我将实施此 class:

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

这段代码显然只是 shell - 我已将内部工作留给您编码。

我完全按照你的要求结构。

当前编译的代码应该有助于成为一个好的起点。

我建议您首先使用数组作为底层数据结构（即 double[N]）来实现它。如果您实现此代码并且它足够高效，那么您就完成了。如果没有，请尝试使用 LinkedList<double> - 这将更难编码，但它应该更快，尽管没有运行你的代码反对它我无法告诉你。

Answer 2

您似乎需要固定大小 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);
    }
}

Answer 3

我最终使用常规数组并在这些数组上使用复制方法来实现所需的功能

如何移动元素？

How to move elements?

.net

c#

queue