Блог

См. Также Редактирование

Я работаю на JavaScript, но читаемый псевдокод любого типа может ответить на мой вопрос.

Мне будет сложно описать это, поэтому, пожалуйста, не стесняйтесь комментировать пояснения — я отвечу на них и соответствующим образом доработаю свой пост.

По сути, у меня есть массив, который действует как очередь, элементы добавляются, и когда они обрабатываются, их нужно удалить, и в конечном итоге будет добавлено больше. Какой самый быстрый способ получить первый элемент в массиве, когда меня не волнует индекс? Я просто хочу выполнять итерацию на основе первого добавления без необходимости каждый раз сдвигать все записи в массиве вниз. Также стоит упомянуть, что я не перебираю массив, у меня есть главный цикл для моего приложения, который проверяет, есть ли в массиве элементы в каждом цикле, и если есть, он захватит эти данные, а затем удалит их из массива. В настоящее время для быстрого выполнения этого я использую pop, но теперь понимаю, что мне нужно каждый раз сначала получать самый старый элемент в очереди, а не самый новый.

Для получения дополнительных разъяснений, если это необходимо:

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

Чтобы сделать это, в моей текущей системе, когда я понимаю, что мне нужен блок для анализа, я помещаю его уникальный идентификатор в массив, затем непрерывный цикл в моем приложении постоянно проверяет указанный массив, проверяя, есть ли в нем элементы. Если это произойдет, он извлекает последний элемент массива и передает уникальный идентификатор в функцию синтаксического анализа.

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

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

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

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

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

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

Спасибо

РЕДАКТИРОВАТЬ: при продолжении поиска в Google у меня возникает ощущение ладони, и я понял, что проблема, которую я описываю, — это стек против очереди. Но теперь мой вопрос переходит к тому, какова самая быстрая реализация очереди, когда индекс на самом деле не имеет для меня ценности?

Ниже приведена реализация очереди FIFO с использованием односвязного списка в javascript.

Для получения дополнительной информации о связанном списке -> https://www.geeksforgeeks.org/linked-list-set-1-introduction /

 // queue implementation with linked list
var ListNode = function(val,next = null){
  
  this.val  = val 
  this.next = next

};

var Queue = function(){
  
  let head = null;
  let tail = null;
  
  this.show = function(){
    
    let curr = head;
    let q = [];
    
    while(curr){
      q.push(curr.val);
      curr = curr.next;
    }
    
    return q.join(' -> ');
  }
  
  this.enqueue = function(item){
    
    let node = new ListNode(item);
    if(!head) {
      head = node;
      tail = node;
    } else {
      tail.next = node;
      tail = node;
    }
    
  }
  
  this.dequeue = function(){
    
    if(!head) return null;
    else {
    
      let first = head;
      head = head.next;
      
      first.next = null;
      
      return first;
    }
    
  }
  
}

var myQueue = new Queue();
myQueue.enqueue(1); // head -> 1 
console.log(myQueue.show())
myQueue.enqueue(2); // head -> 1 -> 2
console.log(myQueue.show())
myQueue.enqueue(3); // head -> 1 -> 2 -> 3
console.log(myQueue.show())
myQueue.dequeue(); // head -> 2 -> 3
console.log(myQueue.show())