JavaScript：'splice' 的算法性能如何？

Question

JavaScript：'splice' 的算法性能如何？

javascriptperformance

37

也就是说，如果我需要频繁地对数组进行单个插入操作，那么使用树或跳表数据结构是否更适合？

- Hamster

测试一下吧！这是回答这个问题最好的方式... - Harmen

1

有什么好的方法来测试这个？ - Hamster

1

如果JavaScript的数组确实是数组，那么它的时间复杂度为O(n)。 - Gumbo

@Gumbo：是的，我想那是有道理的。 - Hamster

尽管如此，仍需要从插入的元素开始逐个更改键。我认为仍然是O(n)。 - Hamster

显示剩余4条评论

3个回答

10

根据在Chrome、Safari和Firefox中进行的测试，以下是一个好的经验法则：将单个值插入到数组的中间大约比将值推送/移动到数组的一端慢一半。(注意:仅测试了大小为10,000的数组。)

http://jsperf.com/splicing-a-single-value

这已经非常快了。因此，不太可能需要实现另一种数据结构来提高性能。

更新：如下面评论中的eBusiness所指出的，在每个splice、push和shift操作中，该测试执行了昂贵的复制操作，这意味着它低估了性能差异。这里有一个经过修订的测试，避免了数组复制，因此应该更准确：http://jsperf.com/splicing-a-single-value/19

- Trevor Burnham

4

实际上，这完全取决于数组的长度。如果您将数组更改为拥有10万个元素，则在中间插入一个值比在末尾添加一个值慢95％，根据您的jsperf测试所测得的结果。这是因为在数组中间插入需要O(n)时间复杂度，而在末尾插入则可以是O(1)时间复杂度。 - Geoff

3

那个 jsperf 测试受到了复制数组的干扰，它主要测量创建一个全新的 10000 项数组所需的时间。我会为您翻译中文并尽力使其简明易懂，但不会添加解释或其他内容。 - aaaaaaaaaaaa

@电子商务哦，我明白你的观点！所以实际上测试结果低估了splice和push/shift之间性能差异。我会相应地编辑我的答案。 - Trevor Burnham

2

@TrevorBurnham 你应该真正删除旧文本，从不正确的基准测试中得出的结论可能不是读者想要的。 - aaaaaaaaaaaa

1

我认为你需要比较unshift而不是shift（shift会删除第一个值，而unshift会添加值）：https://jsperf.com/splicing-a-single-value/66 - maxime schoeni

显示剩余2条评论

1

移动单个值

// tmp = arr[1][i];
// arr[1].splice(i, 1); // splice is slow in FF
// arr[1].splice(end0_1, 0, tmp);

 tmp = arr[1][i];
 ii = i;
 while (ii<end0_1)
  {
  arr[1][ii] = arr[1][++ii];
cycles++;
  }
 arr[1][end0_1] = tmp;

- peter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- T.J. Crowder · Accepted Answer

您可以考虑是否要使用对象，所有 JavaScript 对象（包括Array实例）都是具有可选原型的键/值对的（高度优化的）集合。一个实现应该（请注意我没有说“会”）拥有合理的性能哈希算法。（更新：这是在2010年。在2018年，所有重要的JavaScript引擎上对象都高度优化。）

除此之外，splice的性能在不同的实现（例如供应商）之间可能会有很大差异。这就是为什么“不要过早地进行优化”这一建议适用于多个供应商实现（例如 Web 应用程序）运行的 JavaScript 应用程序比普通编程更为合适的原因之一。保持良好的模块化代码结构，并在出现性能问题时进行处理。