Как заставить массив работать бррр

Реализация структуры данных в виде массива с быстрыми операциями.

Заявление об ограничении ответственности ! Вы должны быть знакомы со сложностью времени и пространства.

Массив использует O (N) памяти, имеет O (1) доступ, вставку и удаление в конце. Однако вставка и удаление с самого начала - это O (N).

Unshift медленнее, чем Push, и Shift медленнее, чем Pop, потому что им также необходимо отменить смещение / сдвинуть все элементы влево после добавления первого элемента. Он растет с его входом (линейный рост).

Существует множество структур данных - связанные списки можно удалять и удалять быстро, но доступ - O (N). Стеки и очереди могут быть эффективными только на одном конце. Хеш-таблицы работают быстро, но требуют много памяти и не имеют индексации. Некоторые деревья большую часть времени работают довольно быстро, но для их эффективности требуется конкретный вариант использования.

Цель

Реализуйте массив, который имеет O (1) для доступа, вставки и удаления, использует как можно меньше памяти и в большинстве ситуаций будет неотличим от массива.

Я буду использовать JavaScipt и имитирую его реализацию массива. Обратите внимание, что реализация массива JavaScript - это реализация динамического массива, который несколько раз изменяет размер массива по мере того, как элементы вставляются / удаляются из него (известная как амортизированная константа).

Поскольку я не знаю правильного имени этой структуры данных, я буду называть ее Двоичный массив.

Ссылка на репозиторий: https://github.com/AT-290690/binary-array

В конце концов, он должен действовать так же, как массив, за исключением того, что он сможет изменять как начало, так и конец коллекции из миллиона элементов, не беспокоясь.

NANOBENCH version 2
> node benchmark/benchmark.js
# regularArray.get middle 200.000 items
ok ~60 μs (0 s + 59833 ns)
# binaryArray.get middle 200.000 items
ok ~233 μs (0 s + 232709 ns)
# regularArray.push 200.000 times
ok ~4.62 ms (0 s + 4624250 ns)
# binaryArray.push 200.000 times
ok ~7.33 ms (0 s + 7330417 ns)
# regularArray.pop 200.000 times
ok ~2.04 ms (0 s + 2036458 ns)
# binaryArray.pop 200.000 times
ok ~5.53 ms (0 s + 5525167 ns)
# regularArray.shift 200.000 times
ok ~4.49 s (4 s + 489609209 ns)
# binaryArray.shift 200.000 times
ok ~7.96 ms (0 s + 7956125 ns)
# regularArray.unshift 200.000 times
ok ~4.43 s (4 s + 426783042 ns)
# binaryArray.unshift 200.000 times
ok ~10 ms (0 s + 10255167 ns)
all benchmarks completed
ok ~8.95 s (8 s + 954412377 ns)

Идея

Как добиться O (1) операций в начале? Ответ заключается в вопросе - Почему массив не сдвигается, а сдвигает O (N)? Потому что он меняет порядок своих элементов каждый раз он снимается и сдвигается.

Заключение - просто не меняйте порядок вещей! Просто сделайте все в конце! Push и Pop - это O (1), поэтому нам просто нужно использовать их вместо них.

Но… Как нам отслеживать индексы? Вздох ... На это уйдет больше времени. Короткий ответ - используйте два массива.

Реализация

Сначала мне нужны два массива - один левый и один правый.

left = [];
right = [];

Каждое добавленное значение в конце я поставлю справа.

Каждое значение, которое добавляется вначале, я помещаю слева.

Чтобы отслеживать смещения, мне понадобятся два свойства:

смещение влево и смещение вправо, которые увеличиваются / уменьшаются при каждой операции.

Время

Для достижения O (1) требуется простое управление состоянием и немного математики.

Я буду отслеживать вставки и соответственно увеличивать offsetRight и offsetLeft.

offsetRight = 0; // offsetRight++ when adding at end
offsetLeft = 0; // offsetLeft-- when adding at start

Я делаю то же самое, когда добавляю или удаляю элементы

Если индекс отрицательный - вставьте слева и наоборот.

Удаление и установка аналогичны. Но как получить товары по их соответствующим индексам?

В классе BinaryArray есть метод get.

По заданному индексу и вычисляет ключ, который затем соответствует фактическому индексу в массиве, содержащем значение.

index + this._offsetLeft

В действии:

const binArr = new BinaryArray();
binArr.addToRight(0);
binArr.addToRight(1);
binArr.addToRight(2);
binArr.addToRight(3);
binArr.addToRight(4);
binArr.addToLeft(-1);
binArr.addToLeft(-2);
binArr.get(0) // -2
binArr.get(1) // -1
binArr.get(2) // 0
binArr.get(3) // 1
...

Вот гифка, описывающая вышеизложенное (синий - справа, красный - слева).

Общий размер массива: слева * -1 + справа = -2 * -1 + 5 = 7

Независимо от операции индексы поддерживаются согласованными и упорядоченными.

  _offsetRight: 5,
  _offsetLeft: -2,
  left: [ <1 empty item>, -1, -2 ],
  right: [ 0, 1, 2, 3, 4 ],
  size: 7

* left всегда будет иметь пустое значение в индексе 0, поскольку индекс 0 не может иметь как положительное, так и отрицательное значение. Также это имеет смысл, поскольку в середине (точка поворота) может быть только один элемент.

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

binArray.toArray(); // [-2, -1, 0, 1, 2, 3, 4]
[...binArray]; // [-2, -1, 0, 1, 2, 3, 4]

Отлично, теперь у меня есть все операции в O (1), но как насчет пространства?

Космос

Давайте вставим больше элементов в конце.

Элементы массива Left и Right не сбалансированы: -2 в начале и 9 в конце (один массив больше другого). Это вообще не проблема, но иногда мне может понадобиться, чтобы на каждой стороне было одинаковое количество предметов.

Реализация метода балансировки:

Контрольный показатель

Вот очень простой тест «Массив против BinaryArray». BinaryArray выводит результат мгновенно, пока массив не распечатает свои первые результаты через несколько секунд. Будет только хуже, если количество элементов увеличится, в то время как BinaryArray останется неизменным.

Он действительно идет «бррр», но не похож на массив… пока. У массивов есть методы, которые упрощают их использование.

Подобно массиву

Если он выглядит как массив и действует как массив, значит, это объект!

В основном это будет специфично для JavaScript - массив имеет следующие методы:

push, pop, unshift, shift, map, filter, reduce, find, some, every….

.push, .pop, .shift и .unshift просты (просто реализуйте их как можно ближе к спектру).

Основа для итераторов такова:

for (let i = 0; i < this.size; i++) callback(this.get(i), i, this);

.concat мог бы быть лучше по пространственной сложности, но на данный момент это достаточно хороший чит:

concat(second) { 
return new BinaryArray([...this, ...second]) 
}

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

sort(callback) {
 return new BinaryArray(this.toArray().sort(callback));
 }

В спецификации .reverse указано, что это нужно делать на месте (без создания каких-либо дополнительных массивов), так что здесь нет никакого обмана.

Будет только пропускать. заполнить

Проверка сходства с массивом

Если приведенный ниже код выводит те же результаты - мы массив.