Цитата:
Предполагаем, что pool организован как Map (<id> => <запрос>) c инкрементными идентификаторами. Вводится дополнительная структура данных (Map вполне подойдет). Ключом являются имена участников, которые в настоящее время стоят в очереди. Значениями - список (Set наверно подойдет) идентификаторов запросов в очереди с этим участником. Когда запрос ставится в очередь, мы вносим информацию об этом в эту структуру. Когда какой то запрос завершается, мы не только удаляем участников из набора buffer, но берем с нашей структуры участников информацию об участниках завершившегося запроса. Берем их наборы идентификаторов запросов, стоящих в очереди, и по ним просматриваем именно эти запросы на возможность выполнения, а не всю очередь. Ну как то так. |
Вообще это все надо проверять на практике.
Выяснять, насколько большая очередь скапливается в реальных условиях. Растет она, стабилизируется или пульсирует. Если там 100-300 элементов и ее просмотр занимает считанные миллисекунды, то стоит ли огород городить. |
Цитата:
|
Ну я писал эти тесты, просто для себя. И сравнивал в основном скорость реализации очереди в виде списка, по сравнению с 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>
|
nset 43228
Заполнение pool 93 100000 Заполнение map 41 100000 Удаление pool 19 81202 Удаление map 40 81297 |
Цитата:
Исходя из вышеперечисленного — что вы имеете ввиду под pool и map и что означают цифры? |
рони, И что?
Вообще я сам не понимаю, что я тестировал. Я удалял слишком много записей. В реальности после исполнения какого то запроса <X op Y> может быть удалено максимум 2 записи. Как только мы удаляем какую то запись <X op P>, этот запрос отправляется на исполнение, X помещается в буфер и дальнейшие запросы с X уже не могут исполняться, и соответственно записи не будут удаляться. Тоже самое и про Y. Другие записи удалены быть не могут, т.к запросы с ними еще не закончились, иначе они не были бы в очереди. |
Цитата:
Это просто разные реализации очереди. |
Цитата:
37 - мс на выполнение просмотра очереди из 100000 элементов и удаления какого то количества. 81418 - количество оставшихся элементов. Я писал, что эти тесты я делал вчера для себя. |
Цитата:
|
| Часовой пояс GMT +3, время: 08:17. |