Очередь с O (1) постановкой в ​​очередь и снятием с очереди с массивами JS

Если вы просто реализуете его с помощью .push() к .enqueue() и .shift() к .dequeue() это легко, но временная сложность .enqueue() равно O (1) и .dequeue() равно O (n).

Пока я все еще использую массивы, я придумал хорошее решение, позволяющее .enqueue() и .dequeue() в O (1). Я использую разреженные массивы. Оказывается суперэффективным, но только когда Queue размер больше 25000. Мои тесты такие;

Queue size 100
Queue: 0.12999999523162842
Array: 0.03999999910593033

Queue size 1000
Queue: 1.1049999967217445
Array: 0.5250000059604645

Queue size 10000
Queue: 3.0750000029802322
Array: 1.7799999937415123

Queue size 100000
Queue: 13.944999992847443
Array: 887.390000000596

ОК Queue становится намного быстрее, чем Array по мере роста размера, но я не могу сказать, что нужно улучшить, чтобы Queue не отстает Array в меньших масштабах. Есть ли что-нибудь, что вы можете предложить в приведенном ниже коде?

class Queue extends Array {
  constructor(){
    super();
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0;
  }
  peek() {
    return this[this.head];
  }
}

var p = Array(100000).fill().map(_ => ~~(Math.random()*1000)),
    q = p.reduce((r,e) => r.enqueue(e), new Queue());

var s,e;

s = performance.now();
for (i=0; i < 100000; i++){
  q.dequeue();
}
e = performance.now();
console.log("Queue:", e-s);

s = performance.now();
for (i=0; i < 100000; i++){
  p.shift();
}
e = performance.now();
console.log("Array:", e-s);

Редактировать:
После некоторого исследования теперь я понимаю, что то, что многим из нас сказали, на самом деле неверно. .shift() не O (n). Он был оптимизирован до O (1) много лет назад, и я думаю, что последними, кто оптимизировал, были ребята из Firefox в 2017 году. Вот ребята обсуждают, как реализовать оптимизацию, и оказывается, они делают то же самое, что я реализовал здесь. В отличие от меня они просто пропускают «delete «исключенного из очереди элемента», поскольку они пишут его на C ++ и могут перемещать указатель (head в приведенном выше коде), оставив освобожденные пробелы в GC. Но в JS мы должны delete их либо в каждом .dequeue() операция или ждать (this.length - this.head) > 50000 и сделать .splice(0,this.head) чтобы предотвратить утечку памяти. Это соответствует тому, что я вижу в Chrome и новом Edge (Chromium). До 50000 шт. .shift() работает O (1), но затем они переключаются на неоптимизированный код. В Firefox это, похоже, не так, как упоминалось в комментарий разработчика.

Вердикт:
Вы можете безопасно и просто реализовать эффективные Queues с .push() и .shift().

Обзор

Я считаю, что ваши отступы и разрывы строк довольно трудно читать.

Object.defineProperty(this,"head",{ value   : 0
                                  , writable: true
                                  });

Я бы посоветовал вам использовать идиоматический стиль.

