Les tableaux Javascript sont-ils rares?

97

Autrement dit, si j'utilise l'heure actuelle comme index dans le tableau:

array[Date.getTime()] = value;

l'interpréteur instanciera-t-il tous les éléments de 0 à maintenant? Les différents navigateurs le font-ils différemment?

Je me souviens qu'il y avait un bogue dans le noyau AIX , qui créait des pseudo-ttys sur demande, mais si vous faisiez, disons, "echo> / dev / pty10000000000" il créerait / dev / pty0, / dev / pty1, .... puis tomber mort. C'était amusant lors des salons, mais je ne veux pas que cela arrive à mes clients.

Baie
la source
1
Un inconvénient possible à faire cela est la difficulté de débogage dans Firebug. une instruction de journal sur le tableau ne listera que les 1000 premiers éléments du tableau, qui seront tous "indéfinis". En outre, array.length vous dira que votre tableau contient n éléments, même si n-1 ne sont que des valeurs non définies "fantômes".
Michael Butler
Le débogage est maintenant OK dans Chrome - voici un exemple de sortie de console: [vide × 9564, Object, vide × 105, Object, vide × 10, Object, vide × 12, Object, vide × 9, Object, vide × 21, Objet, vide × 9, Objet]
jsalvata

Réponses:

40

La manière exacte dont les tableaux JavaScript sont implémentés diffère d'un navigateur à l'autre, mais ils reviennent généralement à une implémentation clairsemée - probablement la même que celle utilisée pour l'accès aux propriétés des objets normaux - si l'utilisation d'un tableau réel serait inefficace.

Vous devrez demander à quelqu'un ayant plus de connaissances sur les implémentations spécifiques de répondre à ce qui déclenche le passage de dense à clairsemé, mais votre exemple doit être parfaitement sûr. Si vous voulez obtenir un tableau dense, vous devez appeler le constructeur avec un argument de longueur explicite et espérer que vous en aurez un.

Voir cette réponse pour une description plus détaillée par olliej.

Christoph
la source
1
Je ne pense pas que vous obtenez un tableau dense si vous dites quelque chose comme foo = new Array(10000). Toutefois, cela est censé fonctionner: foo = Array.apply(null, {length: 10});.
doubleOrt
70

Oui, ils sont. Ce sont en fait des tables de hachage en interne, vous pouvez donc utiliser non seulement de grands entiers, mais également des chaînes, des flottants ou d'autres objets. Toutes les clés sont converties en chaînes via toString()avant d'être ajoutées au hachage. Vous pouvez le confirmer avec un code de test:

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

Affiche:

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

Remarquez comment j'ai utilisé la for...insyntaxe, qui ne vous donne que les indices réellement définis. Si vous utilisez le for (var i = 0; i < array.length; ++i)style d'itération le plus courant , vous aurez évidemment des problèmes avec les index de tableau non standard.

John Kugelman
la source
9
la plupart des implémentations JS stockent les propriétés indexées numériquement dans un tableau réel si possible; c'est de la magie dans les coulisses, cependant: du point de vue du langage, les tableaux sont des objets réguliers avec une lengthpropriété magique
Christoph
7
@John: lengthn'est invisible que dans les for..inboucles car il a le DontEnumdrapeau défini; dans ES5, l'attribut de propriété est appelé enumerableet peut être défini explicitement viaObject.defineProperty()
Christoph
14
Toutes les clés d'objet en JavaScript sont toujours String; tout ce que vous mettez en indice est toString()validé. Combinez cela avec l'imprécision entière d'un grand nombre et cela signifie que si vous définissez a[9999999999999999]=1, a[10000000000000000]sera 1 (et bien d'autres comportements surprenants). L'utilisation de non-entiers comme clés est très imprudente et les objets arbitraires sont tout à fait appropriés.
bobince
71
Alors tu n'utiliseras que des chaînes comme clés d'objet, ni plus, ni moins. String sera le type que vous utiliserez et le type de la clé sera String. Vous n'utiliserez pas d'entier, ni n'utiliserez des non-entiers, sauf que vous procéderez ensuite à la conversion en String. Les objets arbitraires sont tout à fait sortis.
Crescent Fresh
8
Les index de tableau doivent être des entiers. array [3.14] = pi fonctionne car Array est inhérent à Object. Exemple: var x = []; x [.1] = 5; Alors x a encore une longueur de 0.
Mike Blandford
10

