Javascript 数组是稀疏的吗？

发布于 2024-08-06 01:00:40 字数 359 浏览 3 评论 0原文

也就是说，如果我使用当前时间作为数组的索引：

array[Date.getTime()] = value;

解释器会实例化从 0 到现在的所有元素吗？不同的浏览器有不同的做法吗？

我记得 AIX 内核中曾经有一个错误，会根据请求创建伪 tty，但如果你这样做了，比如“echo > /dev/pty10000000000”，它将创建 /dev/pty0、/dev/pty1，....，然后倒地而死。贸易展览很有趣，但我不希望这种情况发生在我的客户身上。

原文

That is, if I use the current time as an index into the array:

array[Date.getTime()] = value;

will the interpreter instantiate all the elements from 0 to now? Do different browsers do it differently?

I remember there used to be a bug in the AIX kernel, which would create pseudo-ttys on request, but if you did, say, "echo > /dev/pty10000000000" it would create /dev/pty0, /dev/pty1, .... and then fall over dead. It was fun at trade shows, but I don't want this to happen to my customers.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

睡美人的小仙女 2024-08-13 01:00:40

是的，他们是。它们实际上是内部哈希表，因此您不仅可以使用大整数，还可以使用字符串、浮点数或其他对象。所有键在添加到哈希之前都会通过 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) 风格的迭代，那么您显然会遇到非标准数组索引的问题。

Yes, they are. They are actually hash tables internally, so you can use not only large integers but also strings, floats, or other objects. All keys get converted to strings via toString() before being added to the hash. You can confirm this with some test code:

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

Displays:

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

Notice how I used for...in syntax, which only gives you the indices that are actually defined. If you use the more common for (var i = 0; i < array.length; ++i) style of iteration then you will obviously have problems with non-standard array indices.

回复收藏 0 原文

心的位置 2024-08-13 01:00:40

JavaScript 数组的具体实现方式因浏览器而异，但如果使用实际数组效率低下，它们通常会回退到稀疏实现（很可能与用于常规对象的属性访问的实现相同）。

您必须询问对特定实现有更多了解的人来回答到底是什么触发了从密集到稀疏的转变，但您的示例应该是完全安全的。如果您想获得一个密集数组，您应该使用显式长度参数调用构造函数，并希望您实际上能获得一个。

请参阅此答案了解更多信息olliej 的详细描述。

回复收藏 0 原文

青柠芒果 2024-08-13 01:00:40

您可以通过使用专为此类事情设计的 JavaScript 语法来避免此问题。您可以将其视为字典，但“for ... in ...”语法将让您抓住所有它们。

var sparse = {}; // not []
sparse["whatever"] = "something";

You could avoid the issue by using a javascript syntax designed for this sort of thing. You can treat it as a dictionary, yet the "for ... in ... " syntax will let you grab them all.

var sparse = {}; // not []
sparse["whatever"] = "something";

回复收藏 0 原文

世界等同你 2024-08-13 01:00:40

JavaScript 对象是稀疏的，数组只是具有自动维护的 length 属性（实际上比最大索引大 1，而不是定义的元素数量）和一些附加方法的特殊对象。不管怎样你都是安全的；如果需要额外的功能，请使用数组，否则使用对象。

回复收藏 0 原文

初心未许 2024-08-13 01:00:40

正如 JavaScript 中通常的情况一样，答案是“它有点奇怪……”

内存使用没有定义，任何实现都可以是愚蠢的。理论上，const a = []; a[1000000]=0; 可能会消耗兆字节的内存，const a = []; 也可能如此。在实践中，甚至微软也避免了这些实现。

Justin Love 指出，长度属性是最高索引集。但只有当索引是整数时才会更新。

所以，数组是稀疏的。但是像reduce()、Math.max()和“for ... of”这样的内置函数将遍历从0到长度的整个可能的整数索引范围，访问许多返回“未定义”的函数。但是“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

但是。还有更多数组的极端情况尚未提及。

The answer, as is usually true with JavaScript, is "it's a bit wierder...."

