Czy tablice Javascript są rzadkie?

97

To znaczy, jeśli użyję bieżącego czasu jako indeksu do tablicy:

array[Date.getTime()] = value;

czy interpreter utworzy instancję wszystkich elementów od 0 do teraz? Czy różne przeglądarki robią to inaczej?

Pamiętam, że kiedyś był błąd w jądrze AIX , który tworzył pseudo-ttys na żądanie, ale gdybyś zrobił, powiedzmy, "echo> / dev / pty10000000000", utworzyłby / dev / pty0, / dev / pty1, .... a potem padnij martwy. Było fajnie na targach, ale nie chcę, żeby przytrafiło się to moim klientom.

javascript sparse-matrix Jagoda
źródło
1
Możliwą wadą tego rozwiązania jest trudność debugowania w Firebug. instrukcja log w tablicy wyświetli tylko pierwsze 1000 elementów w tablicy, z których wszystkie będą „niezdefiniowane”. Ponadto array.length powie ci, że twoja tablica ma w sobie n elementów, mimo że n-1 to tylko niezdefiniowane wartości "widma".
Michael Butler
Debugowanie jest teraz OK w Chrome - oto przykład wyjścia konsoli: [puste × 9564, Obiekt, puste × 105, Obiekt, puste × 10, Obiekt, puste × 12, Obiekt, puste × 9, Obiekt, puste × 21, Obiekt, pusty × 9, Obiekt]
jsalvata

Odpowiedzi:

40

Sposób implementacji tablic JavaScript różni się w zależności od przeglądarki, ale generalnie sprowadzają się do rzadkiej implementacji - najprawdopodobniej tej samej, która jest używana do dostępu do właściwości zwykłych obiektów - jeśli użycie rzeczywistej tablicy byłoby nieefektywne.

Będziesz musiał poprosić kogoś, kto ma większą wiedzę na temat konkretnych implementacji, aby odpowiedział, co dokładnie wyzwala przejście z gęstej na rzadką, ale twój przykład powinien być całkowicie bezpieczny. Jeśli chcesz uzyskać gęstą tablicę, powinieneś wywołać konstruktor z jawnym argumentem długości i mieć nadzieję, że faktycznie go otrzymasz.

Zobacz tę odpowiedź, aby uzyskać bardziej szczegółowy opis autorstwa olliej.

Christoph
źródło
1
Nie sądzę, żebyś faktycznie miał gęstą tablicę, jeśli powiesz coś takiego foo = new Array(10000). Jednak to ma pracę: foo = Array.apply(null, {length: 10});.
doubleOrt
70

Tak, oni są. W rzeczywistości są wewnętrznie tablicami mieszającymi, więc możesz używać nie tylko dużych liczb całkowitych, ale także łańcuchów, liczb zmiennoprzecinkowych i innych obiektów. Wszystkie klucze są konwertowane na ciągi znaków przez toString()przed dodaniem do skrótu. Możesz to potwierdzić za pomocą kodu testowego:

<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>

Wyświetlacze:

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

Zwróć uwagę, jak użyłem for...inskładni, która podaje tylko te indeksy, które są faktycznie zdefiniowane. Jeśli używasz bardziej powszechnego for (var i = 0; i < array.length; ++i)stylu iteracji, będziesz oczywiście miał problemy z niestandardowymi indeksami tablicowymi.

John Kugelman
źródło
9
większość implementacji JS przechowuje właściwości indeksowane numerycznie w rzeczywistej tablicy, jeśli to możliwe; to jednak zakulisowa magia: z językowego punktu widzenia tablice to zwykłe obiekty z magiczną lengthwłaściwością
Christoph
7
@John: lengthjest niewidoczny tylko w for..inpętlach, ponieważ ma DontEnumustawioną flagę; w ES5 atrybut property jest wywoływany enumerablei można go jawnie ustawić za pośrednictwemObject.defineProperty()
Christoph
14
Wszystkie klucze obiektów w JavaScript są zawsze String; wszystko inne, co umieścisz w indeksie dolnym, zostanie toString()-ed. Połącz to z nieprecyzyjną liczbą całkowitą dużej liczby i oznacza to, że jeśli ustawisz a[9999999999999999]=1, a[10000000000000000]będzie 1 (i wiele innych zaskakujących zachowań). Używanie liczb niecałkowitych jako kluczy jest bardzo nierozsądne, a dowolne obiekty są natychmiastowe.
bobince
72
Wtedy będziesz używać tylko łańcuchów jako kluczy obiektów, nie więcej, nie mniej. String będzie typem, którego będziesz używać, a typem klucza będzie String. Nie powinieneś używać liczb całkowitych ani nie-całkowitych, z wyjątkiem tego, że następnie przejdziesz do rzutowania na String. Arbitralne obiekty są na wyciągnięcie ręki.
Crescent Fresh
8
Indeksy tablic muszą być liczbami całkowitymi. array [3.14] = pi działa, ponieważ Array dziedziczy z Object. Przykład: var x = []; x [.1] = 5; Wtedy x nadal ma długość 0.
Mike Blandford
10

