Javascript:'拼接'的算法性能是什么？

Question

也就是说,如果我需要为单个数组插入调用这个函数,我是否更适合使用某种树或跳过列表数据结构？

Answer 1

您可以考虑是否要使用对象; 所有JavaScript对象(包括Array实例)都是(高度优化的)键/值对的集合,带有可选的原型实现应该(注意我不说"确实")具有合理的性能散列算法.(更新:那是在2010年.在2018年,对象在所有重要的JavaScript引擎上都得到了高度优化.)

除此之外,实现(例如,供应商)之间的性能splice会有很大差异.这就是为什么"不过早优化"对于将在多个供应商实现(例如,网络应用程序)中运行的JavaScript应用程序而言甚至比正常编程更合适的一个原因.保持代码良好的模块化,并在出现问题时解决性能问题.

Answer 2

根据在Chrome,Safari和Firefox中进行的测试,这是一个很好的经验法则:将单个值拼接到数组中间的速度大约是将数值推送/移动到数组一端的速度的一半.(注意:仅在10,000的数组上进行测试.)

那很快.因此,您不太可能需要实现其他数据结构以便更多地提高性能.

更新:作为电子商务在下面的评论所指出的,该测试与每个沿进行昂贵的复制操作splice,push和shift,这意味着它低估在性能上的差异.这是一个修改过的测试,可以避免阵列复制,所以它应该更准确:http://jsperf.com/splicing-a-single-value/19

-1 jsperf测试通过复制数组而受到污染,它主要测量创建一个全新的10000项数组所需的时间. (3认同)
实际上，它完全取决于数组的长度。如果更改为 100,000 个元素的数组，那么根据您的 jsperf 测试测量，将值拼接到中间比在末尾添加值慢 95%。那是因为在数组的大小中插入中间是 O(n)，而在最后插入可以是 O(1)。 (2认同)
@TrevorBurnham 你真的应该删除旧文本，从不正确的基准中得出的结论可能不是读者所追求的。 (2认同)