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

https://stackoverflow.com/questions/75976

09-06-2019
|

Вопрос

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

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

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

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

Решение

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

Другие советы

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

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

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

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

Если, однако, вы используете что-то вроде ArrayList, Списка, Коллекции и т.д.затем вызываем метод "Добавить" мочь создайте новый массив - но они умны в этом, они не просто изменяют размер на 1 элемент, они растут геометрически, поэтому, если вы добавляете много значений только время от времени, ему придется выделять новый массив.Даже тогда вы можете использовать свойство "Capacity", чтобы заставить его расти заранее, если вы знаете, сколько элементов вы добавляете (list.Capacity += numberOfAddedElements)

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

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

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

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

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

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

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

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

Первое и самое главное, когда семантика массивов не надо совпадайте с вашим намерением - Нужна динамично растущая коллекция?Набор, который не допускает дубликатов?Коллекция, которая должна оставаться неизменной?Избегайте массивов во всех этих случаях.Это в 99% случаев.Просто констатирую очевидный основной момент.
Во - вторых, когда ты будешь нет кодирование для обеспечения абсолютной критичности производительности - Это примерно в 95% случаев. Массивы работают лучше незначительно, особенно в итерации.Это почти всегда не имеет значения.
Когда ты нет вынужденный ссорой с params ключевое слово - Я просто хотел params принято любое IEnumerable<T> или, что еще лучше, саму языковую конструкцию для обозначения последовательность (и не является типом фреймворка).
Когда ты будешь нет написание устаревшего кода или работа с взаимодействием

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

Самая большая причина избегать массивов imo - концептуальная.Массивы ближе к реализации и дальше от абстракции.Массивы передают больше как это делается чем что сделано что противоречит духу языков высокого уровня.Это неудивительно, учитывая, что массивы ближе к металлу, они прямо из особого типа (хотя внутренне array - это класс).Не хочу показаться педагогичным, но массивы действительно переводятся в семантическое значение, которое требуется очень, очень редко.Наиболее полезной и частой семантикой являются коллекции с любыми записями, наборы с различными элементами, карты значений ключей и т.д. С любой комбинацией добавляемых, доступных только для чтения, неизменяемых вариантов, соблюдающих порядок.Подумайте об этом, возможно, вам понадобится добавляемая коллекция или коллекция только для чтения с предопределенными элементами без дальнейших изменений, но как часто ваша логика выглядит как "Я хочу динамически добавляемую коллекцию, но только фиксированное их количество, и они тоже должны быть изменяемыми"?Я бы сказал, очень редкий.
Array был разработан в эпоху, предшествующую появлению дженериков, и он имитирует универсальность с большим количеством взломов во время выполнения, и он будет демонстрировать свои странности здесь и там.Некоторые из уловов, которые я нашел:
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 могут быть разными для структур и классов.Это не имеет большого значения, но если вы забудете переопределить непатентованный Equals корректно для ссылочных типов, ожидающих поиска универсальной коллекции общий 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();
}

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

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

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

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

Как правило, если вам нужна НАИЛУЧШАЯ производительность индексированного поиска, лучше всего сначала создать список, а затем превратить его в массив, таким образом, сначала заплатив небольшой штраф, но избегая его в дальнейшем.Если проблема заключается в том, что вы будете постоянно добавлять новые данные и удалять старые, то вы можете захотеть использовать ArrayList или список для удобства, но имейте в виду, что это всего лишь массивы особого случая.Когда они "растут", они выделяют совершенно новый массив и копируют все в него, что происходит чрезвычайно медленно.

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

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

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

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

-Рик

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

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

Вы правы, массив отлично подходит для поиска.Однако изменение размера массива требует больших затрат.

Вы должны использовать контейнер, который поддерживает инкрементную корректировку размера в сценарии, в котором вы изменяете размер массива.Вы могли бы использовать ArrayList, который позволяет вам устанавливать начальный размер, и вы могли бы постоянно проверять размер в зависимости от емкости, а затем увеличивать емкость на большой фрагмент, чтобы ограничить количество изменений размера.

Или вы могли бы просто использовать связанный список.Тогда, однако, поиск происходит медленно...

Этот пост на форуме может быть вам полезен, а может и не быть полезен в отношении эффективности различных типов массивов:Массивы C # - многомерные против лексикографических

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

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

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

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

Это правило, которое вы можете применить к чему угодно на самом деле.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow