Массив, размер которого можно быстро изменять

Question

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

• Система.Массив - Redim Preserve копирует всю оперативную память из старой в новую так же медленно, как количество существующих элементов
• Система.Коллекции.Список массивов - достаточно хорош?
• Система.Коллекции.ИЛист - достаточно хорош?

Answer 1

Просто подведем итог нескольким структурам данных:

Система.Коллекции.Список массивов:нетипизированные структуры данных устарели.Вместо этого используйте List(of t).

Система.Коллекции.Общий.Список(из t):это представляет собой массив с возможностью изменения размера.Эта структура данных использует внутренний массив за кулисами.Добавление элементов в список - это O (1) до тех пор, пока базовый массив не был заполнен, в противном случае это O (n + 1) для изменения размера внутреннего массива и копирования элементов.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

Добавление элементов эффективно только при добавлении в конец списка.Вставка в середину заставляет массив сдвигать все элементы вперед, что является операцией O (n).Удаление элементов также является O (n) , поскольку массиву необходимо переместить элементы назад.

Система.Коллекции.Общий.LinkedList(из t):если вам не нужен случайный или индексированный доступ к элементам в вашем списке, например, вы планируете только добавлять элементы и выполнять итерации от первого к последнему, то LinkedList - ваш друг.Вставки и удаления - O (1), поиск - O (n).

Answer 2

Вы должны использовать Общий список<> (Система.Коллекции.Общий.Список) для этого.Он действует в постоянное амортизированное время.

Он также обладает общими с массивами следующими функциями.

• Быстрый произвольный доступ (вы можете получить доступ к любому элементу в списке в O(1))
• Это быстро зацикливается
• Медленно вставлять и удалять объекты в начале или середине (поскольку для этого необходимо скопировать весь список)

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

Answer 3

Был бы LinkedList< T> структура работает на вас?Это не (в некоторых случаях) так интуитивно понятно, как прямой массив, но работает очень быстро.

• Добавьте последнюю для добавления в конец
• AddBefore/Добавить после для вставки в список
• addFirst для добавления в начало

Однако для произвольного доступа это не так быстро, поскольку вам приходится перебирать структуру, чтобы получить доступ к вашим элементам...однако в нем есть .Методы ToList() и .toArray() для получения копии структуры в виде списка / массива, поэтому для доступа на чтение вы могли бы сделать это в крайнем случае.Увеличение производительности вставок может перевешивать снижение производительности из-за необходимости произвольного доступа, а может и нет.Это будет полностью зависеть от вашей ситуации.

Там также есть эта ссылка, которая поможет вам решить, какой путь является правильным:

Когда следует использовать связанный список поверх массива / array list?

Answer 4

Что для вас "достаточно хорошо"?Что именно вы хотите сделать с этой структурой данных?

Нет структуры массива (т.е.O(n) access) позволяет вставлять в середину без O (n) времени выполнения;вставка в конце - это O (n) в худшем случае O (1), амортизированный для массивов с самоизменяющимся размером, таких как ArrayList.

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

Answer 5

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

Если вы часто добавляете в начале / середине своей коллекции и не очень часто индексируете в середине / конце, вам, вероятно, нужен связанный список.Это будет иметь самое быстрое время вставки и будет иметь большое время итерации, это просто отстой при индексации (например, просмотр 3-го элемента с конца или 72-го элемента).