Массив, который может быть изменен быстро
5 ответов
Только суммировать несколько структур данных:
Система. Наборы. ArrayList: невведенные структуры данных являются устаревшими. Используйте Список (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).
Что "достаточно хорошо" для Вас? Что точно Вы хотите сделать с той структурой данных?
Никакая структура массива (т.е. O (n) доступ) не позволяет вставку в середине без O (n) время выполнения; вставка в конце является O (n) худший случай O (1) амортизируемый для самоизменения размеров массивов как ArrayList.
, Возможно, хеш-таблицы (амортизировал O (1) доступ и вставка где угодно, но O (n) худший случай для вставки) или деревья (O (журнал (n)) для доступа и вставки где угодно, гарантируемый) лучше подходят.
Необходимо использовать Универсальный List<> ( Система. Наборы. Универсальный. Список ) для этого. Это работает в постоянное амортизируемое время .
Это также совместно использует следующие функции с Массивами.
- Быстрый произвольный доступ (можно получить доступ к любому элементу в списке в O (1))
- Это быстро для цикличного выполнения более чем
- Медленный, чтобы вставить и удалить объекты в запуске или середина (так как он должен сделать копию всего listbelieve)
при необходимости в быстрых вставках и удалениях в начале или конце используйте или связанный список или очереди
Был бы LinkedList< структура T> работает на Вас? Это не (в некоторых случаях) так же интуитивно как прямой массив, но очень быстро.
- AddLast для добавления в конец
- AddBefore/AddAfter для вставки в список
- AddFirst для добавления к началу
Это не столь быстро для произвольного доступа однако, как необходимо выполнить итерации по структуре для доступа к объектам... однако, он имеет.ToList () и.ToArray () методы для захвата копии структуры в форме списка/массива так для доступа для чтения, Вы могли сделать это в повышении. Увеличение производительности вставок может перевесить снижение производительности потребности в произвольном доступе, или это не может. Это будет зависеть полностью от Вашей ситуации.
существует также эта ссылка, которая поможет Вам решить, который является правильным способом пойти:
, Когда использовать связанный список по массиву/списку массива?
Если скорость является Вашей проблемой, я не вижу, как выбранный ответ немного лучше, чем использование необработанного Массива, хотя это изменяет размер себя, это использует тот же самый механизм, который Вы использовали бы для изменения размеров массива (и должен взять просто касание дольше), ЕСЛИ Вы всегда не добавляете в конец, в этом случае это должно сделать вещи, немного более умные, потому что это выделяет блок за один раз вместо всего одного элемента.
, Если Вы часто добавляете около начала/середины Вашего набора и не индексируете в середину/конец очень часто, Вы, вероятно, хотите Связанный список. Это будет иметь самое быстрое время вставки и будет иметь большое итеративное время, это просто сосет при индексации (такой как рассмотрение 3-го элемента от конца или 72-го элемента).