Vous pouvez éviter le problème en utilisant une syntaxe javascript conçue pour ce genre de chose. Vous pouvez le traiter comme un dictionnaire, mais la syntaxe "for ... in ..." vous permettra de les saisir tous.

var sparse = {}; // not []
sparse["whatever"] = "something";
John Fisher
la source
7

Les objets Javascript sont rares et les tableaux ne sont que des objets spécialisés avec une propriété de longueur auto-maintenue (qui est en fait un plus grand que le plus grand index, pas le nombre d'éléments définis) et quelques méthodes supplémentaires. Vous êtes en sécurité de toute façon; utilisez un tableau si vous avez besoin de fonctionnalités supplémentaires, et un objet dans le cas contraire.

Juste amoureux
la source
4
c'est du point de vue de la langue; les implémentations utilisent en fait de vrais tableaux pour stocker des propriétés numériques denses
Christoph
6

La réponse, comme c'est généralement le cas avec JavaScript, est "c'est un peu plus bizarre ..."

L'utilisation de la mémoire n'est pas définie et toute implémentation est autorisée à être stupide. En théorie, const a = []; a[1000000]=0;pourrait brûler des mégaoctets de mémoire, tout commeconst a = []; . En pratique, même Microsoft évite ces implémentations.

Justin Love souligne que l'attribut de longueur est le plus élevé ensemble d'indices élevé. MAIS il n'est mis à jour que si l'index est un entier.

Ainsi, le tableau est clairsemé. MAIS les fonctions intégrées telles que reduction (), Math.max () et "for ... of" parcourront toute la gamme d'indices entiers possibles de 0 à la longueur, visitant beaucoup qui retournent 'indéfini'. MAIS les boucles 'for ... in' peuvent faire ce que vous attendez, en visitant uniquement les clés définies.

Voici un exemple utilisant 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]}`);

donnant:

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

Mais. Il y a plus de cas de coin avec des tableaux non encore mentionnés.

Charles Merriam
la source
2

La parcimonie (ou densité) peut être confirmée empiriquement pour NodeJS avec le process.memoryUsage () non standard .

Parfois, le nœud est assez intelligent pour garder le tableau clairsemé:

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

Parfois, le nœud choisit de le rendre dense (ce comportement pourrait bien être optimisé à l'avenir):

> 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

Puis à nouveau clairsemé:

> 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

Donc, peut-être que l'utilisation d'un tableau dense pour avoir une idée du bogue original du noyau AIX devra peut-être être forcée avec une plage similaire :

> 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

Parce que pourquoi ne pas le faire tomber?

> 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
la source
1
Bien, et je suis un peu étonné que ma question vieille de dix ans soit toujours d'actualité!
Berry le
1

Ils peuvent l'être, mais ils ne doivent pas toujours l'être, et ils peuvent mieux fonctionner lorsqu'ils ne le sont pas.

Voici une discussion sur la façon de tester la parcimonie d'index dans une instance de tableau: https://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

Ce gagnant de code golf (le moins de caractères) est:

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

En gros, parcourir le tableau pour les entrées indexées tout en décrémentant la valeur de longueur et en renvoyant le !!booléen renforcé du résultat numérique faux / véridique (si l'accumulateur est décrémenté jusqu'à zéro, l'index est entièrement rempli et non fragmenté). Les mises en garde de Charles Merriam ci-dessus doivent également être prises en compte et ce code ne les aborde pas, mais elles s'appliquent aux entrées de chaîne hachée, ce qui peut se produire lors de l'affectation d'éléments avec arr[var]= (something)où var n'était pas un entier.

Si vous vous souciez de la rareté des index, ce sont ses effets sur les performances, qui peuvent différer entre les moteurs de script, il y a une grande discussion sur la création / initialisation de tableau ici: Quelle est la différence entre "Array ()" et "[]" lors de la déclaration d'un JavaScript tableau?

Une réponse récente à cet article a un lien vers cette plongée approfondie sur la façon dont V8 tente d'optimiser les tableaux en les étiquetant pour éviter de (re) tester des caractéristiques telles que la parcimonie: https://v8.dev/blog/elements-kinds . Le billet de blog date du 17 septembre et le matériel est sujet à certains changements, mais la ventilation des implications pour le développement quotidien est utile et claire.

dkloke
la source