Możesz uniknąć tego problemu, używając składni javascript zaprojektowanej do tego typu rzeczy. Możesz traktować go jak słownik, ale składnia „for ... in…” pozwoli ci je wszystkie pobrać.

var sparse = {}; // not []
sparse["whatever"] = "something";
John Fisher
źródło
7

Obiekty JavaScript są rzadkie, a tablice to tylko wyspecjalizowane obiekty z automatycznie utrzymywaną właściwością length (która jest w rzeczywistości o jeden większa niż największy indeks, a nie liczba zdefiniowanych elementów) i kilkoma dodatkowymi metodami. Tak czy inaczej jesteś bezpieczny; użyj tablicy, jeśli potrzebujesz jej dodatkowych funkcji, lub obiektu w przeciwnym razie.

Po prostu zakochany
źródło
4
to z językowego punktu widzenia; implementacje używają rzeczywistych tablic do przechowywania gęstych właściwości numerycznych
Christoph
6

Odpowiedź, jak zwykle w przypadku JavaScript, brzmi „to trochę dziwniejsze ...”

Użycie pamięci nie jest zdefiniowane i każda implementacja może być głupia. Teoretycznie const a = []; a[1000000]=0;mógłby spalić megabajty pamięci, tak jak mógłbyconst a = []; . W praktyce nawet Microsoft unika tych implementacji.

Justin Love zwraca uwagę, że atrybut długości jest najwyższy zestaw indeksów. ALE jest aktualizowany tylko wtedy, gdy indeks jest liczbą całkowitą.

Tak więc tablica jest rzadka. ALE wbudowane funkcje, takie jak redukuj (), Math.max () i „for ... of”, przechodzą przez cały zakres możliwych indeksów całkowitych od 0 do długości, odwiedzając wiele zwracających „undefined”. ALE pętle 'for ... in' mogą działać zgodnie z oczekiwaniami, odwiedzając tylko zdefiniowane klucze.

Oto przykład wykorzystujący 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]}`);

dający:

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

Ale. Jest więcej przypadków narożnych z tablicami, o których jeszcze nie wspomniano.

Charles Merriam
źródło
2

Rzadkość (lub gęstość) można potwierdzić empirycznie dla NodeJS za pomocą niestandardowego procesu. PamięćUsage () .

Czasami węzeł jest na tyle sprytny, że tablica jest rzadka:

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

Czasami node decyduje się na zagęszczenie (to zachowanie może być zoptymalizowane w przyszłości):

> 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

Następnie ponownie rzadkie:

> 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

Być może więc użycie gęstej tablicy, aby wyczuć błąd oryginalnego jądra AIX, może wymagać wymuszenia podobnego zakresu :

> 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

Bo dlaczego nie sprawić, by się przewróciło?

> 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
źródło
1
Fajnie i jestem trochę zdumiony, że moje 10-letnie pytanie jest nadal aktualne!
Berry
1

Mogą, ale nie zawsze muszą, i mogą osiągać lepsze wyniki, gdy nie są.

Oto dyskusja na temat testowania rzadkości indeksów w instancji tablicy: https://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

Zwycięzcą tego kodu golfa (najmniej znaków) jest:

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

Zasadniczo chodzenie po tablicy indeksowanych wpisów przy jednoczesnym zmniejszaniu wartości długości i zwracaniu wzmocnionej wartości !!logicznej fałszywego / prawdziwego wyniku liczbowego (jeśli akumulator jest zmniejszony do zera, indeks jest w pełni zapełniony i nie jest rzadki). Należy również wziąć pod uwagę powyższe zastrzeżenia Charlesa Merriama, a ten kod ich nie rozwiązuje, ale odnoszą się do haszowanych wpisów łańcuchowych, co może się zdarzyć podczas przypisywania elementów, w arr[var]= (something)których zmienna nie była liczbą całkowitą.

Powodem, dla którego warto przejmować się rzadkością indeksów, jest jego wpływ na wydajność, który może różnić się w zależności od silnika skryptowego. Tutaj znajduje się obszerna dyskusja na temat tworzenia / inicjalizacji tablic: Jaka jest różnica między „Array ()” a „[]” podczas deklarowania kodu JavaScript szyk?

Niedawna odpowiedź na ten post zawiera link do tego dogłębnego zagłębienia się w to, jak V8 próbuje zoptymalizować tablice, oznaczając je, aby uniknąć (ponownego) testowania pod kątem cech takich jak rzadkość: https://v8.dev/blog/elements-kinds . Wpis na blogu pochodzi z września 2017 r., A materiał może ulec pewnym zmianom, ale zestawienie implikacji dla codziennego rozwoju jest przydatne i jasne.

dkloke
źródło