Javascript：“拼接”的算法性能是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4228081/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Javascript: What's the algorithmic performance of 'splice'?
提问by Hamster
That is, would I be better suited to use some kind of tree or skip list data structure if I need to be calling this function a lot for individual array insertions?
也就是说，如果我需要为单个数组插入多次调用此函数，我是否更适合使用某种树或跳过列表数据结构？
采纳答案by T.J. Crowder
You might consider whether you want to use an object instead; all JavaScript objects (including Arrayinstances) are (highly-optimized) sets of key/value pairs with an optional prototype An implementation should(note I don't say "does") have a reasonable performance hashing algorithm. (Update: That was in 2010. Here in 2018, objects are highlyoptimized on all significant JavaScript engines.)
您可能会考虑是否要使用对象；所有 JavaScript 对象（包括Array实例）都是（高度优化的）具有可选原型的键/值对集 实现应该（注意我不是说“确实”）具有合理的性能散列算法。（更新：那是在 2010 年。在 2018 年，对象在所有重要的 JavaScript 引擎上都得到了高度优化。）
Aside from that, the performance of spliceis going to vary a lotbetween implementations (e.g., vendors). This is one reason why "don't optimize prematurely" is even more appropriate advice for JavaScript applications that will run in multiple vendor implementations (web apps, for instance) than it is even for normal programming. Keep your code well modularized and address performance issues if and when they occur.
除此之外，splice不同实现（例如，供应商）的性能会有很大差异。这就是为什么“不要过早优化”对于将在多个供应商实现（例如 Web 应用程序）中运行的 JavaScript 应用程序甚至比正常编程更合适的建议的原因之一。保持代码模块化，并在发生时解决性能问题。
回答by Trevor Burnham
Here's a good rule of thumb, based on tests done in Chrome, Safari and Firefox: Splicing a single value into the middle of an array is roughly half as fastas pushing/shifting a value to one end of the array. (Note: Only tested on an array of size 10,000.)
这是一个很好的经验法则，基于在 Chrome、Safari 和 Firefox 中完成的测试：将单个值拼接到数组中间的速度大约是将值推送/移动到数组一端的速度的一半。（注意：仅在大小为 10,000 的数组上进行了测试。）
http://jsperf.com/splicing-a-single-value
http://jsperf.com/splicing-a-single-value
That's pretty fast. So, it's unlikely that you need to go so far as to implement another data structure in order to squeeze more performance out.
这是相当快的。因此，您不太可能需要实现另一种数据结构以提高性能。
Update: As eBusiness points out in the comments below, the test performs an expensive copy operation along with each splice, push, and shift, which means that it understates the difference in performance. Here's a revised test that avoids the array copying, so it should be much more accurate: http://jsperf.com/splicing-a-single-value/19
更新：作为电子商务在下面的评论所指出的，该测试执行与每个沿一个昂贵的复制操作splice，push和shift，这意味着它低估在性能上的差异。这是一个避免数组复制的修订测试，因此它应该更准确：http: //jsperf.com/splicing-a-single-value/19
回答by peter
Move single value
移动单个值
// 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;回答by Renan
Prefer shift/popto spliceif operating at head or tail of array:
喜欢shift/pop到splice如果在头或阵列尾的操作：
