Как реализовать очередь фиксированной длины?

Question

[NFly]

На JavaScript, хотя другие языки тоже интересны.
Нужно реализовать такую структуру: есть массив из фиксированного количества элементов. Когда в массив добавляется новый, то с начала массива и вниз элементы сдвигаются, то есть самый старый пропадает, а новый вставленный получает индекс 0.
Как лучше реализовать такую функциональность с мин. затратами на каждую вставку?

Comments

[netW0rm]

Какой тип данных будет храниться в массиве?

[NFly]

netW0rm: ответил ниже, не увидел ваш коммент

Answer 1

[Stalker_RED]

var stack = [];
var maxLen = 5;
...
stack.unshift(newValue) // вставка нового элемента в начало
if (stack.length > maxLen) stack.pop() // убираем лишний элемент

Осталось обернуть это в объект и добавить геттер и сеттер.

Comments

[NFly]

круто. Правда все эти шифты и попы каждый раз есть изменение структуры массива, что не быстро скорее всего.

[Элль Соломина]

NFly: а по другому для массива никак. Массив это непрерывный кусок памяти и в его начало просто так (без перемещения куска памяти) никак. Для сокращения расходов на вставку в начало стоит использовать не stack а какой нибудь list или queue, т.е. связные списки. Однако в случае списков непрерывного куска памяти у вас уже не будет. Про типы и их использование советую почитать, например, тут codetunnel.com/9-javascript-tips-you-may-not-know .

[NFly]

Алексей Соломин: а что если: предположим, у нас все элементы массива это ссылочные типы (массивы, объекты). Тогда каждый индекс массива хранит лишь ссылку. Можно тогда просто сделать так, чтобы при вставке нулевой индекс получал ссылку на новый элемент, первый индекс получал ссылку на тот элемент массива, который до вставки был нулевым и т.д. тогда последний индекс просто перестанет ссылаться на старый элемент и сборщик мусора его сам удалит?

[Stalker_RED]

NFly: Мы сейчас про яваскрипт или вообще? Если про яваскрипт, то все равно придется пройтись по всему стеку перемещая ссылки (поверьте, в unshift это оптимизируется самим движком).
Если про какие-то низкоуровневые языки, то всё уже украдено до нас:
https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA
https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D...
https://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D...

[netW0rm]

NFly: все эти шифты и попы так и будут работать

[NFly]

Stalker_RED: да, придется, но это можно сделать одним циклом, буфетной переменной и операциями присваивания, то есть не вызывать две функции, то есть может быть менее накладно. В общем надо замерять. Да, яваскрипт.

[Stalker_RED]

NFly: Вы не единственный кто пытался это сделать: www.bennadel.com/blog/2308-creating-a-fixed-length...

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

[NFly]

Stalker_RED: автор использовал прототипы, калы, классы и нагородил кучу функций, поэтому соглашусь с вами, в производительности он не выиграл.

[Элль Соломина]

NFly: в таком контексте если речь не про JS, то например в C++ в list именно так вставка первого элемента и происходит.

Answer 2

[Юрий]

операция unshift в js довольно дорогая
сделал пример для тестирования pop/unshift
https://jsfiddle.net/uzjcttj2/5/ (откройте консоль)
заметьте что у unshift колич итераций в 100 раз меньше. если ставить больше то браузер зависнет.

первые 3 теста - скорость создания массивов разными способами, заметьте что у unshift в 100 раз меньше элементов. видим что самый быстрый - push.

далее 2 теста - скорость добавления/доставания элементов.
хорошо видно что на маленьких массивах время сильно падает.

6ой тест - скорость pop - как видим она очень хорошая.

итого если очередь небольшая - подойдет вариант Stalker_RED

для гигантских очередей написал свою реализацю
используем 2 массива: из b только читаем с конца, в a вставляем и только в конец.
то есть мы берем из конца и вставляем в конец - в js это очень быстро.

сравнение скорости с вариантом Stalker_RED https://jsfiddle.net/wL84rr46/4/
в обоих случаях у нас очередь из 1M элементов.
примерно за одно и то же время (100-200мс на моем компе) первый случай делается всего 100 операции. в моем примере 10M

a = [];
b = []; 
for (i=1e6; --i;) a.push(i); // init array 1M items
var overflowCount;

console.time('example2');
for (i = 1e7; --i;) {
		a.push(123456);
    overflowCount = a.length - maxLen;
    if (overflowCount > 10000) { // удаляем лишние элементы только при серьезном переполнении
        a = a.splice(0, overflowCount); // удаляем в начале overflowCount элементов
    }
    
    if (b.length === 0) { // в b закончились элементы
        b = a; // переносим все в b из a
        a.length = 0; // обнуляем буфер вставки
        if (b.length > maxLen) b.length = maxLen; 
        b.reverse(); // разворачиваем буфер извлечения чтобы доставать элементы из конца
    }
    b.pop(); 
}

