46

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

arr.splice(i, 1);

这会O(n)是最坏的情况，因为它会在 i 之后移动所有元素吗？或者它是恒定的时间，下面有一些链表魔法？

4

3 回答 3

30

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

链接列表将O(1)用于单个删除。

对于那些感兴趣的人，我做了这个懒惰的基准测试。（请不要在 Windows XP/Vista 上运行）。正如你可以从这里看到的，它看起来相当稳定（即O(1)），所以谁知道他们在幕后做了什么来让这个疯狂快速。请注意，无论如何，实际splice速度非常快。

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

于 2011-03-03T02:22:22.953 回答
5
测试：

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

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

我预先构建了数组以保持简单。

调查结果：

最奇怪的是，随着数据集大小的增加，拼接过程甚至花费超过 1ms 的次数呈线性增长。

我什至在我的机器上测试了一个 300,000 的数据集（但 SO 代码段往往在 3,000 之后崩溃）。

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

这违背了我的假设和@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))

于 2019-02-26T06:31:50.087 回答
4

你好！

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

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

对于大数字，它的行为似乎是线性的。

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

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

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

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

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

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

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

  }
  console.log('for an array of size', n, 'the average time of', tries, 'splices was:', sum / tries);
 };
f();

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

于 2021-05-18T14:45:59.307 回答