По какому принципу работает алгоритм с массивом очереди?

Question

[MishaXXL]

Есть бесконечно поступающие запросы
Как я понимаю, все это дело мы записываем в массив и у нас получается

const tasks = [task1, task2, task3, ...task100000000]

Из него уже начинаем брать наши таски на обработку, но после выполнения task1не удаляем его из начала массива, чтобы каждый таске его не перебирать
Как тогда достигается актуальное хранение текущей очереди, чтобы наш массив бесконечно не рос?

Comments

[Everything_is_bad]

но после выполнения task1 не удаляем его

почему? при чем тут перебор?

[Lynn «Кофеман»]

> Как я понимаю, все это дело мы записываем в массив

может да, а может и нет, зависит от реализации

> Как тогда достигается актуальное хранение текущей очереди, чтобы наш массив бесконечно не рос

удалением выполненных задач

[mayton2019]

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

А зачем его "перебирать" второй раз? Уже вроде выполнен.

[MishaXXL]

Everything_is_bad, если мы удалим элемент из начала массива, он у нас переберется и так на каждое удаление

[MishaXXL]

Lynn «Кофеман», в каких-то реализациях это делается через объекты?
Для каких случаев он будет предпочтительней массива?

[Everything_is_bad]

MishaXXL, но тебе не нужно его перебирать, ты придумал проблему на ровном месте. Кроме этого, в реальности использую уже готовые реализации очереди, а не коленочное поделие

Answer 1

[Wataru]

Много разных вариантов для структур данных. Например, кольцевой буфер. Или связный список. В этом случае можно удалять элемент с начала, не сдвигая все элементы в массиве.

Comments

[MishaXXL]

Но у нас же так массив станет приобретать непомерно большую длину и однажды достигнет максимального значения
Да и вообще, вроде, пустой массив на 1 млрд. зарезервированных элементов вроде значительно больше весит, чем пустой массив на 1 тыс. зарезервированных элементов. Или не так?

[Everything_is_bad]

MishaXXL, ты опять что-то придумываешь на ровном месте. Еще раз, "чтобы наш массив бесконечно не рос", из него надо удалять элементы, это вот прям элементарная логика.

[Wataru]

MishaXXL, Массив не выделяют сразу фиксированного размера, чтобы вообще все влезло. Выделяют, допустим, 10 элементов. Если циклический буфер заполнился, то перевыделяют память на 20 элементов, все их туда копируют. Когда заполнится этот, выделяют 40 элементов и т.д. В результате любая операция добавления будет O(1) в среднем, ибо эти перевыделения будут происходить все реже и реже за счет увеличения длины в 2 раза. Так работает тот же std::vector.

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

[MishaXXL]

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

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

[Wataru]

MishaXXL, Массив будет размера столько, сколько максимально было заявок в какой-то момент времени (ну, в 2 раза больше на самом деле). Он не будет расти бесконечно.

Кольцевой буфер - он так называется, потому что он замкнут в кольцо. После конца идет начало. Ваши заявки в этом буфере, как змейка в компьютерной игре, дивгаются по этому буферу. С одного конца они добавляются. с другого удаляются. Вся змейка ползет по массиву вправо и оборачивается.

После того, как вы какой-то элемент "удалили", заменив на undefined, он будет снова переиспользован, когда "змейка" пройдет полный круг и вернется на эту позицию.

Если змейка догоняет свой хвост, то массив увеличивается в 2 раза, и змейка помещается туда. Массив не будет длиннее, чем длина змейки*2 в какой-то момент времени. Но массив не растет просто так при добавлении заявок. Если у вас максимум 100 активных заявок есть в каждый момент времени, он никогда не будет длиннее 200. Ибо змейка длины 100 сама себя не догонит в таком массиве никогда и нового увеличения не произойдет.

[MishaXXL]

Wataru, понял, спасибо
А на случай, если выйдет, что у нас изначально был массив на 1000 элементов, но в какой-то момент случайно пришло 1005 и переполнение массива оказалось в центре, где записаны уже новые, но не выполнены еще все старые, то как это обрабатывается?

[Wataru]

MishaXXL, Выделяется новый массив размера 2000 элементов. Эти 1000 туда копируются. Потом спокойно дописываются 5 новых в конец.

[Alexandroppolus]

MishaXXL,

переполнение массива оказалось в центре,

вот здесь чувак что-то такое мутил под этот случай

[Wataru]

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

[MishaXXL]

Alexandroppolus, подскажи, почему зануление ячеек в массиве понижают производительность?

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

И как описывается скорость получения данных из массива?
Почему он не производительная и как эта реализация выдает максимум производительности?

Иногда бывает необходимо "заглянуть" в следующий элемент очереди без его извлечения - поддержим обращение queue[0] по аналогии с обычным массивом. Для этого прямо в конструкторе объявим геттер для свойства .0

Object.defineProperty(this, 0, {
      get : () => this._head < this._tail ? this._buffer[this._head] : undefined
});

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

Answer 2

[Виктор Кожухарь]

Вот вам готовая простейшая очередь в виде объекта без всяких переборов:

class Queue {
  constructor() {
    this.items = {};
    this.front = 0;
    this.rear = 0;
  }
  enqueue(item) {
    this.items[this.rear] = item;
    this.rear++;
  }
  dequeue() {
    const item = this.items[this.front];
    delete this.items[this.front];
    this.front++;
    return item;
  }
  peek() {
    return this.items[this.front];
  }
  get size() {
    return this.rear - this.front;
  }
  isEmpty() {
    return this.rear == 0;
  }
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);

console.log("Объект очереди: ", queue);

const removed_element = queue.dequeue();
console.log("Обработанный (удаленный) элемент: ", removed_element);

console.log("Объект очереди:", queue);

const top_element = queue.peek();
console.log("Текущий элемент очереди для обработки (без удаления): ", top_element);

const queue_length = queue.size;
console.log("Размер очереди: ", queue_length);

Answer 3

[Saboteur]

Вы определитесь с формулированием вопроса.
Если хранить задачи в массиве вам кажется слишком напряжно, можно использовать другие структуры, удаление которых не требует пересоздания (двухсторонний список, например).
Чем пересборка массива мешает - также не понимаю. Нужно ж понимать как часто у вас добавляются/удаляются задачи, сколько времени занимает пересборка.
Может быть можно просто помечать задачи как удаленные, и удалять раз в сутки в нерабочее время.

В общем у вас вопрос слишком абстрактный

Comments

[MishaXXL]

Мы подписаны на получение задач со стороны сервера и приложения
Мы их должны выполнять строго по очереди по мере их поступления
Каждая задача может выполняться от 0.1 сек до 3 сек.
Для этого я добавляю их в массив
const tasks = []
Когда приходит новая задача, она вызывает функцию handle, которая в свою очередь работает рекурсивно и пока не дойдет до конца массива, будет выполнять каждую следующую задачу из него.

И, если после выполнения задачи из массива, мы ее удалим, то в какой-то момент у нас будет массив из миллиона undefinedв нем, после которых снова добавляются новые задачи.
Так массив будет расти вечно.

Мне стало интересно, как решается проблема с очередью, чтобы не допустить бесконечного роста массива?

[Everything_is_bad]

MishaXXL,

И, если после выполнения задачи из массива, мы ее удалим, то в какой-то момент у нас будет массив из миллиона undefinedв нем, после которых снова добавляются новые задачи.

ты в курсе про shift? и зачем вообще у тебя тут рекурсия. Либо вообще используй нормальные очереди

[Saboteur]

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

Мне стало интересно, как решается проблема с очередью, чтобы не допустить бесконечного роста массива?

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