d23r4t5y6u7i8

Benchmark created by artalar on January 8, 2020

Setup

const createQueue = () => {
    const queue = new Map();
    let min = 0;
    let max = 0;
    return {
      insert(priority, el) {
        let part = queue.get(priority);
        if (!part) queue.set(priority, (part = []));
        if (!part.includes(el)) {
          part.push(el);
          min = Math.min(min, priority); // useful only for cycles
          max = Math.max(max, priority);
        }
      },
      extract() {
        let part = queue.get(min);
        while (!part || !part.length) {
          if (min === max) return;
          part = queue.get(++min);
        }
        return part.shift();
      }
    };
  };
  
  class Queue {
    constructor() {
      this.min = 0;
      this.max = 0;
      this.queue = new Map();
    }
    insert(priority, el) {
      let part = this.queue.get(priority);
      if (!part) this.queue.set(priority, (part = []));
      if (!part.includes(el)) {
        part.push(el);
        this.min = Math.min(this.min, priority); // useful only for cycles
        this.max = Math.max(this.max, priority);
      }
    }
    extract() {
      let part = this.queue.get(this.min);
      while (!part || !part.length) {
        if (this.min === this.max) return;
        part = this.queue.get(++this.min);
      }
      return part.shift();
    }
  }
  
  const createEl = () => ({ value: Math.random() });
  
  const qObj = createQueue();
  const qCls = new Queue();
  const el1 = createEl();
  const el2 = createEl();
  const inserts = [
    [0, createEl()],
    [2, createEl()],
    [2, createEl()],
    [2, createEl()],
    [3, createEl()],
    [4, el2],
    [4, el2],
    [4, createEl()],
    [5, createEl()],
    [5, 2],
    [5, 2],
    [6, createEl()],
    [11, createEl()],
  ];

Test runner

createQueue()

new Queue()

inserts.forEach(a => qObj.insert(...a));
let c;
while ((c = qObj.extract())) 0;

inserts.forEach(a => qCls.insert(...a));
let c;
while ((c = qCls.extract())) 0;

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by artalar on January 8, 2020