Какова временная сложность array.splice () в Google Chrome? - PullRequest
Новая
       50

Какова временная сложность array.splice () в Google Chrome?

30 голосов
/ 03 марта 2011

Если я удаляю один элемент из массива, используя splice (), примерно так: 

arr.splice(i, 1);

Будет ли это O(n) в худшем случае, потому что он сдвигает все элементы после i?Или это постоянное время с какой-то магией связанного списка внизу?

Ответы [ 2 ]

20 голосов
/ 03 марта 2011

В худшем случае должно быть O(n) (копирование всех элементов n-1 в новый массив).

Связанный список будет O(1) для одного удаления.

Для тех, кто заинтересован, я сделал этот эталонный тест . ( Пожалуйста, не запускайте в Windows XP / Vista ). Как вы можете видеть из этого, он выглядит довольно постоянным (то есть O(1)), так что кто знает, что они делают за кулисами, чтобы сделать это безумно быстрым. Обратите внимание, что независимо от этого фактический splice ОЧЕНЬ быстр.

Повторный запуск расширенного теста непосредственно в оболочке V8, который предлагает O(n). Обратите внимание, что вам нужны огромные размеры массива, чтобы получить среду выполнения, которая может повлиять на ваш код. Этого следует ожидать, как будто вы смотрите на код V8, который использует memmove для создания нового массива.

0 голосов
/ 26 февраля 2019
Тест :

Я воспользовался советом в комментариях и написал простой тест для определения времени набора данных размером 3000, каждый из которых содержал 3000 элементов. Тест просто склеил бы

  • первый элемент в первом массиве
  • второй элемент во втором массиве
  • третий элемент в третьем массиве
  • ...
  • 3000-й элемент в 3000-м массиве

Я предварительно собрал массив, чтобы все было просто.

Выводы:

Самое странное, что число раз, когда процесс сращивания занимает больше 1 мс, растет линейно по мере увеличения размера набора данных.

Я зашел так далеко, что протестировал его на наборе данных 300 000 на моей машине (но фрагмент SO имеет тенденцию падать после 3000).

Я также заметил, что число splice() с, которое занимало более 1 мс для данного набора данных (30 000 в моем случае), было случайным. Итак, я запустил тест 1000 раз и составил график результатов, и он выглядел как стандартное распределение; заставляет меня поверить, что случайность была вызвана только прерываниями планировщика.

Это идет вразрез с моей гипотезой и @ Иван догадывается, что splice() с начала массива будет иметь 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))
...