Очередь с 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().

1 ответ
1

Обзор

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

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>

  • Большое спасибо за ваше время, потраченное на этот ответ. Что касается отступов, это мой стиль, и я буду его придерживаться. Я даже купил для этого сверхширокий монитор. Если привыкнуть к широким отступам, назад уже не вернуться. Для меня это то, как следует писать код. Также спасибо за head выставленная часть. В окопе солдаты не должны обнажать голову, да? ..? Я согласен и могу исправить это при расширении массива. Расширение массива избавляет меня от реализации многих функций, таких как .map(). Почему бы вам не захотеть, чтобы ваш тип Queue был функтором бесплатно? Однако по производительности ->

    – Все в порядке

  • когда я delete то dequeued, да, за это приходится платить. Но я могу отложить это на более поздний этап. Тем не менее … я бы смиренно посоветовал вам протестировать ваш код на простом массиве, используя .shift() вместо того dequeue при разумных размерах ниже 10000. Посмотрим, как получится. Проголосовали за усилия.

    – Все в порядке


Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *