在 JavaScript 中创建省略索引的数组结构

Question

数组中的索引（维护索引）使得 Array.prototype.shift 和 Array.prototype.unshift O(N) 而不是 O(1)。

但是，如果我们只想使用 pop() / push() / shift() 和 unshift() 而从不使用索引进行查找，有没有办法实现一个 JavaScript 数组来省略编制索引？

我想不出办法。我能想到的唯一方法是使用数组，并且只使用 pop() / push() （因为它们是 O(1)）...但即使有多个数组，也不确定是否可行。

想要做到这一点 w/o 如果可能的话，一个链表。 我用一个双向链表实现了一个解决方案，但想知道是否可以这样做这 w/o 一个链表。

最终目标： 尝试创建一个 FIFO 队列，其中所有操作都在恒定时间内进行，而不使用链表。

Answer 1

如果您要存储的数据是原始数据（字符串、整数、浮点数或原始数据的组合），您可以使用 JavaScript TypedArray，将其转换为适当的类型化数组视图，用数据加载它，然后自己跟踪偏移量。

在您的示例中，pop、shift 和 unshift 都可以通过 incrementing/decrementing 整数索引来实现。 push 比较难，因为 TypedArray 是固定大小的：如果 ArrayBuffer 已满，只有两个选择：截断数据，或者分配一个新的类型化数组，因为 JS 不能存储指针。

如果要存储同类对象（它们具有相同的属性），则可以使用不同的视图和偏移量将每个值保存到 TypedArray 中以模仿 C 结构（参见 MDN 示例），然后使用 JS 函数从 TypedArray 到 serialize/unserialize 它们，基本上将数据从二进制表示转换为成熟的 JS 对象。

Answer 2

用整数索引的 ES2015 Map 怎么样？

让我们调用地图myFIFOMap。

您将 first 和 last 整数成员保留为您的 FIFO class 的一部分。将它们都从零开始。

每次你想push()进入你的FIFO队列，你调用myFIFOMap.set(++last,item)。 pop() 看起来像：

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

应该是 O(1) 来推送或弹出。

不要忘记检查边界条件（例如，当 first===last 时不要让它们 pop()）。

鉴于 JavaScript 实际上使用双精度浮点数，您应该能够运行 ~2^53 objects 通过您的 FIFO，然后再遇到整数精度问题。因此，如果您运行每秒通过 FIFO 处理 10,000 个项目，那应该可以使用大约 28,000 年的运行时间。

Answer 3

按照@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();
  }

}

外卖:

事实证明，你可以调用 getByIndex()，正如 Tim 的建议所指出的那样。
使用 Map 比 POJSO 快约 10%，这可能只是因为使用 POJSO 需要将整数转换为字符串以供查找。
Map 实现比双向链表快大约 20%，因此双向链表并没有慢多少。它可能更慢，主要是因为我们必须为队列中的每个项目创建一个带有 next/prev 指针的容器对象，而使用非链表实现，我们可以在队列中插入基元等
双向链表允许我们在常数时间内从队列中间remove/insert项；我们不能对非链表实现做同样的事情。
当对超过 10,000 个元素的数组进行操作时，以上所有项的性能都比普通数组高几个数量级。

我这里有一些常量时间队列实现： https://github.com/ORESoftware/linked-queue

Tim 有一个很好的建议，让 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);

在 JavaScript 中创建省略索引的数组结构

Create array structure in JavaScript that omits indexing

javascript

arrays

time-complexity

node.js

constant-time