代码之家 › 专栏 › 技术社区 › Alexander Mills

O(1)删除JavaScript队列

queue hashmap hash node.js javascript

Alexander Mills · 技术社区 · 6 年前

我可以在队列中添加常量/O?现在我有一个简单的数组作为队列,但是要找到要删除的元素,我必须遍历数组,然后调用 Array.prototype.splice

Array.prototype.shift Array.prototype.unshift ,它们都是O(N),因为它们必须更新数组中每个项的索引。

因此,我希望在列表/队列中的任何位置都能以恒定的时间插入/删除元素。如果试图将普通数组放入FIFO队列,那么普通数组似乎不会产生这种结果。

1 回复 | 直到 6 年前

Alexander Mills 6 年前

我已经考虑了一段时间,我能想到的就是一个双重链接的列表。双链接列表允许我们在固定时间内添加/删除队列中的项目。

请参阅此处的答案:

https://www.quora.com/How-can-I-create-a-queue-in-JavaScript-where-I-can-search-for-or-remove-elements-in-near-O-1-time-Right-now-I-have-a-simple-array-as-a-queue-but-to-find-an-element-to-delete-I-have-to-go-through-the-array-and-then

下面是一个似乎有效的实现:

https://github.com/ORESoftware/linked-queue

一个简单的例子说明了这一点,对于一个数组,每个shift/unshift调用都是O(N),因此下面的操作需要80秒!

const values = [];

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  values.unshift({});
}

console.log('total time:', Date.now() - t); // 80 seconds!

const {LinkedQueue} = require('@oresoftware/linked-queue');

const q = new LinkedQueue();

const t = Date.now();

for (let i = 0; i < 100000; i++) {
  q.addToFront({});
}

console.log('total time:', Date.now() - t);  // 60 milliseconds!

推荐文章