Есть ли причина использовать массив при наличии списков? [закрыто]

30

Кажется, что List<T>в C # можно делать все, что может делать массив, и даже больше, и кажется, что он также эффективен в памяти и производительности, как и массив.

Так зачем мне использовать массив?

Я явно не спрашиваю о случаях, когда API или другое внешнее ограничение (то есть функция Main) требует от меня использования массива ... Я только спрашиваю о создании новых структур данных в своем собственном коде.

JoelFan
источник
56
Для реализацииList<T>
чокнутый урод
43
is also just as efficient in memory and performance as an array- гм. Откуда вы взяли это понятие?
Одед
12
Несколько измерений, как var test = new string[5,5];)
Knerd
7
Также есть широко используемый массив byte [].
SBoss
11
В частности, для C # Эрик Липперт написал об этом в blogs.msdn.com/b/ericlippert/archive/2008/09/22/… .
Мефи

Ответы:

26

По той же причине я не езжу на грузовике, когда иду на работу. Я не использую то, что я не буду использовать функции.

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

Самая важная причина, по которой я использую массив вместо List <>, заключается в том, что данные имеют фиксированную длину . Если я не буду добавлять или удалять какие-либо элементы из этой коллекции данных, я хочу убедиться, что тип отражает это.

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

И иногда проще портировать кусок кода, который использует массив вместо фреймворк-зависимого типа.

Мерт Акчакая
источник
4
Как массив «быстрее» списка, учитывая, что List<T>он реализован с использованием массива? Если вы знаете количество элементов заранее (что необходимо знать при использовании массива), вы можете использовать эти знания и при инициализации списка.
Теодорос Чатциганнакис
1
@TheodorosChatzigiannakis При использовании массива мы выделяем память и просто делаем присваивания, просто malloc (), никаких накладных расходов. Когда вы используете List <>, вы будете «добавлять» элементы, а при добавлении элементов List <> выполняет некоторую проверку границ и вызывает метод EnsureCapacity, который копирует содержимое в другой вновь выделенный массив, если текущей емкости недостаточно. Это означает, что если вам не нужно динамически выделять новую память, производительность List не такая хорошая, как у массива.
Мерт Акчакая
4
То , что вы хотите сказать , что это правильно, но это предполагает , что либо мы заранее не знаем количество элементов (в этом случае, массивы не являются полезными в любом случае) , или что мы делаем знать количество элементов заранее , но мы намеренно не использовать это в случае со списком. Если мы делаем использовать количество элементов , чтобы инициализировать список с требуемой мощностью, мы получаем только один выделение массива (пока вы не достигнете этого потенциала), таким образом , мы платим ту же затрату производительности. Все остальные общие операции одинаковы (поиск, поиск по индексу, присваивание по индексу), за исключением дальнейших добавлений (которых у массивов нет вообще).
Теодорос Чатзигианнакис
3
@TheodorosChatzigiannakis: массивы работают быстрее, чем списки. Просто запустите простой тест, чтобы проверить.
Мердад
1
@TheodorosChatzigiannakis, да, но есть еще пограничные проверки.
Мерт Акчакая
18

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

struct EvilMutableStruct { public double X; } // don't do this

EvilMutableStruct[] myArray = new EvilMutableStruct[1];
myArray[0] = new EvilMutableStruct()
myArray[0].X = 1; // works, this modifies the original struct

List<EvilMutableStruct> myList = new List<EvilMutableStruct>();
myList.Add(new EvilMutableStruct());
myList[0].X = 1; // does not work, the List will return a *copy* of the struct

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


Более серьезно, вам нужен массив, если вы хотите передать элемент по ссылке . т.е.

Interlocked.Increment(ref myArray[i]);  // works
Interlocked.Increment(ref myList[i]);   // does not work, you can't pass a property by reference

Это может быть полезно для беззащитного кода без блокировки.


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

double[] myArray = new double[1000]; // contains 1000 '0' values
                                     // without further initialisation

List<double> myList = new List<double>(1000) // internally contains 1000 '0' values, 
                                             // since List uses an array as backing storage, 
                                             // but you cannot access those
for (int i =0; i<1000; i++) myList.Add(0);   // slow and inelegant

