Создать массив с длиной n, инициализировать все значения с 0, кроме одного, индекс которого соответствует определенному условию, в O (1)?

Question

Я хочу создать массив типа номер с длиной n. Все значения внутри массива должны быть 0, кроме того, индекс которого соответствует условию.

Вот как я это делаю в настоящее время:

const data: number[] = [];
for (let i = 0; i < n; i++) {
  if (i === someIndex) {
    data.push(someNumber);
  } else {
    data.push(0);
  }
}

Так скажем n = 4, someIndex = 2, someNumber = 4 приведет к массиву [0, 0, 4, 0].

Есть ли способ сделать это в O (1) вместо O (n)?

Answer 1

Создание массива размером n за O (1) теоретически возможно в зависимости от деталей реализации - в принципе, если массив реализован как хеш-таблица, его свойство length можно установить без выделение или инициализация пространства для всех его элементов. Спецификация ECMAScript для конструктора Array(n) не обязывает Array(n) делать что-либо, что обязательно занимает больше O (1) времени, хотя также не требует, чтобы сложность времени была O (1).

На практике сложность времени Array(n) зависит от браузера, хотя проверить это немного сложно. Функцию performance.now() можно использовать для измерения времени, прошедшего между началом и концом вычисления, но точность этой функции во многих браузерах искусственно снижается для защиты от атак с тактовой частотой процессора, таких как Spectre. Чтобы обойти это, мы можем вызвать конструктор repetitions раз, а затем разделить прошедшее время на repetitions, чтобы получить более точное измерение для вызова конструктора.

Мой временной код приведен ниже:

function timeArray(n, repetitions=100000) {
    var startTime = performance.now();
    for(var i = 0; i < repetitions; ++i) {
        var arr = Array(n);
        arr[n-1] = 'foo';
    }
    var endTime = performance.now();
    return (endTime - startTime) / repetitions;
}

for(var n = 10000; n <= 1000000; n += 10000) {
    console.log(n, timeArray(n));
}

Вот мои результаты от Google Chrome (версия 74) и Firefox (версия 72); на Chrome производительность явно O (n), а на Firefox это явно O (1) с довольно постоянным временем около 0,01 мс на моей машине.

Я измерил с помощью repetitions = 1000 на Chrome и repetitions = 100000 на Firefox, чтобы получить достаточно точные результаты в разумные сроки.

Еще один вариант, предложенный @M. Дитц в комментариях должен объявить массив как var arr = [];, а затем назначить его по некоторому индексу (например, arr[n-1] = 'foo';). Оказывается, что на O (1) требуется время как Chrome, так и Firefox, оба последовательно в течение одной наносекунды:

Это предполагает версию с [] лучше использовать, чем версию с Array(n), но, тем не менее, спецификация не требует, чтобы это занимало O (1) время, поэтому могут быть другие браузеры, где эта версия занимает O (n) время , Если кто-то получит другие результаты в другом браузере (или другой версии одного из этих браузеров), добавьте комментарий.

Answer 2

Вам необходимо присвоить n значений, и поэтому есть такой объем работы, который нужно сделать. Работа увеличивается линейно с увеличением n .

Сказав это, вы можете надеяться сделать свой код немного быстрее, используя .fill:

const data: number[] = Array(n).fill(0);
data[someIndex] = someNumber;

Но не заблуждайтесь; это все равно O (n) : .fill может быть быстрее, но все равно требуется заполнить весь массив нулями, что означает, что соответствующий объем памяти должен быть инициализирован, так что операция имеет линейный сложность времени.

Если, однако, вы отбросите требование о необходимости установки нулей, вы можете только сохранить someNumber:

const data: number[] = Array(n);
data[someIndex] = someNumber;

Таким образом, вы на самом деле не выделяйте память для всего массива, поэтому этот фрагмент кода выполняется за постоянное время. Любой доступ к индексу, отличному от someIndex, даст вам значение undefined. Вы можете перехватить это условие и преобразовать его в ноль на лету:

let value = i in data ? data[i] : 0;

Очевидно, что если вы собираетесь получить доступ к всем индексам массива таким образом, вы ' опять будет линейная сложность времени.