Как и когда отказаться от использования массивов в C #?

Question

Мне всегда говорили, что добавление элемента в массив происходит так:

Пустая копия массива + 1 элемент создал, а затем данные из исходный массив копируется в него тогда новые данные для нового элемента затем загружено

Если это так, то использование массива в сценарии, который требует большой активности элементов, противопоказано из-за использования памяти и ЦП, верно?

Если это так, разве вы не должны стараться избегать использования массива как можно чаще, когда будете добавлять много элементов? Стоит ли использовать вместо этого iStringMap? Если это так, что произойдет, если вам нужно более двух измерений И нужно добавить много добавлений элементов. Вы просто принимаете удар по производительности или есть что-то еще, что следует использовать?

Answer 1

Посмотрите на общий List<T> как замену массивов. Они поддерживают большинство тех же функций, что и массивы, включая выделение начального размера хранилища, если хотите.

Answer 2

Это действительно зависит от того, что вы подразумеваете под "добавить".

Если вы имеете в виду:

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

Тогда нет, это не создает новый массив и фактически является самым быстрым способом изменения любого вида IList в .NET.

Если, однако, вы используете что-то вроде ArrayList, List, Collection и т. Д., То вызов метода «Add» может создать новый массив - но они умны в этом, они не просто изменяйте размер на 1 элемент, они растут геометрически, поэтому, если вы добавляете много значений только время от времени, ему придется выделять новый массив. Даже в этом случае вы можете использовать свойство "Capacity", чтобы заставить его расти раньше, если вы знаете, сколько элементов вы добавляете (list.Capacity += numberOfAddedElements)

Answer 3

Если вы собираетесь много добавлять / удалять элементы, просто используйте список. Если он многомерный, вы всегда можете использовать List > или что-то еще.

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

Если вы хотите использовать массив для эффективного чтения, но собираетесь часто «добавлять» элементы, у вас есть два основных варианта:

1) Создайте его как список (или список списков), а затем используйте ToArray (), чтобы превратить его в эффективную структуру массива.

2) Выделите массив так, чтобы он был больше, чем вам нужно, затем поместите объекты в предварительно выделенные ячейки. Если вам понадобится даже больше элементов, чем было выделено заранее, вы можете просто перераспределить массив при его заполнении, удваивая размер каждый раз. Это дает производительность изменения размера O (log n) вместо O (n), как это было бы с массивом reallocate-один-на-добавление. Обратите внимание, что именно так работает StringBuilder, предоставляя вам более быстрый способ непрерывного добавления строки.

Answer 4

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

Если вы используете 0,1% использования, требующего предельной скорости, убедитесь, что доступ к вашему списку действительно является проблемой, прежде чем пытаться оптимизировать его.

Answer 5

Когда отказаться от использования массивов

1. Прежде всего, , когда семантика массивов не совпадает с вашим намерением - Нужна динамически растущая коллекция? Набор, который не позволяет дубликаты? Коллекция, которая должна оставаться неизменной? Избегайте массивов во всех этих случаях. Это 99% случаев. Просто констатирую очевидную основную мысль.

2. Во-вторых, , когда вы не кодируете для абсолютной критичности производительности - это примерно в 95% случаев. Массивы работают лучше незначительно , особенно в итерации . Это почти всегда никогда не имеет значения.

3. Когда вы не вынуждены аргументом с params ключевым словом - я просто хотел params принять любой IEnumerable<T> или даже лучше языковой конструкции сам по себе для обозначения последовательности (а не типа фреймворка).

4. Когда вы не пишете устаревший код или имеете дело с взаимодействием

Короче говоря, это очень редко, что вам на самом деле нужен массив. Я добавлю, почему можно этого избежать?

1. Самая большая причина избегать массивов imo - концептуальная. Массивы ближе к реализации и дальше от абстракции. Массивы передают больше , как это делается , чем , что делается , что противоречит духу языков высокого уровня. Это неудивительно, учитывая, что массивы ближе к металлу, они прямо из специального типа (хотя внутренне массив - это класс). Не для того, чтобы быть педагогическим, но массивы действительно переводят в семантическое значение, которое очень редко требуется. Наиболее полезной и частой семантикой является семантика с любыми записями, наборами с различными элементами, картами значений ключей и т. Д. С любой комбинацией добавляемых, доступных только для чтения, неизменных, уважающих порядок вариантов. Подумайте об этом, вы можете захотеть добавить коллекцию с возможностью добавления или коллекцию только для чтения с предопределенными элементами без дальнейшей модификации, но как часто ваша логика выглядит так: «Я хочу динамически добавляемую коллекцию, но только с фиксированным числом из них, и они также должны быть модифицируемыми» «? Очень редко я бы сказал.

