Являются ли массивы JavaScript на самом деле связанными списками?

Question

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

Разве это не проблема в JavaScript? Если да, то есть ли структура списка?

Answer 1

Скорее всего, это зависит от того, какой движок JavaScript вы используете.

Internet Explorer использует сочетание разреженных и плотных массивов для этой работы.Некоторые из более кровавых деталей объясняются здесь: http://blogs.msdn.com/b/jscript/archive/2008/04/08/performance-optimization-of-arrays-part-ii.aspx.

Answer 2

Массивы Javascript обычно реализуются в виде хэш-карт (как и объекты Javascript) с одной добавленной функцией: существует атрибут length, который на единицу выше, чем наибольшее положительное целое число, которое использовалось в качестве ключа. Ничто не мешает вам также , используя в качестве ключей строки, числа с плавающей точкой и даже отрицательные числа. Ничего, кроме здравого смысла.

Answer 3

Дело в динамических языках в том, что они динамические.Как и ArrayList в Java, или массивы в Perl, PHP и Python, Array в JavaScript будет выделять определенный объем памяти, а когда он становится слишком большим, язык автоматически добавляется к объекту.Это так же эффективно, как C ++ или даже Java?Нет (C ++ может обойти даже самые лучшие реализации JS), но люди не собирают Quake в JS (только пока).

На самом деле лучше думать о них как о HashMaps с некоторыми специализированными методами.в любом случае - в конце концов, это действительно так: var a = []; a['cat']='meow';.

Answer 4

Нет.

Что такое массивы JavaScript, а какие нет, определяется спецификацией языка, в частности, раздел 15.4 .Array определяется в терминах операций, которые он не предоставляет подробности реализации макета памяти какой-либо конкретной структуры данных.

Может ли Array быть реализован поверх связанного списка?Да.Это может ускорить выполнение некоторых операций, таких как shift и unshift, но индекс 1011 * также часто доступен по индексу, который неэффективен для связанных списков.

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

На практике большинство интерпретаторов оптимизируют плотные массивы, используя структуру данных, основанную наизменяемый или перераспределяемый массив, похожий на C ++ vector или Java ArrayList.

Answer 5

На самом деле они больше похожи на пользовательские объекты, которые используют свойства в качестве индексов. Пример:

var a = { "1": 1, "2": 2};
a.length = 2;
for(var i=0;i<a.length;i++)
    console.log(a[i]);

a будет вести себя почти как массив, и вы также можете вызывать функции из Array.prototype для него.

Answer 6

Массивы Javascript не являются настоящими массивами, как в C / C ++ или других языках. Следовательно, они не так эффективны, но, возможно, их проще использовать и они не исключают исключений.