Массивы Javascript разрежены?

97

То есть, если я использую текущее время в качестве индекса в массиве:

array[Date.getTime()] = value;

будет ли интерпретатор создавать экземпляры всех элементов от 0 до настоящего момента? Разные браузеры делают это по-разному?

Я помню, что раньше была ошибка в ядре AIX , которая создавала псевдо-tty по запросу, но если вы скажете «echo> / dev / pty10000000000», он создаст / dev / pty0, / dev / pty1, .... а затем упасть замертво. На выставках было весело, но я не хочу, чтобы это случилось с моими покупателями.

javascript sparse-matrix Ягода
источник
1
Возможный недостаток этого - сложность отладки в Firebug. оператор журнала в массиве перечислит только первые 1000 элементов в массиве, которые все будут «неопределенными». Кроме того, array.length сообщит вам, что в вашем массиве есть n элементов, хотя n-1 - просто «призрачные» неопределенные значения.
Майкл Батлер
Отладка теперь в Chrome в порядке - вот пример вывода консоли: [пустой × 9564, Объект, пустой × 105, Объект, пустой × 10, Объект, пустой × 12, Объект, пустой × 9, Объект, пустой × 21, Object, empty × 9, Object]
jsalvata 09

Ответы:

40

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

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

См. Этот ответ для более подробного описания от olliej.

Кристоф
источник
1
Я не думаю, что вы действительно получите плотный массив, если скажете что-то вроде foo = new Array(10000). Однако, это должно работать: foo = Array.apply(null, {length: 10});.
doubleOrt
70

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

<script>
  var array = [];
  array[0] = "zero";
  array[new Date().getTime()] = "now";
  array[3.14] = "pi";

  for (var i in array) {
      alert("array["+i+"] = " + array[i] + ", typeof("+i+") == " + typeof(i));
  }
</script>

Отображает:

array[0] = zero, typeof(0) == string
array[1254503972355] = now, typeof(1254503972355) == string
array[3.14] = pi, typeof(3.14) == string

Обратите внимание, как я использовал for...inсинтаксис, который дает вам только фактически определенные индексы. Если вы используете более распространенный for (var i = 0; i < array.length; ++i)стиль итерации, у вас, очевидно, возникнут проблемы с нестандартными индексами массива.

Джон Кугельман
источник
9
большинство реализаций JS по возможности сохраняют свойства с числовой индексацией в реальном массиве; это закулисная магия: с точки зрения языка, массивы - это обычные объекты с магическим lengthсвойством
Кристоф
7
@John: lengthневидим только в for..inциклах, потому что у него установлен DontEnumфлаг; в ES5 атрибут свойства вызывается enumerableи может быть явно установлен черезObject.defineProperty()
Christoph
14
Все ключи объекта в JavaScript всегда String; все, что вы добавляете в нижний индекс, получает toString()-ed. Объедините это с неточностью целого числа большого числа, и это означает, что если вы установите a[9999999999999999]=1, a[10000000000000000]будет 1 (и многие другие удивительные поведения). Использование нецелых чисел в качестве ключей очень неразумно, а произвольные объекты не подходят.
bob со
72
Тогда ты должен использовать только строки в качестве ключей объекта, ни больше, ни меньше. String должен быть того типа, который вы должны использовать, а тип ключа должен быть String. Целое число не следует использовать, равно как и не целые числа, за исключением того, что вы затем переходите к приведению к String. Произвольные объекты тут же.
Crescent Fresh
8
Индексы массивов должны быть целыми числами. array [3.14] = pi работает, потому что Array наследуется от Object. Пример: var x = []; x [.1] = 5; Тогда длина x по-прежнему равна 0.
Майк Бландфорд,
10

Вы можете избежать этой проблемы, используя синтаксис javascript, предназначенный для такого рода вещей. Вы можете рассматривать его как словарь, но синтаксис «for ... in ...» позволит вам получить их все.

var sparse = {}; // not []
sparse["whatever"] = "something";
Джон Фишер
источник
7

Объекты Javascript разрежены, а массивы - это просто специализированные объекты с автоматически поддерживаемым свойством длины (которое на самом деле на единицу больше, чем наибольший индекс, а не количество определенных элементов) и некоторыми дополнительными методами. В любом случае вы в безопасности; используйте массив, если вам нужны дополнительные функции, и объект в противном случае.

Только в любви
источник
4
это с языковой точки зрения; реализации на самом деле используют реальные массивы для хранения плотных числовых свойств
Кристоф
6

Ответ, как это обычно бывает с JavaScript, - «это немного сложнее ....»

Использование памяти не определено, и любая реализация может быть глупой. По идее const a = []; a[1000000]=0;мог бы сжечь мегабайты памяти, как мог const a = [];. На практике даже Microsoft избегает таких реализаций.

Джастин Лав указывает, что атрибут длины - это самый высокий индексный набор. НО он обновляется только в том случае, если индекс является целым числом.

Итак, массив разреженный. НО встроенные функции, такие как reduce (), Math.max () и "for ... of", будут проходить через весь диапазон возможных целочисленных индексов от 0 до длины, посещая многие из них, которые возвращают undefined. НО циклы for ... in могут работать так, как вы ожидаете, посещая только определенные ключи.

Вот пример использования Node.js:

"use strict";
const print = console.log;

let a = [0, 10];
// a[2] and a[3] skipped
a[4] = 40;
a[5] = undefined;  // which counts towards setting the length
a[31.4] = 'ten pi';  // doesn't count towards setting the length
a['pi'] = 3.14;
print(`a.length= :${a.length}:, a = :${a}:`);
print(`Math.max(...a) = :${Math.max(a)}: because of 'undefined values'`);
for (let v of a) print(`v of a; v=:${v}:`);
for (let i in a) print(`i in a; i=:${i}: a[i]=${a[i]}`);

