Форум

voraa · #**101** (**permalink**) 07.01.2023, 10:45

Сообщение от webgraph

Или у вас вообще иная логика подразумевается? (если да, то какая?)

Все это делается для того, что бы избежать просмотра длинной очереди (pool), а просматривать только те записи, участники которых только что освободились.
Предполагаем, что pool организован как Map (<id> => <запрос>) c инкрементными идентификаторами.
Вводится дополнительная структура данных (Map вполне подойдет). Ключом являются имена участников, которые в настоящее время стоят в очереди. Значениями - список (Set наверно подойдет) идентификаторов запросов в очереди с этим участником.
Когда запрос ставится в очередь, мы вносим информацию об этом в эту структуру.
Когда какой то запрос завершается, мы не только удаляем участников из набора buffer, но берем с нашей структуры участников информацию об участниках завершившегося запроса. Берем их наборы идентификаторов запросов, стоящих в очереди, и по ним просматриваем именно эти запросы на возможность выполнения, а не всю очередь.

Ну как то так.

voraa · #**102** (**permalink**) 07.01.2023, 10:55

Вообще это все надо проверять на практике.
Выяснять, насколько большая очередь скапливается в реальных условиях. Растет она, стабилизируется или пульсирует.
Если там 100-300 элементов и ее просмотр занимает считанные миллисекунды, то стоит ли огород городить.

webgraph · #**103** (**permalink**) 07.01.2023, 11:00

Сообщение от voraa

Я тесты провел.
Просмотр очереди из 100_000 записей с удалением половины (все четные, например) занимает 15-40 мс даже на моем довольно старом AMD
Я сравнивал свою реализацию со списком и реализацию через map.
Результаты разнятся от теста к тесту. То список чуть быстрее, то map.

Раз вы тестировали, можете показать вашу реализацию с Map?)

voraa · #**104** (**permalink**) 07.01.2023, 11:32

Ну я писал эти тесты, просто для себя. И сравнивал в основном скорость реализации очереди в виде списка, по сравнению с 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>

рони · #**105** (**permalink**) 07.01.2023, 12:07

nset 43228
Заполнение pool 93 100000
Заполнение map 41 100000
Удаление pool 19 81202
Удаление map 40 81297

webgraph · #**106** (**permalink**) 07.01.2023, 12:20

Сообщение от рони

nset 43228
Заполнение pool 93 100000
Заполнение map 41 100000
Удаление pool 19 81202
Удаление map 40 81297

Причем здесь pool и map?) У нас есть 2 сущности — buffer и pool. Buffer мы решили на данном этапе с помощью Set() сделать. Pool — хранилище ключ-значение, где ключом является автоинкремент ID, а значением — объект, состоящий из 2-х участников и описания операции. Pool на данном этапе реализован в виде List и Map.

Исходя из вышеперечисленного — что вы имеете ввиду под pool и map и что означают цифры?

voraa · #**107** (**permalink**) 07.01.2023, 12:21

рони, И что?

Вообще я сам не понимаю, что я тестировал. Я удалял слишком много записей. В реальности после исполнения какого то запроса <X op Y> может быть удалено максимум 2 записи.
Как только мы удаляем какую то запись <X op P>, этот запрос отправляется на исполнение, X помещается в буфер и дальнейшие запросы с X уже не могут исполняться, и соответственно записи не будут удаляться. Тоже самое и про Y.
Другие записи удалены быть не могут, т.к запросы с ними еще не закончились, иначе они не были бы в очереди.

voraa · #**108** (**permalink**) 07.01.2023, 12:23

Сообщение от webgraph

У нас есть 2 сущности — buffer и pool.

Я же писал, что я тестировал очередь реализованную как список (назвал pool) и через Map и инкрементным ключом (назвал map)
Это просто разные реализации очереди.

voraa · #**109** (**permalink**) 07.01.2023, 12:27

Сообщение от webgraph

и что означают цифры?

Удаление pool 37 81418
37 - мс на выполнение просмотра очереди из 100000 элементов и удаления какого то количества.
81418 - количество оставшихся элементов.

Я писал, что эти тесты я делал вчера для себя.

рони · #**110** (**permalink**) 07.01.2023, 13:09

Сообщение от voraa

рони, И что?

просто результат тестирования, на всякий случай.

Форум

Справочник

Discord чат

Курсы javascript