Memory usage is not defined and any implementation is allowed to be stupid. In theory, const a = []; a[1000000]=0; could burn megabytes of memory, as could const a = [];. In practice, even Microsoft avoids those implementations.

Justin Love points out, the length attribute is the highest index set. BUT its only updated if the index is an integer.

So, the array is sparse. BUT built-in functions like reduce(), Math.max(), and "for ... of" will walk through the entire range of possible integer indices form 0 to the length, visiting many that return 'undefined'. BUT 'for ... in' loops might do as you expect, visiting only the defined keys.

Here's an example using 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]}`);

giving:

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

But. There are more corner cases with Arrays not yet mentioned.

回复收藏 0 原文

忘羡 2024-08-13 01:00:40

NodeJS 的稀疏性（或密集性）可以通过非标准 process.memoryUsage()< /a>.

有时节点足够聪明，可以保持数组稀疏：

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

有时节点选择使其密集（这种行为将来可能会得到优化）：

> 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 内核错误可能会需要用 range-alike 来强制：

> 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

Sparseness (or denseness) can be confirmed empirically for NodeJS with the non-standard process.memoryUsage().

Sometimes node is clever enough to keep the array sparse:

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

Sometimes node chooses to make it dense (this behavior might well be optimized in future):

> 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

Then sparse again:

> 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

So perhaps using a dense array to get a feel for the original AIX kernel bug might need to be forced with a range-alike:

> 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

Because why not make it fall over?

> 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

回复收藏 0 原文

就此别过 2024-08-13 01:00:40

他们可以，但并不总是必须如此，当他们不这样做时，他们可以表现得更好。

以下是有关如何测试数组实例中索引稀疏性的讨论：
https://benmccormick.org/2018/06/19/code -golf-sparse-arrays/

此代码高尔夫（最少字符）获胜者是：

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

基本上遍历索引条目的数组，同时递减长度值并返回假值的硬化 !! 布尔值/truthy 数值结果（如果累加器一直递减至零，则索引已完全填充且不稀疏）。 Charles Merriam 的上述警告也应予以考虑，此代码并未解决这些问题，但它们适用于散列字符串条目，当使用 arr[var]= (something) 分配元素（其中 var 不是整数）时可能会发生这种情况。

关心索引稀疏性的原因是它对性能的影响，这在脚本引擎之间可能有所不同，这里有关于数组创建/初始化的精彩讨论：
“Array() 和“Array()”之间有什么区别" 和 "[]" 在声明 JavaScript 数组时？

该帖子的最新答案提供了一个链接，可深入探讨 V8 如何通过标记数组来优化数组，以避免（重新）测试稀疏性等特征：https://v8.dev/blog/elements-kinds。该博文发表于 2017 年 9 月，内容可能会发生一些变化，但对日常开发的影响的细分是有用且清晰的。

They can be but they don't always have to be, and they can perform better when they're not.

Here's a discussion about how to test for index sparseness in an array instance:
https://benmccormick.org/2018/06/19/code-golf-sparse-arrays/

This code golf (fewest characters) winner is:

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

Basically walking the array for indexed entries while decrementing the length value and returning the hardened !! boolean of the falsy/truthy numerical result (if the accumulator is decremented all the way to zero, the index is fully populated and not sparse). Charles Merriam's caveats above should be considered as well and this code doesn't address them, but they apply to hashed string entries which can happen when assigning elements with arr[var]= (something) where var wasn't an integer.

On reason to care about index sparseness is its effects on performance, which can differ between script engines, there's a great discussion about array creation/.initialization here:
What’s the difference between "Array()" and "[]" while declaring a JavaScript array?

A recent answer to that post has a link to this deep dive into how V8 tries to optimize arrays by tagging them to avoid (re-)testing for characteristics like sparseness: https://v8.dev/blog/elements-kinds. The blog post is from Sept '17 and the material is subject to some change, but the breakdown to implications for day-to-day development is useful and clear.

回复收藏 0 原文

~没有更多了~