Comments

[Юрий]

при этом если буфер будет не 1M элементов а еще больше то скорость не сильно упадет, а в первом примере - очень сильно.

[NFly]

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

[Stalker_RED]

NFly: Дык в js и так всё кроме примитивов передается по ссылке.

Юрий: Я даже не пытался как-то оптимизировать.
И вы же знаете, что синтетические тесты такие синтетические...
В реальном случае данные из очереди должны куда-то передаваться, а не просто делать в пустоту b.pop()
И в условии не сказано, с какой стороны этот буфер будет считываться. В случае FIFO, геттер должен проверять не выходит ли текущее значение за диапазон. И вероятно, сбрасывать переполнение придется чаще. Хотя можно завести свой указатель на последний прочитанный элемент, и при незначительном переполнении просто сдвигать его.

[Юрий]

NFly: вот пример для объектов https://jsfiddle.net/wL84rr46/5/

1 пример стал 800мс (было 200) медленнее в 4 раза
2ой пример стал 240мс (было 120 примерно) медленнее в 2 раза

[Юрий]

Stalker_RED: к вам никаких претензий. ваш алгоритм простой и работает прекрасно при небольших длинах очереди (менее 1000-10000 элементов конечно заморачиваться не стоит на это). просто нужно было с чем то сравнить. самому было интересно как эту задачу оптимизировать.

"В случае FIFO, геттер должен проверять не выходит ли текущее значение за диапазон. И вероятно, сбрасывать переполнение придется чаще. "

нет не требуется.
сброс if (overflowCount > 10000) нужен исключительно для того чтобы в очереди не скопилось очень много лишних элементов (например мы только пишем туда и ничего не извлекаем, если этого не делать там скопятся милионы элментов, вставку это сильно не замедлит, но память будет расходовать, поэтому эта очистка исключительно для экономии памяти).

очередь всегда не более миллиона. реальное ограничение длины происходит в if (b.length > maxLen) b.length = maxLen; при копировании.

доп указателей не требуется.

[Юрий]

NFly: бегло прочитал ваши коменты в др ответе, не совсем понял что за переприсваивание ссылок.

вы упомянули там с++ в принципе в js можно было бы сделать очередь как в с++ (лет 10 назад страдал таким) то есть каждый элемент ссылается на след объект, и главный обьект очереди имеет ссылку на первый и последний, тогда добавление и удаление обьектов тоже очень простые - поменять пару ссылок. но будет кончено оверхэд по памяти изза доп обьектов (типа ListItem которые хранят указатели на соседние такие элементы и на хранимые обьекты).

указаннное мной решение работает быстро и не требует доп обьектов. в js массивы и так мощная штука можно вполне обойтись ими.

[NFly]

Юрий: имел ввиду не посто заменить примитивные типы на объекты, а избавиться от шифт и поп.
а что если: предположим, у нас все элементы массива это ссылочные типы (массивы, объекты). Тогда каждый индекс массива хранит лишь ссылку. Можно тогда просто сделать так, чтобы при вставке нулевой индекс получал ссылку на новый элемент, первый индекс получал ссылку на тот элемент массива, который до вставки был нулевым и т.д. тогда последний индекс просто перестанет ссылаться на старый элемент и сборщик мусора его сам удалит?
И реализовать это через буфферные переменные, в цикле переприсваивая индексам массива элементы. То есть индекс n получает элемент индекса n-1. Последний, тот который length-1 удаляется без шифт,как бы попадает. А первым индексом то есть нулевым становится новый вставленный объект.
Прошу пощения что не могу привести код, с планшета и это набирать больно.

[Юрий]

NFly: понял что вы хотите, можно попробовать, но уверен что это будет медленнее.

по первой моей ссылке был тест скорости вставки
array create push 10M: 510.000ms
array create by index 10M: 1668.000ms

push быстрее чем присваивание по индексу (a[i] = ...)
а тут у вас будет цикл с присваиванием.

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

[NFly]

Юрий: да, вы правы. Eще раз спасибо за развернутый ответ.
Я имел ввиду что-то такое:
https://jsfiddle.net/uzjcttj2/6/

[Юрий]

NFly: да, в js такое не прокатит. "100 итераций - 320ms" не айс

если уж хотите ссылками то надо делать двухсвязные списки (хотя для этой задачи можно и односвязные) algmet.narod.ru/theory_a4m/spiski

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