Для перебора коллекции Map есть 3 метода:

map.keys() – возвращает итерируемый объект по ключам,
map.values() – возвращает итерируемый объект по значениям,
map.entries() – возвращает итерируемый объект по парам вида [ключ, значение], этот вариант используется по умолчанию в for..of.

let recipeMap = new Map([
  ["огурец", 500],
  ["помидор", 350],
  ["лук",    50]
]);

// перебор по ключам (овощи)
for (let vegetable of recipeMap.keys()) {
  alert(vegetable); // огурец, помидор, лук
}

// перебор по значениям (числа)
for (let amount of recipeMap.values()) {
  alert(amount); // 500, 350, 50
}

// перебор по элементам в формате [ключ, значение]
for (let entry of recipeMap) { // то же самое, что и recipeMap.entries()
  alert(entry); // огурец,500 (и так далее)
}

А зачем их искать, если массив по итогу каждый раз перебирается от начала до конца?

Вся реализация со списком Не отлаживал, конечно, но как то так

class CPoolItem {
    next = null;
    prev = null;
    operation;

    constructor (operation) {
        this.operation = operation;
    }
}

class CPool {
    first = null;
    last = null;
    constructor () {}

    // добавить в конец
    add (item) {
        this.fist ??= item;
        item.prev = this.last;
        if (this.last) 
            this.last.next = item;
        this.last = item;
        return this;
    }

    // удалить 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;
        return this;
    }
    // последовательно просмотреть pool, выполняя операции, какие возможно.
    view () {
        let item = this.first;
        while (item) {
            if (canExec(item.operation)) {
                exec (item.operation);
                this.delete(item)
            }
            item = item.next
        }
    }
}

const pool = new CPool();

// Когда поcтупила новая операция делаем
poll.add(new CPoolItem(operation));
pool.view();

// Когда какая то операция выполнилась удаляем участников из буфера и делаем
pool.view();

// canExec(operation) проверяет, что участников операции нет в буфере
// exec (operation) добавляет участников в буфер и отправляет операцию на исполнение.

Что-то здесь вообще ничего не понятно...

С каким списком?) Я не понимаю во что именно добавляется. Это массив, объект, мап?)

Простая работа с двунаправленным списком.
operation - некий объект, который мне точно не известен, но он описывает операцию, которую надо выполнить. От кого, кому, что ....
operation оборачивается в CPoolItem. Это айтем нашего пула.
new CPoolItem(operation)
Сам пул задается классом CPool.
в нем определены методы add - добавление айтема в конец пула,
delete - удаления айтема из пула
и view последовательный просмотр пула с выполнением операций, которые на данный момент возможны.

Ну список это обычная структура данных.
Есть всякие очереди, деревья, списки...
В них элементы располагаются не последовательно, как в массиве, а где угодно, но связаны между собой указателями.
В двунаправленных списках у каждого элемента есть указатели на предыдущий элемент (prev) и следующий (next).
В самом заголовке списка есть указатели на первый (first) и последний (last)
Обычный список

А в чем конкретно преимущество этого списка по сравнению с тем же Map?) Как этот список экспортировать и импортировать?

Ну если только такой перебор с инкрементным ключом, то наверно и Map подойдет.

Т.е. почти всегда очередь будет пустая?

Это хорошо, но могут возникать какие-либо тормоза в обработке запросов. В этом случае в очереди накопится много элементов. Если длина очереди равна N, то разгребать её надо будет за время примерно N*N/2 (просмотр всей очереди после завершения каждой операции). И это может стать проблемой.

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

Ну вот о чем-то подобном и приходили мысли, после чего появилась идея вообще отказаться от этого списка очереди и просто через setTimeout проверять доступность выполнения запроса (в случае если он сразу не выполнился), что, как выяснилось, тоже может привести к негативным последствиям.

У вас есть идеи?)

А если представить, что попросту нет возможности использовать списки/мапы и тому подобное. Как бы тогда это могло разрешаться?)

Трудно представить. Список можно сделать всегда и на чем угодно.
А всякие варианты с timeout мне не нравятся из-за непонятно какого подбора времен. А если ситуация хоть временно изменится, то эти подобранные для среднего случая времена будут ни на что не годится.

Ну, имелось ввиду и не списки, и не timeout. Потому что с timeout мне тоже до конца не нравится. Это как long-polling вместо websocket

