что следует использовать: массив против связанного списка?

Question

Я планирую реализовать ограниченную очередь без использования класса Queue<T>. После прочтения плюсов и минусов Arrays и LinkedList<T> я больше склоняюсь к использованию массива для реализации функциональности очереди. Коллекция будет фиксированного размера. Я просто хочу добавлять и удалять элементы из очереди.

что-то вроде

public class BoundedQueue<T>
{
   private T[] queue;
   int queueSize;

   public BoundedQueue(int size)
   {
      this.queueSize = size;
      queue = new T[size + 1];
   }
}

вместо

public class BoundedQueue<T>
{
   private LinkedList<T> queue;
   int queueSize;

   public BoundedQueue(int size)
   {
      this.queueSize = size;
      queue = new LinkedList<T>();
   }
}

Я выбрал Array из-за эффективности и из-за того, что коллекция имеет фиксированный размер. Хотел бы получить другие мнения по этому вопросу. Спасибо.

Answer 1

Ну, это было бы ошибкой. Я предполагаю, что вы - бывший программист на C / C ++, std :: list - король. На первый взгляд, это невероятно экономно с памятью, не может сделать список, возможно, более эффективным, чем просто выделение памяти, которая вам нужна, верно? Да, LinkedList делает это.

Но нет, это невероятно несовместимо с тем, как работают кэши ЦП, они действительно как массивы и указатели ненависти. Поместите сборщик мусора поверх него, чтобы он вполне мог упаковывать память.

Тесты для чтения и плаката здесь . Старк.

Answer 2

Я не уверен, почему вы исключили бы использование Queue<T> для внутреннего использования, особенно учитывая, что вы используете LinkedList<T> (они в одной сборке). Queue<T> даст вам наибольшую производительность и использование памяти. Ваш класс может выглядеть примерно так:

public class BoundedQueue<T>
{
    private Queue<T> _queue;
    private int _maxSize;

    public BoundedQueue(int maxSize)
    {
        if (maxSize <= 0)
            throw new ArgumentOutOfRangeException("maxSize");

        _queue = new Queue<T>(maxSize);
        _maxSize = maxSize;
    }

    public int Count
    {
        get { return _queue.Count; }
    }

    /// <summary>
    /// Adds a new item to the queue and, if the queue is at its
    /// maximum capacity, also removes the oldest item
    /// </summary>
    /// <returns>
    /// True if an item was dequeued during this operation;
    /// otherwise, false
    /// </returns>
    public bool EnqueueDequeue(T value, out T dequeued)
    {
        dequeued = default(T);
        bool dequeueOccurred = false;

        if (_queue.Count == _maxSize)
        {
            dequeued = _queue.Dequeue();
            dequeueOccurred = true;
        }

        _queue.Enqueue(value);

        return dequeueOccurred;
    }
}

Но, может быть, у вас была веская причина исключить класс Queue<T>, о котором я просто не могу вспомнить?

Answer 3

Вы, конечно, должны использовать Queue<T>, но в вопросе вы сказали, что не хотите использовать очередь, а вместо этого внедряете очередь самостоятельно. Вы должны сначала рассмотреть ваш вариант использования для этого класса. Если вы хотите что-то реализовать быстро, вы можете использовать LinkedList<T>, но для библиотеки общего назначения вам нужно что-то быстрее.

Вы можете увидеть, как это реализовано в .NET с помощью .NET Reflector. Это поля, которые у него есть:

private T[] _array;
private const int _DefaultCapacity = 4;
private static T[] _emptyArray;
private const int _GrowFactor = 200;
private int _head;
private const int _MinimumGrow = 4;
private const int _ShrinkThreshold = 0x20;
private int _size;
[NonSerialized]
private object _syncRoot;
private int _tail;
private int _version;

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

Что касается безопасности резьбы, ни один из типов не дает никаких гарантий. Например, в документации для LinkedList<T> говорится следующее:

Этот тип не является потокобезопасным. Если к LinkedList необходимо получить доступ несколькими потоками, вам необходимо реализовать собственный механизм синхронизации.

Answer 4

Как будет вести себя ваша ограниченная очередь, когда элемент добавляется сверх его емкости?Будет ли первый предмет вытолкнут таким образом [1, 2, 3] -> [2, 3, 4] или последний элемент будет заменен следующим образом [1, 2, 3] -> [1, 2, 4]?Если первое, то я бы порекомендовал LinkedList.Если последнее, массив или список в порядке.Я просто подумал, что спрошу, потому что поведение вашего объекта будет определять соответствующий курс действий, и это поведение никогда не было определено, насколько я могу судить.Может быть, все, кроме меня, уже точно знают, что вы имели в виду под «ограниченной очередью», но я не хотел предполагать.

Answer 5

Итак, вот основное отличие / преимущества / недостатки использования как массивов, так и связанных списков:

Массивы: - Добавление элементов в массивы может быть относительно дорогостоящим, если вставка не выполняется в конце (а также удаление), поскольку все элементы массива должны быть перемещены. - Очень эффективно, если объект добавлен в конце - Доступ к элементам очень быстрый ... Просто укажите адрес!

LinkedList: - Добавление элементов в любом месте очереди всегда одинаково затратно и очень быстро - Доступ к элементам должен быть сделан с помощью метода доступа (итератор).

Итак, вы пытаетесь реализовать очередь ... но что за очередь? Все зависит от того, что вы будете делать с этим.

Если вы реализуете очередь First In First Out (или Last In Last Out) (например, стек), вам лучше использовать Linked-List, так как вы всегда можете использовать один и тот же метод доступа для доступа к входному или внутреннему вашего списка.

Но если вам нужна очередь и вам нужно постоянно получать доступ к вашим элементам в разных местах, перейдите к массиву!

Из того, что я понял о вашей задаче, я бы порекомендовал Связанный список ... но вы будете знать лучше!

Это будет проблемой только в том случае, если вы начнете иметь ALOT элементов в своей очереди. Если вы останетесь ниже нескольких тысяч, это не

надеюсь, это поможет

Answer 6

Вы можете использовать массив, вам просто нужно вести счет индекса элемента head или перемещать все на единицу каждый раз, когда вы добавляете что-то.Массивы хороши для доступа по индексу, связанные списки хороши для следующей / предыдущей и быстрой вставки. Например,

, если у вас есть [1,2,3,4,5], а заголовок равен 1Вы добавляете 6, вы отбрасываете 5 со спины, я думаю, и ставите шесть на свое место.6 будет новым заголовком, но содержимое массива будет [1,2,3,4,6].