давая:

a.length= :6:, a = :0,10,,,40,:
Math.max(...a) = :NaN: because of 'undefined values'
v of a; v=:0:
v of a; v=:10:
v of a; v=:undefined:
v of a; v=:undefined:
v of a; v=:40:
v of a; v=:undefined:
i in a; i=:0: a[i]=0
i in a; i=:1: a[i]=10
i in a; i=:4: a[i]=40
i in a; i=:5: a[i]=undefined
i in a; i=:31.4: a[i]=ten pi
i in a; i=:pi: a[i]=3.14

Но. Есть еще не упомянутые еще случаи с массивами.

Чарльз Мерриам
источник
2

Редкость (или плотность) для NodeJS можно подтвердить эмпирически с помощью нестандартного метода process.memoryUsage () .

Иногда узел достаточно умен, чтобы сохранить разреженный массив:

Welcome to Node.js v12.15.0.
Type ".help" for more information.
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 3.07 MB
undefined
> array = []
[]
> array[2**24] = 2**24
16777216
> array
[ <16777216 empty items>, 16777216 ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 2.8 MB
undefined

Иногда node решает сделать его плотным (это поведение вполне может быть оптимизировано в будущем):

> otherArray = Array(2**24)
[ <16777216 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.57 MB
undefined

Затем снова разреженный:

> yetAnotherArray = Array(2**32-1)
[ <4294967295 empty items> ]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`)
The script is using approximately 130.68 MB
undefined

Поэтому, возможно, использование плотного массива, чтобы почувствовать исходную ошибку ядра AIX, может потребоваться принудительно с подобным диапазоном :

> denseArray = [...Array(2**24).keys()]
[
   0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11,
  12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
  24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
  36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
  48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
  72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
  84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
  96, 97, 98, 99,
  ... 16777116 more items
]
> console.log(`The script is using approximately ${Math.round(process.memoryUsage().heapUsed / 1024 / 1024 * 100) / 100} MB`);
The script is using approximately 819.94 MB
undefined

Почему бы не заставить его упасть?

> tooDenseArray = [...Array(2**32-1).keys()]

<--- Last few GCs --->

[60109:0x1028ca000]   171407 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 
[60109:0x1028ca000]   171420 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 
[60109:0x1028ca000]   171434 ms: Scavenge 1072.7 (1090.0) -> 1056.7 (1090.0) MB, 0.2 / 0.0 ms  (average mu = 0.968, current mu = 0.832) allocation failure 


<--- JS stacktrace --->

==== JS stack trace =========================================

    0: ExitFrame [pc: 0x100931399]
    1: StubFrame [pc: 0x1008ee227]
    2: StubFrame [pc: 0x100996051]
Security context: 0x1043830808a1 <JSObject>
    3: /* anonymous */ [0x1043830b6919] [repl:1] [bytecode=0x1043830b6841 offset=28](this=0x104306fc2261 <JSGlobal Object>)
    4: InternalFrame [pc: 0x1008aefdd]
    5: EntryFrame [pc: 0x1008aedb8]
    6: builtin exit frame: runInThisContext(this=0x104387b8cac1 <ContextifyScript map = 0x1043...

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

Writing Node.js report to file: report.20200220.220620.60109.0.001.json
Node.js report completed
 1: 0x10007f4b9 node::Abort() [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 2: 0x10007f63d node::OnFatalError(char const*, char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 3: 0x100176a27 v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 4: 0x1001769c3 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 5: 0x1002fab75 v8::internal::Heap::FatalProcessOutOfMemory(char const*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 6: 0x1005f3e9b v8::internal::Runtime_FatalProcessOutOfMemoryInvalidArrayLength(int, unsigned long*, v8::internal::Isolate*) [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 7: 0x100931399 Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
 8: 0x1008ee227 Builtins_IterableToList [/Users/pzrq/.nvm/versions/node/v12.15.0/bin/node]
Abort trap: 6
pzrq
источник
1
Хорошо, и я немного удивлен, что мой вопрос десятилетней давности все еще актуален!
Берри
1

Они могут быть, но не всегда, и они могут работать лучше, когда это не так.

Вот обсуждение того, как проверить разреженность индекса в экземпляре массива: https://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

Этот код победителя гольфа (наименьшее количество символов):

let isSparse = a => !!a.reduce(x=>x-1,a.length)

По !!сути, обход массива для индексированных записей с уменьшением значения длины и возвращением усиленного логического значения ложного / правдивого числового результата (если аккумулятор полностью уменьшен до нуля, индекс полностью заполнен, а не разрежен). Вышеупомянутые предостережения Чарльза Мерриама также следует учитывать, и этот код не обращается к ним, но они применяются к хешированным строковым записям, что может произойти при назначении элементов, arr[var]= (something)где var не является целым числом.

Причина, по которой нужно заботиться о разреженности индекса, заключается в его влиянии на производительность, которое может различаться для разных скриптовых движков, здесь большое обсуждение создания / инициализации массива: В чем разница между «Array ()» и «[]» при объявлении JavaScript массив?

В недавнем ответе на этот пост есть ссылка на подробное описание того, как V8 пытается оптимизировать массивы, помечая их, чтобы избежать (повторного) тестирования на такие характеристики, как разреженность: https://v8.dev/blog/elements-kinds . Сообщение в блоге от сентября 2017 года, и в него могут быть внесены некоторые изменения, но разбивка по значениям для повседневной разработки полезна и понятна.

Dkloke
источник