Создайте структуру массива в JavaScript, в которой отсутствует индексирование

Question

Индексирование (поддержание индексов) в массиве составляет Array.prototype.shift и Array.prototype.unshift O (N) вместо O (1).

Однако, если мы просто хотим использовать pop () / push () / shift () и unshift () и никогда не используют индексы для поиска, есть ли способ реализовать массив JavaScript, в котором отсутствует индексация?

Я не могу придумать, как это сделать.Единственный способ сделать это - использовать массивы и использовать только pop () / push () (поскольку это O (1)) ... но даже с несколькими массивами, не уверен, что это возможно.

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

Конечная цель: попытка создать очередь FIFO, в которой все операции выполняются в постоянном времени, без использования связанного списка.

Answer 1

Как насчет ES2015 Map, который вы индексируете целыми числами?

Давайте назовем карту myFIFOMap.

Вы сохраняете first и last целочисленный член как часть вашего класса FIFO.Начните их обоих с нуля.

Каждый раз, когда вы хотите push() в свою очередь FIFO, вы звоните myFIFOMap.set(++last,item).И pop() выглядит примерно так:

const item = myFIFOMap.get(first); 
myFIFOMap.delete(first++); 
return item;

Должен быть O(1) для нажатия или выталкивания.

Не забудьте проверить граничные условия (например, не позволяйте имpop() при first===last).

Учитывая, что JavaScript на самом деле использует плавающую точку двойной точности, вы должны иметь возможность запустить ~ 2 ^ 53 объектов через FIFO, прежде чем возникнут проблемы с целочисленной точностью.Таким образом, если вы выполняете 10000 элементов через FIFO в секунду, это должно быть хорошо в течение примерно 28 000 лет работы.

Answer 2

Исходя из ответа @SomeCallMeTim, который, я думаю, находится на правильном пути, у меня есть это:

export class Queue {

  lookup = new Map<number, any>();
  first = 0;
  last = 0;
  length = 0;
  elementExists = false; // when first === last, and item exists there

  peek() {
    return this.lookup.get(this.first);
  }

  getByIndex(v: number) {
    return this.lookup.get(v);
  }

  getLength() {
    return this.length;
  }

  pop() {

    const last = this.last;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.last > this.first) {
      this.length--;
      this.last--;
    }

    const v = this.lookup.get(last);
    this.lookup.delete(last);
    return v;
  }

  shift() {

    const first = this.first;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.first < this.last) {
      this.length--;
      this.first++;
    }

    const v = this.lookup.get(first);
    this.lookup.delete(first);
    return v;
  }

  push(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.last++;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.last++;
    }

    return this.lookup.set(this.last, v);

  }

  enq(v: any) {
    return this.push.apply(this, arguments);
  }

  enqueue(v: any) {
    return this.push.apply(this, arguments);
  }

  deq() {
    return this.shift.apply(this, arguments);
  }

  dequeue() {
    return this.shift.apply(this, arguments);
  }

  unshift(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.first--;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.first--;
    }

    return this.lookup.set(this.first, v);
  }

  addToFront(v: any){
    return this.unshift.apply(this,arguments);
  }

  removeAll() {
    return this.clear.apply(this, arguments);
  }

  clear(): void {
    this.length = 0;
    this.elementExists = false;
    this.first = 0;
    this.last = 0;
    this.lookup.clear();
  }

}

вынос :

1. оказывается, вы можете позвонить getByIndex(), как указывает предложение Тима.

2. Использование карты на удивление на ~ 10% быстрее, чем POJSO, возможно, только потому, что с POJSOцелые числа должны быть преобразованы в строки для поиска.

3. Реализация Map примерно на 20% быстрее, чем двусвязный список, поэтому двусвязный список не намного медленнее.Вероятно, это медленнее в основном потому, что мы должны создать контейнерный объект с указателями next / prev для каждого элемента в очереди, тогда как при реализации несвязанного списка мы можем вставлять примитивы в очередь и т. Д.

4. Двусвязный список позволяет нам удалять / вставлять элементы из середины очереди в постоянное время;мы не можем сделать то же самое с реализацией несвязанного списка, как есть.

5. Все вышеперечисленное на несколько порядков более производительно, чем обычный массив при работе с массивом с более чем 10 000элементов или около того.

У меня есть несколько реализаций очереди с постоянным временем здесь: https://github.com/ORESoftware/linked-queue

У Тима было хорошее предложение, чтобы сделать getByIndex () проще в использовании - мыможет сделать это:

  getByIndex(v: number) {

    if(!Number.isInteger(v)){
      throw new Error('Argument must be an integer.');
    }

    return this.lookup.get(v + this.first);
  }

таким образом, чтобы получить 5-й элемент в очереди, все, что нам нужно сделать, это:

getByIndex(4);

Answer 3

Если данные, которые вы храните, являются примитивными (строка, целые числа, числа с плавающей точкой или комбинации примитивов), вы можете использовать JavaScript TypedArray , привести его к соответствующему представлению типизированного массива, загрузить его с данными, а затем следите за смещением (ями).

В вашем примере pop, shift и unshift могут быть реализованы путем увеличения / уменьшения целочисленного индекса.push сложнее, потому что TypedArray имеет фиксированный размер: если ArrayBuffer заполнен, единственными двумя вариантами являются усечение данных или выделение нового типизированного массива, поскольку JS не может хранить указатели.

Если вы храните однородные объекты (они имеют одинаковые свойства), вы можете сохранить каждое значение в TypedArray, используя различные представления и смещения, чтобы имитировать структуру C (см. Пример MDN), а затем использовать функцию JS для сериализации / десериализации ихиз TypedArray, в основном преобразующей данные из двоичного представления, в полноценный объект JS.