在Google Chrome中,array.splice()的时间复杂度是多少？

Question

如果我使用splice()从数组中删除一个元素,如下所示:

arr.splice(i, 1);

这是O(n)不是最糟糕的情况,因为它会在我之后移动所有元素？或者它是不变的时间,下面有一些链表魔术吗？

Answer 1

最坏的情况应该是O(n)(将所有n-1元素复制到新数组).

链表将O(1)用于单个删除.

对于那些感兴趣的人,我已经制作了这个懒散的基准.(请不要在Windows XP/Vista上运行).正如你从中可以看到的那样,它看起来相当稳定(即O(1)),所以谁知道他们在幕后做了什么让这个疯狂快.请注意,无论如何,实际上splice非常快.

直接在V8 shell中重新运行扩展基准测试O(n).请注意,您需要巨大的数组大小才能获得可能会影响代码的运行时.这应该是预期的,就好像您查看它用于memmove创建新数组的V8代码一样.

Answer 2

\xc2\xa1嗨！

\n

我自己做了一个实验，想分享我的发现。实验非常简单，我们对一个大小为 n 的数组运行 100 次拼接操作，并计算每个拼接函数花费的平均时间。然后我们改变 n 的大小，以检查它的行为。

\n

下图总结了我们对大数字的发现：

\n

对于大数字，它似乎呈线性表现。

\n

我们还检查了“小”数字（它们仍然很大，但没有那么大）：

\n

\n

在这种情况下，它似乎是恒定的。

\n

如果我必须决定一个选项，我会说它是 O(n)，因为这就是它对于大数的表现。但请记住，线性行为仅适用于非常大的数字。

\n

然而，很难找到明确的答案，因为 javascript 中的数组实现很大程度上取决于数组的声明和操作方式。

\n

我推荐这个 stackoverflow 讨论和这个 quora 讨论来了解数组是如何工作的。

\n

我在节点 v10.15.3 中运行它，使用的代码如下：

\n

const f = async () => {\n  const n = 80000000;\n  const tries = 100;\n  const array = [];\n  for (let i = 0; i < n; i++) { // build initial array\n    array.push(i);\n  }\n  \n  let sum = 0;\n  for (let i = 0; i < tries; i++) {\n    const index = Math.floor(Math.random() * (n));\n    const start = new Date();\n    array.splice(index, 1); // UNCOMMENT FOR OPTION A\n    // array.splice(index, 0, -1); // UNCOMMENT FOR OPTION B\n    const time = new Date().getTime() - start.getTime();\n    sum += time;\n    array.push(-2); // UNCOMMENT FOR OPTION A, to keep it of size n\n    // array.pop(); // UNCOMMENT FOR OPTION B, to keep it of size n\n\n  }\n  console.log(\'for an array of size\', n, \'the average time of\', tries, \'splices was:\', sum / tries);\n };\nf();\n

\n

请注意，代码有一个选项 B，我们对三参数 splice 函数进行了相同的实验来插入元素。它的工作原理类似。

\n

Answer 3

考试：

我采纳了评论中的建议，编写了一个简单的测试来计时拼接大小为 3,000 的数据集数组，每个数组包含 3,000 个项目。该测试将简单地拼接

• 第一个数组中的第一项
• 第二个数组中的第二项
• 第三个数组中的第三项
• ...
• 第 3000 个数组中的第 3000 项

为了简单起见，我预先构建了数组。

调查结果：

最奇怪的是，随着数据集大小的增加，拼接过程甚至需要超过 1 毫秒的次数会线性增长。

我在我的机器上测试了 300,000 个数据集（但 SO 片段在 3,000 个数据集后往往会崩溃）。

splice()我还注意到，对于给定数据集（在我的例子中为 30,000 个），花费时间超过 1 毫秒的 s 数量是随机的。所以我运行了 1,000 次测试并绘制了结果数，它看起来像一个标准分布；让我相信随机性只是由调度程序中断引起的。

这违背了我的假设和@Ivan的猜测，即splice()从数组开头进行 ing 将具有O(n)时间复杂度

以下是我的测试：

let data = []
const results = []
const dataSet = 3000

function spliceIt(i) {
  data[i].splice(i, 1)
}

function test() {
  for (let i=0; i < dataSet; i++) {
    let start = Date.now()
    spliceIt(i); 
    let end = Date.now()
    results.push(end - start)
  }
}

function setup() {
  data = (new Array(dataSet)).fill().map(arr => new Array(dataSet).fill().map(el => 0))
}

setup()
test()
// console.log("data before test", data)
// console.log("data after test", data)
// console.log("all results: ", results)
console.log("results that took more than 1ms: ", results.filter(r => r >= 1))