2

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

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

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

如果可能的话，希望使用 oa 链表来执行此操作。我用双链表实现了一个解决方案，但想知道是否可以用 oa 链表来做这个。

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

4

3 回答 3

1

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

让我们调用地图myFIFOMap。

您保留一个整数成员作为 FIFO 类的一部分first。last从零开始它们。

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

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

应该是O(1)push或者pop。

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

鉴于 JavaScript 实际上使用双精度浮点，在整数精度出现问题之前，您应该能够通过 FIFO运行~2^53 个对象。因此，如果您每秒通过 FIFO 运行 10,000 个项目，这对于大约 28,000 年的运行时间应该是有益的。

于 2018-06-04T22:34:03.133 回答
0

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

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

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

于 2018-06-04T22:10:57.277 回答
0

与@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. 使用 Map 比 POJSO 快约 10%，这可能只是因为使用 POJSO 需要将整数转换为字符串以进行查找。

  3. Map 实现比双向链表快约 20%，因此双向链表并没有那么慢。它可能更慢，主要是因为我们必须为队列中的每个项目创建一个带有 next/prev 指针的容器对象，而使用非链表实现，我们可以在队列中插入原语等。

  4. 双向链表允许我们在恒定时间内从队列中间删除/插入项目；我们不能对非链表实现做同样的事情。

  5. 当对具有超过 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);
于 2018-06-04T23:13:29.350 回答