Коллекция C#, оптимизированная для вставки индекса 0?

Question

Какие коллекции C# лучше всего оптимизированы как для вставки нулевого индекса, так и для добавления к концу?

Я думаю, что простой - LinkedList, но, учитывая мой интерес, в больших байт-буферах, я подозреваю, что стоимость памяти за узел может быть непомерно дорогостоящей для моих нужд.

Я понимаю, что нормальный List имеет буферную поддержку с емкостью, обычно большей, чем фактические данные. Когда данные заполняют буфер, создается новый буфер, а содержимое старого переносится на новый. Это отлично подходит для добавления к концу, но ужасно для роста в начале. Мои тесты, добавление/вставка миллион случайных целых чисел в List:

• Список Append время 0.014sec.
• Список Нулевой Вставить время 173.343sec

Answer 1

Мое решение, как упоминал Эрик Липперт; сохраняйте реальные данные, плавающие в середине буфера поддержки, а не в начале. Однако это все еще список, а не очередь; все еще можно добавить/удалить/заменить повсюду.

public class BList<T> : IList<T>, IReadOnlyList<T> 
{ 
    private const int InitialCapacity = 16; 
    private const int InitialOffset = 8; 

    private int _size; 
    private int _offset; 
    private int _capacity; 
    private int _version; 

    private T[] _items; 

    public BList() 
    { 
     _version = 0; 
     _size = 0; 
     _offset = InitialOffset; 
     _capacity = InitialCapacity; 
     _items = new T[InitialCapacity]; 
    } 

    public BList(int initialCapacity) 
    { 
     _size = 0; 
     _version = 0; 
     _offset = initialCapacity/2; 
     _capacity = initialCapacity; 
     _items = new T[initialCapacity]; 
    } 

    public void Insert(int insertIndex, T item) 
    { 
     if (insertIndex < 0) 
      throw new ArgumentOutOfRangeException(nameof(insertIndex)); 

     var padRight = Math.Max(0, (insertIndex == 0) ? 0 : (insertIndex + 1) - _size); 
     var padLeft = insertIndex == 0 ? 1 : 0; 

     var requiresResize = _offset - padLeft <= 0 || 
           _offset + _size + padRight >= _capacity; 
     if (requiresResize) 
     { 
      var newSize = _size + 1; 
      var newCapacity = Math.Max(newSize, _capacity * 2); 
      var newOffset = (newCapacity/2) - (newSize/2) - padLeft; 
      var newItems = new T[newCapacity]; 

      Array.Copy(_items, _offset, newItems, newOffset, insertIndex); 
      Array.Copy(_items, _offset, newItems, newOffset + 1, _size - insertIndex); 

      newItems[newOffset + insertIndex] = item; 

      _items = newItems; 
      _offset = newOffset; 
      _size = newSize; 
      _capacity = newCapacity; 
     } 
     else 
     { 
      if (insertIndex == 0) 
       _offset = _offset - 1; 
      else if (insertIndex < _size) 
       Array.Copy(_items, _offset + insertIndex, _items, _offset + insertIndex + 1, _size - insertIndex); 

      _items[_offset + insertIndex] = item; 

      _size = _size + 1; 
     } 

     _version++; 
    } 

Full code

Тест вставки Count: 131072

Answer 2

Причина списки (и массивы в целом) плохо для вставки, является то, что все элементы после индекса вставки должны быть перемещены вверх.

Самый лучший вариант для вставки в начале - это связанный список, так как вам нужно только изменить ссылки на первый элемент, предыдущий элемент (по первому первому элементу) и следующий элемент. Это простые операции.

Проблема со вставкой связанного списка на полпути - это то, что вам нужно пройти весь список, чтобы получить элемент в позиции X. Это не работает для больших связанных списков. Если у вас есть много вставки в позиции 0, вы можете попробовать (если возможно) перевернуть список, который вы можете вставить «до конца».

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

Answer 3

Вы можете создать свою собственную реализацию IList<T>, которая содержит два списка: один для элементов, добавленных на передний план (хранится в обратном порядке), и один для элементов, добавленных в спину (в правильном порядке). Это обеспечит, чтобы все ваши вставки в самом начале или конце списка были O (1) (за исключением нескольких случаев, когда необходимо увеличить емкость).

public class TwoEndedList<T> : IList<T> 
{ 
    private readonly List<T> front = new List<T>(); 
    private readonly List<T> back = new List<T>(); 

    public void Add(T item) 
    { 
     back.Add(item); 
    } 

    public void Insert(int index, T item) 
    { 
     if (index == 0) 
      front.Add(item); 
     else if (index < front.Count) 
      front.Insert(front.Count - index, item); 
     else 
      back.Insert(index - front.Count, item); 
    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return front.Reverse<T>().Concat(back).GetEnumerator(); 
    } 

    // rest of implementation 
} 

Answer 4

Структура данных, которая имеет форму списка, но оптимизирована для вставки и удаления на обоих концах - но не середина - называется Deque, который является коротким для «двусвязной очереди ». Я не знаю, содержит ли стандартная библиотека deque в эти дни.

Если вы заинтересованы в методах построения неизменные двусторонних очередей, я предлагаю вам прочитать, в порядке возрастания сложности:

• Моя серия статей о неизменных типов данных, в частности, это: https://blogs.msdn.microsoft.com/ericlippert/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue/
• Этот вопрос и вопросы: Implement an immutable deque as a balanced binary tree?
• Книга Криса Окасаки «Чисто функциональные структуры данных» описывает, как создать деку, которая является O (1) во всех операциях, умным использованием ленивой конструкции и заметок

Если вы хотите создать изменяемый deque, это довольно просто сделать, используя те же методы, что и список. Список - это всего лишь обертка вокруг массива, где массив «слишком велик» в дальнем конце. Чтобы сделать изменяемый deque, вы можете сделать массив, который слишком велик, но данные находятся посередине, а не на маленьком конце. Вам просто нужно отслеживать, каковы верхние и нижние индексы данных, и когда вы сталкиваетесь с любым из концов массива, перераспределите массив и скопируйте данные в середину.

Answer 5

раздвоенной очередь, как отметили другие, что вы ищете. Существует приличный список на основе реализации здесь, который поддерживает enqueueing/извлечение из/выглядывает и т.д., как вы могли бы ожидать от правильной очереди, и на обоих концах, в то время как поддержка всех типовых операций, а также список:

IDoubleEndedQueue

DoubleEndedQueue

ConcurrentDoubleEndedQueue (если потокобезопасность желательно)

Как уже упоминалось, при реализации Deque с основной список, вставки/удаления в середине требуется сдвиг массива (боль, которая может быть слегка смягченным благодаря возможности сдвигаться в более коротком направлении, чем в худшем случае вставки/удаления с индексом 0 с традиционным списком).