В чем отличие списка от массива js?
Простой 2 комментария
В js нет типа «список».
Так что массив (Array) это список.
Отмеченный ответ не имеет ничего общего с js. Массив в js, это не тот массив, что в C++ или Java.
В большинстве языков, список, это абстракция, которая предоставляет возможность пройтись по элементам и дает какое-то api на доступ, вставку, удаление и т.д. Список внутри может быть чем угодно, может быть массивом, может быть односвязным списком, бинарным деревом, хэш-таблицей, в которой будешь обращаться вроде как к индексу, а за ним, на самом деле хэш.
Массив, действительно, это рядом стоящие в памяти значения. Преимущества, быстрый доступ, т.к он идет всего лишь по сдвигу от начала массива, но вставить невозможно, т.к. под массив выделяется конкретный размер памяти с учетом его типа. Массив можно только пересоздать с новыми значениями.
Список C # против массива
Различия между списком C # и массивом
Класс C # List представляет строго типизированный список объектов, к которым индекс может получить доступ, и он поддерживает сохранение значений определенного типа без приведения к объекту или из него.
| Добавьте целочисленные значения в коллекцию List: List intList = new List (); Добавьте строковые значения в коллекцию List: Цвета списка = новый список (); Получить элементы из коллекции List с помощью цикла for: foreach (цвет строки в цветах) (
Сравнение лицом к лицу между C # List и Array InfographicsНиже приведены 8 лучших отличий между C # List и Array. Ключевые различия между C # List и ArrayОбе версии C # List и Array являются популярным выбором на рынке; Давайте обсудим некоторые основные различия между C # List и Array: Сравнение лицом к лицу между C # List и ArrayНиже приведено самое лучшее сравнение между C # List и Array.
Оба C # List vs Array являются разными типами, имеют разные возможности и хранят свои данные по-разному. Эти возможности хранения и дизайн структур данных C # List и Array делают их уникальными по-своему. Массив имеет фиксированный размер и после его выделения нельзя добавлять или удалять элементы из него, также все элементы должны быть одного типа. Таким образом, это типобезопасная и наиболее эффективная линейная структура данных с точки зрения скорости и производительности. Кроме того, массив поддерживает несколько измерений. Список предоставляет более общие возможности и получен из API-интерфейсов Collection. В отличие от Array, они динамичны по своей природе, могут изменять размеры автоматически при частой вставке и удалении элементов. По сути, это типобезопасная версия структуры данных ArrayList. Функция обеспечения безопасности типов означает, что не будет упаковок или распаковок, которые повысят производительность, и если кто-либо попытается добавить элемент неправильного типа, он выдаст ошибку во время компиляции. Рекомендуемая статьяЧто работает быстрее: массив или ArrayList?Что работает быстрее? Прогнал тест 100 раз. Результаты всегда разные: то один быстрее, то второй. Так есть ли реальный выигрыш в использовании массива вместо ArrayList? ArrayList создавал с нужным размером сразу, чтобы время на «расширение» не тратилось. Проверялось быстродействие команды add. Пытался понять, уменьшит ли замена ArrayList на обычный массив в «узких местах» время выполнения (часто слышал такое предположение). Если в моем случае всегда известен заранее размер массива/листа. Результаты получились случайные. Иногда ArrayList значительно быстрее, иногда массив, иногда они равны. 5 ответов 5Обычный массив почти наверняка будет выигрывать в скорости как при доступе, так и при записи. Хотя бы потому, что при обращении к ArrayList у вас лишний вызов метода, а может и не один. С другой стороны, внутри ArrayList’а тот же самый массив и доступ вполняется по тому же принципу, поэтому если нет чрезмерной нагрузки на него, то в общем их производительность примерно одного порядка. Разница для вас в том, что с листами работать намного проще и удобнее, чем с массивами. По этой причине вам не следует заниматься ерундой и гонять какие-то нелепые тесты, а просто использовать ArrayList, если только у вас нет каких-то ОЧЕНЬ серьёзных оснований использовать массив. Одно из таких оснований: вы точно знаете заранее размер массива и вы точно знаете, что использование этого массива в коде ограничено и вам не придётся городить огород, чтобы гонять потом эти массивы в листы и наоборот. UPD Что за числа в вашем тесте детские? 1000.000? Это просто смешно. Я прогнал тест на выполнение 10.000.000.000 добавлений и получил вот что: UPD2 Убрал сборку мусора вообще и перегруппировал нули и получил следующее Результат очень стабилен. Думаю, на get результаты будут подобные. Когда «О» большое подводит
«О» большое — это отличный инструмент. Он позволяет быстро выбрать подходящую структуру данных или алгоритм. Но иногда простой анализ «О» большого может обмануть нас, если не подумать хорошенько о влиянии константных множителей. Пример, который часто встречается при программировании на современных процессорах, связан с выбором структуры данных: массив, список или дерево. Память, медленная-медленная памятьВ начале 1980-х время, необходимое для получения данных из ОЗУ и время, необходимое для произведения вычислений с этими данными, были примерно одинаковым. Можно было использовать алгоритм, который случайно двигался по динамической памяти, собирая и обрабатывая данные. С тех пор процессоры стали производить вычисления в разы быстрее, от 100 до 1000 раз, чем получать данные из ОЗУ. Это значит, что пока процессор ждет данных из памяти, он простаивает сотни циклов, ничего не делая. Конечно, это было бы совсем глупо, поэтому современные процессоры содержат несколько уровней встроенного кэша. Каждый раз когда вы запрашиваете один фрагмент данных из памяти, дополнительные прилегающие фрагменты памяти будут записаны в кэш процессора. В итоге, при последовательном проходе по памяти можно получать к ней доступ почти настолько же быстро, насколько процессор может обрабатывать информацию, потому что куски памяти будут постоянно записываться в кэш L1. Если же двигаться по случайным адресам памяти, то зачастую кэш использовать не получится, и производительность может сильно пострадать. Если хотите узнать больше, то доклад Майка Актона на CppCon — это отличная отправная точка (и отлично проведенное время). В результате этого массивы стали лучшей структурой данных, когда важна производительность, даже если согласно анализу «О» большого массив должен работать медленнее. Там, где вы хотели использовать дерево, отсортированный массив с двоичным поиском может подойти лучше. Там, где вы хотели использовать очередь, растущий массив может подойти лучше, и так далее. Связный список и динамический массивКогда вы поняли важность доступа к последовательной памяти, для вас не будет сюрпризом тот факт, что если нужно быстро пройти по коллекции, то массив будет быстрее связного списка. Окружения с умным управлением памятью и сборщиками мусора, возможно, будут хранить узлы связного списка более последовательно, но они не могут гарантировать это. Использование сырого массива обычно требует более сложного кода, особенно когда нужно вставлять или добавлять новые элементы, так как придется обрабатывать рост массива, перемещение элементов, и так далее. В большинстве языков есть родные библиотеки, содержащие ту или иную реализацию динамических массивов. В C++ естьvector, в C# есть List (в F# используется под именем ResizeArray), а в Java есть ArrayList. Обычно эти структуры предоставляют такой же или похожий интерфейс, как и связный список. В этой статье я буду называть такие структуры динамическими массивами (Array List), но имейте ввиду, что в примерах на C# используется класс List, а не более старый ArrayList. Что, если нужна структура данных, в которую можно быстро вставлять элементы и быстро проходить по ним? Давайте представим, для этого примера, что у нас такой случай: мы будем вставлять в начало коллекции примерно в 5 раз чаще, чем проходить по ней. Давайте также представим, что и у связного списка, и у динамического массива в нашей среде есть одинаково приятные для работы интерфейсы. Остается только решить, что будет более эффективным решением. Мы можем обратиться к анализу «О» большго для оптимизации нашего ценного времени. Обратимся к полезной подсказке про «О» большое, соответствующие сложности для этих структур данных это:
Проблема динамических массивов заключается во вставке, как минимум нужно будет копировать и двигать каждый элемент на единицу после точки вставки чтобы освободить место для нового элемента. Отсюда O(n). Иногда нужно создать новый массив, больший по размеру чтобы появилось место для вставки. В нашем случае вставка происходит в 5 раз чаще, чем проход, так что, кажется, вывод очевиден. Пока n достаточно большой, связный список должен в целом быть эффективнее. ЭкспериментНо чтобы удостовериться, лучше посчитать. Давайте проведем эксперимент с C#, используя BenchMarkDotNet. В C# есть коллекция LinkedList, которая является классическим связным списком, и List, который является динамическим массивом. Интерфейсы у обоих похожи, и оба можно с легкостью применить в нашем случае. Рассмотрим худший случай для динамического массива — вставка всегда происходит в начало, так что приходится копировать весь массив при каждой вставке. Конфигурация окружения тестирования такая: Тест-кейсы:Результаты:
Где находится переломный момент, зависит от множества факторов, но хорошее приближенное правило предложено Чандлером Каррутом из Google: динамический массив будет эффективнее связного списка до тех пор, пока вставок не станет на порядок больше, чем проходов. В нашем случае правило работает хорошо, потому что при отношении 10:1 можно увидеть сдвиг в сторону связного списка:
Дьявол в деталяхДинамический массив побеждает потому, что числа, по которым происходит проход, находятся в памяти последовательно. Каждый раз, когда происходит запрос числа из памяти, целый набор чисел добавляется в кэш L1, так что следующие 64 байта данных уже готовы к обработке. При работе со связным списком каждый вызов node.Next перенаправляет указатель на следующий узел, и нет гарантий, что этот узел будет находится в памяти сразу за предыдущим. Поэтому иногда мы будем попадать мимо кэша. Но нам не всегда приходится работать с типами, хранящими непосредственно значения, особенно в объектно-ориентированных языках, где проход зачастую происходит по ссылочным типам. В таком случае, не смотря на то, что в динамическом массиве сами указатели находятся в памяти последовательно, объекты, на которые они указывают — нет. Ситуация все еще лучше, чем со связным списком, где вам придется дважды разыменовывать указатели для каждого элемента, но как это влияет на общую производительность? Производительность значительно ухудшается, в зависимости от размера объектов и особенностей железа и софта. Если заменить в примере выше числа на маленькие объекты (12 байт), то точка «перелома» опускается до 4 вставок к одному проходу:
Управляемый код на C# сильно страдает в этом случае, потому что проход по динамическому массиву создает излишние проверки границ массива. Вектор в С++, скорее всего, будет работать эффективнее. Если быть совсем агрессивным в решении этой задачи, то можно написать более быстрый класс для динамического массива с использованием небезопасного кода C# чтобы избежать проверки границ массива. Относительная разница также будет сильно зависеть от того, как распределитель памяти и сборщик мусора управляют динамической памятью, насколько большие объекты и от других факторов. Более крупные объекты обычно улучшают производительность динамических массивов в моей среде. Когда речь идет о целых приложениях, относительная производительность динамических массивов может также улучшаться с увеличением фрагментации динамической памяти, но чтобы удостовериться, нужно проводить тестирование.
Java здесь может показать лучшие результаты, потому что она автоматически делает умные изменения маленьких объектов, или можно просто использовать отдельные массивы примитивных типов. И хотя такое писать очень нудно, это может оказаться быстрее, чем массив структур. Все зависит от особенностей обращения к данным в вашем коде. Имейте это ввиду, когда производительность особенно важна. Убедитесь, что абстракция себя оправдываетЧасто люди не согласны с такими выводами, и их аргументы— это чистота кода, корректность и поддерживаемость. Конечно, в каждой сфере есть свои приоритеты, но я считаю, что когда абстракция лишь ненамного улучшает чистоту когда, а производительность страдает сильно, нужно взять за правило выбирать производительность. Если не жалеть времени на изучение среды, то можно узнать о случаях, когда существует более быстрое и не менее чистое решение, как это часто бывает в случае с динамическими массивами вместо списков. Информация для размышления: вот семь разных способов найти сумму списка чисел в C#, со временем исполнения и использованием памяти. Везде используется арифметика с проверкой переполнения, чтобы сравнение с Linq, где метод Sum использует именно такую арифметику, было корректным. Заметьте, насколько лучший метод быстрее остальных. Заметьте, насколько затратный самый популярный способ. Заметьте, что абстракция foreach хорошо работает с массивами, но не с динамическими массивами или связными списками. Каким бы ни был ваш язык и окружение, важно понимать эти детали чтобы принимать правильные решения по умолчанию. О выборе структур данных для начинающих
Часть 1. Линейные структурыМассивКогда вам нужен один объект, вы создаёте один объект. Когда нужно несколько объектов, тогда есть несколько вариантов на выбор. Я видел, как многие новички в коде пишут что-то типа такого: Это даёт нам значение пяти рекордов. Этот способ неплохо работает, пока вам не потребуется пятьдесят или сто объектов. Вместо создания отдельных объектов можно использовать массив. Будет создан буфер из 5 элементов, вот такой:
Заметьте, что индекс массива начинается с нуля. Если в массиве пять элементов, то они будут иметь индексы от нуля до четырёх. Недостатки простого массиваЕсли вам нужно неизменное количество объектов, то массив вполне подходит. Но, допустим, вам нужно добавить в массив ещё один элемент. В простом массиве этого сделать невозможно. Допустим, вам нужно удалить элемент из массива. В простом массиве это так же невозможно. Вы привязаны к одному количеству элементов. Нам нужен массив, размер которого можно менять. Поэтому нам лучше выбрать… Динамический массивДинамический массив — это массив, который может менять свой размер. Основные языки программирования в своих стандартных библиотеках поддерживают динамические массивы. В C++ это vector. В Java это ArrayList. В C# это List. Все они являются динамическими массивами. В своей сути динамический массив — это простой массив, однако имеющий ещё два дополнительных блока данных. В них хранятся действительный размер простого массива и объём данных, который может на самом деле храниться в простом массиве. Динамический массив может выглядеть примерно так: Элемент internalArray указывает на динамически размещаемый буфер. Действительный массив буфера хранится в maxCapacity. Количество использовуемых элементов задаётся currentLength. |
