@NFly

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

На JavaScript, хотя другие языки тоже интересны.
Нужно реализовать такую структуру: есть массив из фиксированного количества элементов. Когда в массив добавляется новый, то с начала массива и вниз элементы сдвигаются, то есть самый старый пропадает, а новый вставленный получает индекс 0.
Как лучше реализовать такую функциональность с мин. затратами на каждую вставку?
  • Вопрос задан
  • 708 просмотров
Пригласить эксперта
Ответы на вопрос 2
Stalker_RED
@Stalker_RED
var stack = [];
var maxLen = 5;
...
stack.unshift(newValue) // вставка нового элемента в начало
if (stack.length > maxLen) stack.pop() // убираем лишний элемент

Осталось обернуть это в объект и добавить геттер и сеттер.
Ответ написан
riky
@riky
Laravel
операция 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(); 
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы