2

我需要一个按以下方式工作的 C# 数据结构：

  1. 用静态尺寸定义它
  2. 将新数据添加到列表末尾
  3. 最旧的数据脱落。
  4. 数据元素的随机访问

示例：如果我定义了 5 个元素的结构并添加了以下内容

1,2,3,4,5,6,7,8

数据结构如下所示：

4,5,6,7,8

我不确定哪种结构会以这种方式工作。向量？列表？堆？数据结构支持像数组一样的静态大小，并推送旧数据的推送数据。

堆栈/队列不提供随机访问。列表没有“推送”操作。

也许是一个 LinkedList 并为删除第一个元素的“push”添加自定义操作？LinkList 随机访问虽然是 o(n) 操作。

4

3 回答 3

5

为了获得最大效率，这可能是实现循环缓冲区的自定义类。

只需在实例化时创建一个固定大小的数组来保存数据。此外还有一个起始索引、一个大小成员和一个容量，这样您就可以知道缓冲区中有多少数据以及它从哪里开始。

因此，首先，您的列表不包含数据，起始位置为 0，大小为 0。

当你添加一个项目时，它会进入元素(start + size) % capacity，size如果它还不是 at 则递增capacity。如果它是at capacity，你start也会增加，如果需要的话环绕：start = (start + 1) % capacity。

要从列表中获取索引处的元素n，您实际上可以使用以下命令对其进行调整start：

return element[(start + n) % capacity];

我没有涉及删除列表的开头，因为那不在您的规范中。但是，这是一个简单的检查，以确保size不是 0，然后在 处提取项目，然后使用上面显示的相同环绕element[start]递增。start

在伪代码中（未经测试但应该接近）：

def listNew (capacity):
    me = new object
    me.capacity = capacity
    me.data = new array[capacity]
    me.start = 0
    me.size = 0
    return me

def listAdd (me, item):
    if me.size = me.capacity:
        me.data[me.start] = item
        me.start = (me.start + 1) % me.capacity
    else:
        me.data[(me.start + me.size) % me.capacity] = item
        me.size = me.size + 1

def listGet (me, index):
    if index > size:
        return 0 # or raise error of some sort
    return me.data[(me.start + index) % me.capacity]

def listRemove (me):
    if size == 0:
        return 0 # or raise error of some sort
    item = me.data[(me.start + index) % me.capacity]
    me.start = (me.start + 1) % me.capacity
    me.size = me.size - 1
    return item

根据要求，所有这些操作都是 O(1) 时间复杂度。

对于将数字添加到五元素列表的特定示例1，8您最终会得到：

  0   1   2   3   4 <--- index
+---+---+---+---+---+
| 6 | 7 | 8 | 4 | 5 |
+---+---+---+---+---+
              ^
              +--------- start    = 3
                         size     = 5
                         capacity = 5

这样，从缓冲区中提取虚拟索引 3（第四个数字）将为您提供一个实际索引：

  (start + 3) % capacity
= (  3   + 3) %    5
=       6     %    5
=             1
于 2013-08-12T02:45:39.383 回答
2

它是一个最大长度队列（因此​​，一旦一个元素达到最大长度，您必须先出列并丢弃一个元素，然后再将另一个元素排入队列）。您可以在 C# 队列上进行随机访问，但它是 O(n)（使用 ElementAt LINQ 扩展），如果 5 是典型大小，这可能不是真正的问题。如果你想要 O(1) 我怀疑你必须自己动手（https://github.com/mono/mono/blob/master/mcs/class/System/System.Collections.Generic/Queue.cs? source=cc可能会有所帮助！）

于 2013-08-12T02:45:31.617 回答
0

在这种情况下，队列是最好的，您应该编写自己的包装类，在入队之前检查您的计数（限制）（将新数据添加到列表末尾）以使其表现得像一个固定的，这里是一个例子：

public class FixedQueue<T> : Queue<T>
{
//to sets the total number of elements that can be carried without resizing,
//we called the base constrctor that takes the capacity
    private Random random;
    public int Size { get; private set; }

    public FixedQueue(int size, Random random)
        :base(size)                 
    {
         this.Size = size;
         this.random = random;
    }

    public new void Enqueue(T element)
    {
        base.Enqueue(element);
        lock (this)
            while (base.Count > Size)
                base.Dequeue();  //as you said, "Oldest data falls off" :)
    }

    public T RandomAcess()
    {
        return this.ElementAt(random.Next(Count));
    }
}
于 2013-08-12T04:12:07.190 回答