Тут такая ситуация.
Приходят запросы. Некоторые запросы не могут быть сразу выполнены. Что с ними делать? Варианта 2:
1 - отправлять отказ клиенту, сейчас не могу, попробуй снова прислать запрос позже. Не самый лучший вариант, т.к. может случиться так, что клиент долго и много раз посылать свой запрос.
2 - хранить такие запросы на сервере до тех пор пока они не смогут быть исполнены.
Осталось продумать реализацию такого хранилища. Должна быть возможность помещать туда запрос. И просматривать запросы, что бы выяснить какие могут быть исполнены. И удалять запросы, которые отправляются на выполнение.
Как реализовать такое хранилище можно долго рассуждать. Очередь напрашивается как бы сама собой (ну не совсем очередь "первый пришел - первый обслужен".
Хотелось бы, что бы запросы там не застревали надолго. Т.е не было ситуации, что какой то запрос там долго находится, хотя позже пришедшие запросы с этими же пользователями уже выполнились. Для этого из множества запросов, которые могут быть выполнены в данный момент, первыми надо выбирать те, которые раньше пришли.
Вот такое должно быть хранилище. Как его называть - списком или еще как не суть. Вот как реализовывать действительно стоит думать
Я придумал списки, вы map. И то и то работает и примерно одинаково по времени. Где и как можно оптимизировать время просмотра - не очень понятно. Если бы надо было там искать каких то определенных членов операций. можно еще было бы придумать списки для каждого члена и т.п. Только боюсь, что таких списков будет слишком много, и работа с ними не слишком оптимизирует, т.к их тоже надо как то просматривать. Но нам приходится искать и запросы, членов которых нет в буфере. Как это оптимизировать - совсем не понятно.
В любом случае, если за единицу времени постоянно приходит больше запросов, чем может быть обработано за это же время - любое хранилище будет расти. И тут уже надо думать, не о том, как его организовать, а как увеличить количество запросов обрабатываемых в единицу времени.
Ну или уменьшать количество запросов - давать отказ клиенту если количество необработанных запросов в хранилище превышает определенную величину. Так и говорить "система перегружена, попробуй минут через 10 (20, 30)"

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

Тогда хранить и вести списки для участников, которые находятся в буфере, и тех, которые в очереди. Удалять пустые списки. Просматривать эти списки.
Это же тоже работа.

voraa,
это копеечная работа, которая не зависит от размера очереди. Зато вместо одного большого списка для всех, надо будет смотреть два маленьких списка для освободившихся участников. А если таки понадобится соблюдать очередность действий для каждого участника, бонусом имеем быструю проверку на присутствие в очереди.

Если различных участников много, то выигрыш весьма изрядный.

А если мало, но может быть много задач на одни и те же пары участников, то можно добавить в персональные списки ещё группировку по партнеру. Впрочем, пока нет смысла упарываться до такой степени..

Что-то я догнать не могу логику... Можете попунктно описать порядок действий?)

Вот начало:
1. На сервер приходит запрос <Петя> хочет передать <Васе>
2. Проверяем Петю и Васю в buffer
3. Если хотя бы один есть в buffer, то ...

[... что дальше должно быть исходя из ваших маленьких списков?]

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

/*
 *
 Ситуация, когда большое множество различных участников хотят провести операцию с участником <X> — очень актуальная. 
 *
 */

И исходя из ваших маленьких списков непонятно как участнику X что-то сделать в промежутке этих бесчисленных операций. В примере с 1 списком это понятно — операция вставляется в очередь и при достижении выполняется. А как это делается в вашем случае?

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

Ну как то так.

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

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

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

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

рони, И что?

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

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

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

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

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

Я бы чуть по-другому сделал:
pool - это Map, где ключём будет участник, а значением - двусвязный список задач, связанных с участником. Большой общий список всё равно не нужен. Когда приходит новая задача, она просто добавляется в списки к обоим участникам (если не может выполниться прямо сейчас, т.е. кто-то из двух занят).

Когда участников много (всего М), то оптимизация очень хорошая: если задачи распределены более-менее равномерно, то имеем дело со списками, которые меньше полного списка в М раз. Ну а если оказалось, что почти все задачи завязаны на какого-то одного участника Х, то по нему выстроится длинный список, зато все прочие будут почти всегда свободны, и нам не придется долго искать задачу в этом длинном списке.

Долгие проходы по списку будут, но в редких случаях.

Итого: довольно простая оптимизация, которая охватывает почти все кейсы.

Когда выполнился запрос с участниками X-Y, мы должны искать по X и по Y запросы, которые могут быть выполнены.
По X находим X-P, по Y находим Y-Q.
Какой взять на выполнение?
Если всегда брать по первому имени, не получится так, что много запросов ?-Y и запросы с Y-? , будут слишком долго сидеть в этом пуле?
Допустим решили взять X-P. Его надо удалить из списка X.
Но список P тоже надо просмотреть и удалить именно этот запрос

Оба. Потому что обе эти задачи просто ждали, когда освободятся участники.

Да, надо удалить. Но в объекте с задачей можно хранить ссылки на узлы списков, в которых она хранится, а имея на руках такую ссылку, узел удаляется без его поиска в списке, за О(1).

По X находим P-X, по Y находим Y-P.
Запрос Y-P пришел раньше. Y что то передает P, потом запрос P что то передает Х Они и исполняться должны сначала Y-P, потом P-X. Оба взять не получится и там и там P.

Значит Р-Х пока что в пролёте, ищем дальше по списку для Х, с учётом того, что Р теперь занят.

А если бы вместо Y-P был Y-Х, то дальнейшего поиска по списку Х вообще не надо.

Но я так понял со слов автора топика, очередность выполнения действий для конкретного участника не особо важна. Иначе все получается даже проще:

- когда прилетает новая задача А-В, проверяем что А и В нет в выполняемых и их списки ожидания пусты - в этом случае сразу стартуем задачу, иначе добавляем в обе очереди.

- по завершении задачи А-В смотрим только начала списков для А и В. Там видим, например, А-С и В-Д, которые запускаем, только если С и Д свободны, а оные задачи находятся в голове списков для С и Д.

В этой схеме всё отстреливает за наше любимое О(1)

Всякие ситуации могут быть.
Завершился запрос А - Б.
В очереди у А: С-А (С свободно), у Б: Б-С и Б-Д (Д свободно)
Мы берем С-А, (Б-С уже нельзя взять) (а почему именно С-А, а не Б-С? может Б-С пришел раньше, но вынужден ждать), а Б-Д не возьмем, т.к весь список Б мы не просматриваем

Вообще, Очередь на 10_000 элементов просматривается (с выяснением свободны ли элементы ища их в Set) за 3-4мс.
Мое мнение, что если очередь сильно больше, то дело не во времени просмотра очереди. Значит запросов сильно больше, чем время их обработки, И оптимизировать надо не очередь, а обработку.

Б-Д точно не берём, она должна быть после Б-С.
Из С-А и Б-С запустим ту задачу, которая первая в очереди для С. Если там какая-нибудь С-Д, то ничего не запускается в этот раз.

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

Т.е при освобождении А и Б мы должны не только их очереди просматривать, но и какие то другие?