Ну я писал эти тесты, просто для себя. И сравнивал в основном скорость реализации очереди в виде списка, по сравнению с map.
Попробуйте разобраться
<body>
<script>
function canExec(op) {
return op.v % 2;
}
function exec(op) {}
class CPoolItem {
next = null;
prev = null;
operation;
constructor(operation) {
this.operation = operation;
}
}
class CPool {
first = null;
last = null;
size = 0;
constructor() {}
// добавить в конец
add(item) {
this.first ??= item;
item.prev = this.last;
if (this.last) this.last.next = item;
this.size++;
this.last = item;
}
// удалить item
delete(item) {
const next = item.next;
const prev = item.prev;
if (!prev) this.first = next;
else prev.next = next;
if (!next) this.last = prev;
else next.prev = prev;
this.size--;
return this;
}
// последовательно просмотреть pool, выполняя операции, какие возможно.
view() {
let item = this.first;
while (item) {
if (canExec(item.operation)) {
exec(item.operation);
this.delete(item);
}
item = item.next;
}
}
values() {
const _this = this;
return (function* () {
let item = _this.first;
while (item) {
yield item;
item = item.next;
}
})();
}
}
const pool = new CPool();
const map = new Map();
let inckey = 0;
const nr100 = () => Math.round(Math.random() * 100_000);
const genKeys = n => {
const keys = [];
while (n--) {
const nkey = nr100();
const key = ('' + nkey).padStart(6, '0');
keys.push(key);
}
return keys;
};
const N = 100_000;
let t0;
const keys = genKeys(N);
const buffer = new Set();
// Заполняем buffer из массива имен пользователей keys по принципу
// Если имени нет в buffer оно туда заносится
// Если именя есть в buffer оно оттуда удаляется
for (let i = 0; i < N; i++) {
key = keys[i];
if (!buffer.has(key)) buffer.add(key);
else buffer.delete(key);
}
const nseta = buffer.size;
// Проверяем может ли быть выполнен запрос op
function canExec(op) {
return !(buffer.has(op.u1) || buffer.has(op.u2));
}
// Выполняем запрос op
function exec(op) {}
// Тестируем скорость заполнения очереди в 100_000 элементов
// Заполняем pool случайно сгенрированными записями {u1:, u2:}
t0 = performance.now();
for (const key of keys) {
const u1 = keys[nr100()];
const u2 = keys[nr100()];
pool.add(new CPoolItem({ u1, u2 }));
}
const taddpool = performance.now() - t0;
const np = pool.size;
// Заполняем map случайно сгенрированными записями id => {u1:, u2:}
t0 = performance.now();
for (const key of keys) {
const u1 = keys[nr100()];
const u2 = keys[nr100()];
map.set(++inckey, { u1, u2 });
}
const taddmap = performance.now() - t0;
const nm = map.size;
// Тестируем скорость удаления записей из очереди в 100_000 элементов
// Из pool удаляются элементы {u1, u2}, если u1 и u2 не присутствуют в buffer
t0 = performance.now();
pool.view();
const tdelpool = performance.now() - t0;
// Из map удаляются элементы {u1, u2}, если u1 и u2 не присутствуют в buffer
t0 = performance.now();
for (const [key, value] of map.entries())
if (canExec(value)) {
exec(value);
map.delete(key);
}
const tdelmap = performance.now() - t0;
console.log('nset', nseta);
console.log('Заполнение pool', taddpool.toFixed(0), np);
console.log('Заполнение map', taddmap.toFixed(0), nm);
console.log('Удаление pool', tdelpool.toFixed(0), pool.size);
console.log('Удаление map', tdelmap.toFixed(0), map.size);
</script>
</body>