Google Chrome中array.splice（）的时间复杂度是多少？ [英] What's the time complexity of array.splice() in Google Chrome?

问题描述

  arr.splice（i，1）如果我使用splice（）从数组中移除一个元素， ; 
  

这会是 O（n） in最坏的情况是因为它转移了我之后的所有元素？或者它是不变的时间，下面有一些链接列表魔术？

code> O（n）（将所有 n-1 元素复制到新数组中）。

对于单次删除，链接列表将为 O（1）。 对于那些感兴趣的是我制作了这个懒散的基准测试。 （请勿在Windows XP / Vista上运行）。 正如你可以看到的那样，它看起来相当稳定（即 O（1）），所以谁知道他们在幕后做了什么疯狂的快。请注意，无论如何，实际 splice 非常快。

重新运行 extended benchmark 直接在V8 shell中建议 O（n）。但请注意，您需要巨大的数组大小才能获得可能影响代码的运行时。这应该是可以预料的，如果你看看它使用 memmove 创建新数组的V8代码。

If I remove one element from an array using splice() like so:

arr.splice(i, 1);

Will this be O(n) in the worst case because it shifts all the elements after i? Or is it constant time, with some linked list magic underneath?

解决方案

Worst case should be O(n) (copying all n-1 elements to new array).

A linked list would be O(1) for a single deletion.

For those interested I've made this lazily-crafted benchmark. (Please don't run on Windows XP/Vista). As you can see from this though, it looks fairly constant (i.e. O(1)), so who knows what they're doing behind the scenes to make this crazy-fast. Note that regardless, the actual splice is VERY fast.

Rerunning an extended benchmark directly in the V8 shell that suggest O(n). Note though that you need huge array sizes to get a runtime that's likely to affect your code. This should be expected as if you look at the V8 code it uses memmove to create the new array.

这篇关于Google Chrome中array.splice（）的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！