(обратите внимание, что было бы возможно реализовать конструктор для List, который делает то же самое, просто C # не предлагает эту функцию)


вам нужен массив, если вы хотите эффективно копировать части коллекции

Array.Copy(array1, index1, array2, index2, length) // can't get any faster than this

double[,] array2d = new double[10,100];
double[] arraySerialized = new double[10*100];
Array.Copy(array2d, 0, arraySerialized, 0, arraySerialized.Length);
// even works for different dimensions

(опять же, это то, что может быть реализовано и для List, но эта функция не существует в c #)

HugoRune
источник
Если тип должен представлять группу связанных, но независимых переменных, склеенных с клейкой лентой (например, координаты точки), структура открытого поля является лучшим представлением. Если переменная должна содержать группу таких групп, массив этого типа структуры является лучшим представлением. Не следует использовать изменяемые структуры в местах, где требуется объект, но это не означает, что следует использовать объекты или вещи, которые претендуют на то, чтобы быть объектами, в местах, где требуется связка переменных с клейкой лентой.
суперкат
В некоторых ситуациях вам может понадобиться изменяемая структура, например, когда вам нужен последний бит производительности, и вы не можете позволить себе выделение кучи и ссылки, и в этом случае массив структур - ваш лучший выбор. Хорошее эссе здесь . Но я бы не согласился с тем, что класс не должен представлять «кучу переменных, слипшихся». Концептуально структуры и классы в основном одинаковы, различия в основном связаны с деталями реализации.
HugoRune
Если кто-то хочет использовать коллекцию ссылок на изменяемые объекты как коллекцию независимых групп независимых переменных, необходимо установить и поддерживать инвариант, согласно которому каждый элемент идентифицирует объект, на который в юниверсе не существует других неэфемерных ссылок. Это, безусловно, может быть сделано (и часто так и есть), но в языке или структуре нет ничего, что могло бы помочь программисту в поддержке этого инварианта. В отличие от этого, массив длины-100 типа структуры с четырьмя полями экземпляров автоматически и навсегда инкапсулирует 400 независимых переменных.
суперкат
Я думаю, что эти комментарии являются неподходящим местом для дальнейшего обсуждения этого вопроса, и, учитывая, что вы добавили свой собственный ответ , нет необходимости дублировать эту информацию здесь. Достаточно сказать, что массивы могут использоваться для управления изменчивыми структурами. Вопрос о том, когда и когда использовать поведение реализации этих структур для реализации определенных ограничений данных, выходит за рамки моего ответа.
HugoRune
15

Так зачем мне использовать массив?

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

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

Telastyn
источник
23
Размер массивов не устанавливается в камне в то время, когда пишется код. Это может быть и часто является переменной времени выполнения. Это просто никогда не изменяется после того, как массив был создан .
11
Нет ничего необычного в том, чтобы иметь дело с фиксированным количеством элементов. Если вы работаете с 3D-точками, вы, вероятно, не будете работать с 5D-точками в будущем. Большая проблема с массивами заключается в том, что они изменчивы и не имеют удобных ярлыков, прикрепленных к их элементам.
Доваль
3
@JanDvorak Списки могут уменьшаться или увеличиваться и поэтому не имеют смысла ни в каком контексте, включающем фиксированное количество элементов.
Довал
9
Редко? Не все работают над сверхсложными сверхконфигурируемыми корпоративными чудовищами.
whatsisname
3
Очень распространено иметь фиксированное количество элементов. Просто убедитесь, что длина определяется константой, поэтому, когда в следующем выпуске число элементов увеличивается с 3 до 4, вы просто меняете константу, и все, что зависит от этого, адаптируется.
Ганс
9

На ваш вопрос уже был дан ответ .

и кажется также столь же эффективным в памяти и производительности как массив.

Это не так. Из вопроса я связал:

List/foreach:  3054ms (589725196)
Array/foreach: 1860ms (589725196)

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

Так как основная предпосылка вашего вопроса, таким образом, побеждена, я предполагаю, что это отвечает на ваш вопрос. В дополнение к этому, иногда массивы навязываются вам Win32 API, шейдером вашего GPU или какой-либо другой не-DotNet библиотекой.

Даже в DotNet некоторые методы потребляют и / или возвращают массивы (например, String.Split). Это означает, что либо вы теперь должны потреблять стоимость вызовов ToListи ToArrayвсе время, либо вы должны согласовывать и использовать массив, возможно, продолжая цикл, передавая это бедным нижестоящим пользователям вашего кода.

Больше вопросов и ответов по переполнению стека на эту тему:

Superbest
источник
Интересно, что этот ответ указывает на то, что если вы используете старомодные индексированные циклы ( для вместо foreach ), разница в производительности будет минимальной.
user949300
3

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

var array = new [] { "A", "B", "C" };
var list = new List<string>() { "A", "B", "C" };

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

Я делал это время от времени в модульных тестах.

IKH
источник
1
Да, просто чтобы добавить. Это также работает, вам нужно сдать IList <T>
Эсбен Сков Педерсен
+1, часто у меня есть какая-то операция для пары объектов одного типа, которых нет в коллекции. Это легко, коротко и понятно написать foreach( var x in new []{ a, b, c ) ) DoStuff( x )или new []{ a, b, c ).Select( ... )т. Д.
stijn
3

Это строго с точки зрения ОО.

Хотя я не могу придумать причину для передачи всего лишь массива, я, конечно, вижу ситуации, когда представление массива внутри класса, вероятно, является лучшим выбором.

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

Существует значительное количество научных областей, которые широко используют матричную математику. (например, обработка изображений, исправление ошибок в данных, цифровая обработка сигналов, множество прикладных математических задач). Большинство алгоритмов в этих областях написаны с точки зрения использования многомерных массивов / матриц. Поэтому было бы более естественно реализовать алгоритмы по мере их определения, а не делать их более «программными» дружественными за счет потери прямой привязки к документам, на которых основаны алгоритмы.

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

Замочить
источник
3

Это на самом деле относится и к другим языкам, которые также имеют списки (например, Java или Visual Basic). Есть случаи, когда вам нужно использовать массив, потому что метод возвращает массив вместо List.

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

Дилан Миус
источник
1
Многие языки даже не имеют отдельных списков и массивов. С другой стороны, использование list<T>where vector<T>будет работать - ужасно плохая идея в C / C ++.
Gort the Robot
1
«Потому что метод возвращает массив» - это ошибка Java, вынуждающая программистов накапливать код с помощью «Arrays.asList (x)». T [] должен по крайней мере реализовать Iterable <T>
Кевин Клайн
4
@StevenBurnap - это ужасно плохо в C, потому что нет способа скомпилировать этот код.
Пит Беккер
@PeteBecker Выражение vector<T> x компилируется нормально для меня в C . :-)
svick
Извините, я имел в виду C-свернутый вручную эквивалент list<T>. По сути, я видел много проблем с производительностью, вызванных разработчиками, которые просто использовали списки по умолчанию, когда массив был лучшим выбором.
Gort the Robot
1

Ну, я нашел применение для массивов в игре, которую я писал. Я использовал его для создания системы инвентаря с фиксированным количеством слотов. Это имело несколько преимуществ:

  1. Я точно знал, сколько открытых слотов инвентаря имеет игровой объект, посмотрев, какие слоты были нулевыми.
  2. Я точно знал, в каком индексе был каждый элемент.
  3. Это был все еще «типизированный» массив (Item [] Inventory), поэтому я мог добавлять / удалять объекты типа «Item».

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

Монтана
источник
1

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

Но если вашему алгоритму необходим произвольный доступ к элементам в коллекции, тогда да, массив необходим.

Это несколько аналогично «нужно ли идти?». На разумном современном языке это вообще не нужно. Но если вы удалите абстракции, в какой-то момент это все, что вам действительно доступно, то есть единственный способ реализовать эти абстракции - использовать функцию «ненужные». (Конечно, аналогия не идеальна, я не думаю, что кто-то говорит, что массивы - плохая практика программирования; их легко понять и подумать).

Митч
источник
Список <T> также предлагает произвольный доступ. Конечно, это реализовано с помощью массива, но это не должно беспокоить вас, пользователя. В лучшем случае вы предложили одну причину использования массивов: для реализации List<T>.
@delnan Я думаю, что это моя точка зрения в отношении абстракций. Иногда лучше думать с точки зрения массива, а не только по соображениям эффективности. (конечно, иногда лучше думать о связанном списке и лучше думать о списке (не заботясь о ссылках или каким-либо иным образом о том, как он реализован), а лучше просто о коллекции.
Mitch
0

Устаревшая совместимость.

Все формы личного опыта:

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

Устаревший код - foo (панель массива []) уверен, что вы можете использовать функцию toarray списка / вектора / коллекции, но если вы не используете какие-либо дополнительные функции, проще начать использовать массив, часто более читаемый без переключения типов.

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

Skeith
источник
3
коллеги, которые за 20 лет отстали, и босс, который хочет знать, какие типы данных вы используете ... Мне нравится этот сайт, чтобы напомнить себе, насколько хуже может быть моя работа
JoelFan
1
около 40% того, что мы делаем, - это встраиваемый дизайн, где обсуждения ведутся в КБ, ему нравится говорить мне, что он не устарел, он спекулировал, лол
Skeith
0

1) Нет многомерной версии List. Если ваши данные имеют более одного измерения, использование списков будет очень неэффективным.

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

В крайнем случае рассмотрим Minecraft. (Да, это не написано на C #. По той же причине.)

Лорен Печтель
источник
0

Массив из 100 элементов некоторого типа T инкапсулирует 100 независимых переменных типа T. Если T оказывается типом значения, который имеет изменяемое открытое поле типа Q и одно из типа R, то каждый элемент массива будет инкапсулировать независимые переменные типов Q и R. Таким образом, массив в целом будет инкапсулировать 100 независимых переменных типа Q и 100 независимых переменных типа R; Любая из этих переменных может быть доступна по отдельности, не затрагивая другие. Ни один тип коллекции, кроме массивов, не позволяет использовать поля структур в качестве независимых переменных.

Если вместо этого T оказался типом класса с открытыми изменяемыми полями типа Q и R, то каждый элемент массива содержит единственную ссылку, где угодно в юниверсе, на экземпляр T, и если ни один из элементов массива не будет когда-либо быть изменен для идентификации объекта, на который существует какая-либо внешняя ссылка, тогда массив будет эффективно инкапсулировать 100 независимых переменных типа Q и 100 независимых переменных типа R. Другие типы коллекций могут имитировать поведение такого массива, но если это единственная цель массив состоит в том, чтобы инкапсулировать 100 переменных типа Q и 100 типа R, инкапсуляция каждой пары переменных в свой собственный объект класса является дорогостоящим способом сделать это. Дальше,использование массива или коллекции изменяемого типа класса создает вероятность того, что переменные, идентифицируемые элементами массива, могут быть не независимыми .

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

Supercat
источник
0

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

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

Затем есть реализации списка, такие как ArrayList, которые реализуют список с использованием массива. Они полезные примитивы, чтобы иметь.

Рори Хантер
источник
2
Вопрос, в частности, задается о типе .Net List<T>, который реализуется не с помощью связанного списка, а с использованием массива (по сути, это эквивалентно ArrayList<T>Java).
svick
-2

Вот некоторые рекомендации, которые вы можете использовать, когда выбирать Arrayи когда выбирать List.

  • Используйте Arrayпри возвращении из метода.
  • Используйте Listв качестве переменной при создании возвращаемого значения (внутри метода). Затем используйте .ToArray()при возвращении из метода.

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

Arrayпредназначен для работы со «статическими» коллекциями, а Listдля работы с «динамическими» коллекциями.

Даниэль Лидстрём
источник
2
Правило, которое вы предлагаете, является произвольным и может привести к неэффективному коду, который выполняет ненужное копирование. По крайней мере, вам нужна какая-то форма оправдания для этого.
Жюль
@Jules Я считаю, что опыт разработчика гораздо важнее микрооптимизации. У меня никогда не было проблем с производительностью на этом уровне.
Даниэль Лидстрем
Однако я не вижу, как опыт разработчика улучшается этим правилом. Это требует от вас угадать, что клиенты вашего кода захотят делать с возвращаемыми значениями, и делает ваш код менее удобным для использования, когда вы ошибаетесь, и все же я не вижу в этом никакого преимущества. Производительность может быть вторичной проблемой, но я бы не стал жертвовать ею, чтобы следовать правилу, которое ничего не дает.
Жюль
@ Джулс Думаю, все зависит от твоих собственных предпочтений. Я предпочитаю рассматривать возвращаемые значения как константы, поэтому я предпочитаю использовать Arrayвместо них List. Приятно слышать ваши мысли, хотя!
Даниэль Лидстрем
Рассматривали ли вы использование UmmodifiableLists?
Жюль