2. Массив был разработан в эпоху, предшествующую дженерикам, и имитирует универсальность с большим количеством хаков во время выполнения, и он покажет свои странности здесь и там. Некоторые из уловов, которые я нашел:

   1. Сломанная ковариация.

      string[] strings = ...
      object[] objects = strings;
      objects[0] = 1; //compiles, but gives a runtime exception.
      

   2. Массивы могут дать вам ссылку на структуру! . Это не похоже ни на что другое. Образец:

      struct Value { public int mutable; }
      
      var array = new[] { new Value() };  
      array[0].mutable = 1; //<-- compiles !
      //a List<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
      print array[0].mutable // 1, expected or unexpected? confusing surely
      

   3. Методы, реализованные во время выполнения, такие как ICollection<T>.Contains, могут различаться для структур и классов . Это не имеет большого значения, но если вы забудете переопределить non generic Equals правильно для ссылочных типов, ожидающих, что универсальная коллекция будет искать generic Equals, вы получите неверные результаты.

      public class Class : IEquatable<Class>
      {
          public bool Equals(Class other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      public struct Struct : IEquatable<Struct>
      {
          public bool Equals(Struct other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      class[].Contains(test); //prints "non generic"
      struct[].Contains(test); //prints "generic"
      

   4. Свойство Length и индексатор [] в T[] кажутся обычными свойствами, к которым вы можете получить доступ через отражение (что должно включать в себя некоторую магию), но когда дело доходит до деревьев выражений, вы должны плюнуть из того же кода, что и компилятор. Существуют ArrayLength и ArrayIndex методы для этого отдельно. Один такой вопрос здесь . Другой пример:

      Expression<Func<string>> e = () => new[] { "a" }[0];
      //e.Body.NodeType == ExpressionType.ArrayIndex
      
      Expression<Func<string>> e = () => new List<string>() { "a" }[0];
      //e.Body.NodeType == ExpressionType.Call;
      

Как отказаться от использования массивов

Наиболее часто используемый заменитель - List<T>, который имеет более чистый API. Но это динамически растущая структура, которая означает, что вы можете добавить к List<T> в конце или вставить куда угодно на любую емкость. Точное поведение массива ничем не заменит, но люди обычно используют массивы как коллекцию только для чтения, где вы ничего не можете добавить к ее концу. Заменитель - ReadOnlyCollection<T>. Я несу этот метод расширения:

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}

Answer 6

Как правило, если вам нужна производительность поиска по индексу BEST, лучше сначала создать список, а затем превратить его в массив, заплатив сначала небольшое наказание, но избегая позже. Если проблема заключается в том, что вы будете постоянно добавлять новые данные и удалять старые, тогда вы можете использовать ArrayList или List для удобства, но имейте в виду, что это просто особые массивы. Когда они «растут», они выделяют совершенно новый массив и копируют в него все, что очень медленно.

ArrayList - это просто массив, который увеличивается при необходимости. Добавить амортизируется O (1), просто будьте осторожны, чтобы убедиться, что изменение размера не произойдет в плохое время. Insert is O (n), все элементы справа должны быть перемещены. Удалить - это O (n), все элементы справа должны быть перемещены.

Также важно помнить, что Список не является связанным списком. Это просто типизированный ArrayList. Документация List отмечает, что в большинстве случаев она работает лучше, но не объясняет почему.

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

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

-Rick

Answer 7

ArrayList и List увеличивают массив более чем на один при необходимости (я думаю, что это удваивает размер, но я не проверял источник). Как правило, они являются лучшим выбором при создании массива динамического размера.

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

Answer 8

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

Итак, вы не должны использовать массивы, если вы не знаете размер массива, или размер может измениться. Однако, если у вас есть массив фиксированной длины, это простой способ получения элементов по индексу.

Answer 9

Если вы собираетесь много добавлять, и вы не будете использовать произвольный доступ (например, myArray[i]). Вы можете рассмотреть возможность использования связанного списка (LinkedList<T>), потому что он никогда не будет «расти», как реализация List<T>. Имейте в виду, что вы можете получить доступ к элементам в реализации LinkedList<T> только с помощью интерфейса IEnumerable<T>.

Answer 10

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

В другой раз я обычно использую массив над списком, когда мне нужно вернуть коллекцию как свойство объекта - я не хочу, чтобы вызывающие добавляли элементы из этой коллекции с помощью методов Add списка, а вместо этого хотели бы, чтобы они добавляли элементы в коллекцию через интерфейс моего объекта. В этом случае я возьму внутренний List и вызову ToArray и верну массив.