2

次のように機能する C# データ構造が必要です。

  1. 静的サイズで定義する
  2. リストの最後に新しいデータを追加する
  3. 最も古いデータが落ちます。
  4. データ要素のランダム アクセス

例: 5 つの要素の構造を定義し、次を追加した場合

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

データ構造は次のようになります。

4,5,6,7,8

どの構造がこのように機能するかはわかりません。ベクター？リスト？スタック？データ構造は、配列のような静的サイズをサポートし、古いデータをプッシュするデータをプッシュします。

スタック/キューはランダム アクセスを提供しません。リストには「プッシュ」操作がありません。

おそらくLinkedListで、最初の要素を削除する「プッシュ」のカスタム操作を追加しますか? ただし、LinkList のランダム アクセスは o(n) 操作です。

4

3 に答える 3

5

最大限の効率を得るには、おそらく循環バッファーを実装するカスタム クラスになります。

データを保持するために、インスタンス化時に固定サイズの配列を作成するだけです。さらに、開始インデックス、サイズ メンバー、および容量があるため、バッファー内のデータ量と開始位置がわかります。

したがって、まず、リストにはデータが含まれておらず、開始位置は 0、サイズは 0 です。

アイテムを追加すると、要素に入り、(start + size) % capacityまだsizeにない場合はインクリメントされcapacityます。だった場合はcapacity、同様にインクリメントしstart、必要に応じて次のようにラップしますstart = (start + 1) % capacity。

リストからindex の要素を取得するにはn、実際に次のように調整しますstart。

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

リストの先頭を削除することは仕様にないため、カバーしていません。ただし、 が 0 でないことを確認するのは簡単なチェックであり、次にsizeでアイテムを抽出し、上記と同じラップアラウンドで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数字を85 要素のリストに追加する特定の例では、次のようになります。

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

そうすれば、バッファから仮想インデックス 3 (4 番目の数字) を抽出すると、次の実際のインデックスが得られます。

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

これは最大長のキューです (最大長に達したら、別の要素をキューに入れる前に、1 つの要素をデキューして破棄する必要があります)。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 に答える