После { перейти к следующей строке и сделать один отступ. Поместите запятую в конце строк и пробелы после запятых, если не в конце строки

Object.defineProperty(this, "head", { 
    value: 0,
    writable: true
});

или если линия короткая

Object.defineProperty(this, "head", {value: 0, writable: true});

или

Object.defineProperty(
    this, 
    "head", { 
        value: 0,
        writable: true
    }
);

То же самое и с троичными.

return this.head < this.length ? ( first = this[this.head]
                                 , delete this[this.head++]
                                 , first
                                 )
                               : void 0;

Зачем нужен оператор void что требует дополнительного выражения 0 когда ты можешь просто выразить undefined.

Я понимаю причину разделения группы, но отступ очень велик. Идиоматический стиль гораздо читабельнее.

return this.head < this.length ? ( 
        first = this[this.head],
        delete this[this.head++],
        first
    ) :                       
    undefined;                           

или

return this.head < this.length ?
    (first = this[this.head], delete this[this.head++], first) :                       
    undefined; 

Небезопасная инкапсуляция

Расширение Array с поведением enqueue и dequeue просто запрашивает ошибки, поскольку любая из существующих функций может повредить состояние.

Правила кода: «Если он есть, он будет использован».

Хороший код обеспечивает соблюдение правил, не раскрывая свойств и поведения, которые могут повредить состояние.

Даже простое использование Queue не заслуживает доверия, потому что вы разоблачаете head.

Очередь JS

Сложность и производительность — две стороны одной медали. Хотя они связаны, между ними есть большая разница. С участием shift в $ O (1) $ его производительность по-прежнему в 10 раз ниже, чем pop

Однако вы используете delete чтобы удалить предметы. Снова это $ O (1) $ но это даже медленнее, чем shift.

Связанный список

Я обнаружил, что простой связанный список является наиболее эффективным и производительным решением для очереди в JS.

Реализация его как фабричной функции позволяет замыканию сохранять свое состояние безопасно изолированным от кода с помощью очереди.

function Queue() {
    var head, tail;
    return Object.freeze({     
        enqueue(value) { 
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}

Этот стиль предлагает надежную герметизацию, поддерживает идеальный $ O (1) $ для enqueue и dequeue без ущерба для производительности.

Тестовое задание

Тест сравнивает время выполнения вашей очереди с версией очереди со связным списком.

Есть два цикла тестирования: сначала для 1000 элементов, затем, когда закончите, нажмите кнопку для 500 000 элементов.

Я внес небольшие изменения в ваш код, чтобы повысить производительность. Не использовать свойство define и не возвращать массив в очередь.

var size = 1000;
const COOL = 200;

class Queue extends Array {
  constructor(){
    super();
    this.head = 0;
  }
  enqueue(x) { this.push(x) }
  dequeue() {
    var first;
    return this.head < this.length ? 
        (first = this[this.head] , delete this[this.head++] , first) : 
        void 0;
  }
  peek() { return this[this.head] }
}

function QueueLinked() {
    var head, tail;
    return Object.freeze({     
        enqueue(value) { 
            const link = {value, next: undefined};
            tail = head ? tail.next = link : head = link;
        },
        dequeue() {
            if (head) {
                const value = head.value;
                head = head.next;
                return value;
            }
        },
        peek() { return head?.value }
    });
}


function fillQueue(queue, count = size) {
    while (count--) { queue.enqueue(count) }
    return queue;
}
function testOPQueue() {
    const q = fillQueue(new Queue());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}
function testLinkedQueue() {
    const q = fillQueue(QueueLinked());
    var ii = 0, val = 0;
    do {
        ii += val;
        val = q.dequeue();
    } while (val !== undefined);
    return ii;
}

if (testOPQueue() !== testLinkedQueue()) { throw new Error("Test results differ") }

const funcTest = (name, call, bias = 1) => ({name, call, time: 0, cycles: 0, bias});

timeFunctions(50, 500, "1000 items:",
    funcTest("Array Queue", testOPQueue),
    funcTest("Linked Queue", testLinkedQueue),
).then(() => {
    test2.classList.remove("hide");
    test2.addEventListener("click", () => {
        test2.classList.add("hide");
        size = 500000;
        timeFunctions(50, 3, "500,000 items:",
            funcTest("Array Queue", testOPQueue),
            funcTest("Linked Queue", testLinkedQueue),
        );
    });
});


function timeFunctions(testCount, cycles, name, ...functions) {
    return new Promise(done => {
        const testGroup = () => {
            var i;
            for (const func of functions) {
                i = cycles;
                const now = performance.now();
                while (i--) { func.call() }
                func.time += performance.now() - now;
                func.cycles += cycles;
            }
        }
        const test = () => {
            testGroup();
            console.clear();
            console.log(name + " " + (testCount - count + 1) + " of " + testCount);
            for (const func of functions) {
                console.log(
                    func.name.padEnd(maxNameLen + 2,".") + ": " + 
                    (((func.time / func.cycles) / func.bias).toFixed(3) + "ms").padStart(9," ") +
                    (" Total: " + func.time.toFixed(3) + "ms") 
                );
            }
            if (--count) { setTimeout(test, COOL) }
            else { done() }
        }
        var count = testCount;
        var maxNameLen = 0
        for (const func of functions) {
            func.time = 0;
            func.cycles = 0;
            maxNameLen = Math.max(maxNameLen, func.name.length);
        }
        setTimeout(test, COOL);
    });
}

.hide { display: none }

<button id="test2" class="hide">Test 500000 items</button>