Как добавить элемент в отсортированный массив?

[voraa]

Хотя, если порядок выполнения запросов имеет значение, то просмотр простой очереди тоже не спасает.
Допустим в очереди стоят
С-А, С-Б, Б-Д. (С и Д свободны)
Освободились А и Б.
Просматривая очередь и беря С-А, мы не сможем потом взять С-Б, но возьмем Б-Д. А это не правильно. С-Б должен быть взят раньше.

[Alexandroppolus]

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

да, ещё 1-2 других очередей. Но это всё же не совсем "просмотр очереди", а только лишь головы ея.

[Alexandroppolus]

Просматривая очередь и беря С-А, мы не сможем потом взять С-Б, но возьмем Б-Д. А это не правильно. С-Б должен быть взят раньше.

ага. С общей очередью реализовывать строгий порядок будет сложнее

[voraa]

ага. С общей очередью реализовывать строгий порядок будет сложнее

Просто дольше. Там придется еще вести множество (Set) тех участников, которые уже встретились в очереди. Т.е проверять не только, тех, что уже исполняются, а еще и тех, что раньше в очереди, но не могут исполняться.

[webgraph]

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

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

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

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

Alexandroppolus, voraa,

Получается, когда какая-либо операция между <Петя> и <Вася> выполнена — мы проверяем pool на наличие ключей только с их именем, вместо того, чтобы проверять единый список от начала до конца.

Только непонятно как проводить выполнение операции в таком случае:

1. Выполняется операция <Петя> передает <Васе> 5 бочек апельсинов — а этот момент они находятся в buffer.

const buffer = new Set();

buffer.add('Петя');
buffer.add('Вася');

2. Пока эти 5 бочек транспортируются, <Вася> решил 1 бочку апельсинов передать <Мише> и 1 бочку <Кате>.

const pool = new Map();

//при условии, что Васи вообще нет в pool
pool.set('Вася', [
{
action: 'Отправить 1 бочку апельсинов',
to: 'Миша'
},
{
action: 'Отправить 1 бочку апельсинов',
to: 'Катя'
}
]);

pool.set('Миша', [{
action: 'Отправить 1 бочку апельсинов',
from: 'Вася'
}]);

//а вот Катя уже сидит в пуле, например
let KatyaTasks = pool.get('Катя');
KatyaTasks.push({
action: 'Отправить 1 бочку апельсинов',
from: 'Вася'
});
pool.set('Катя', KatyaTasks);

3. Когда операция между <Петя> и <Вася> завершается, то они удаляются из buffer и их имена начинают искаться в pool.

buffer.delete('Петя');
buffer.delete('Вася');

/* а дальше-то как? */

[voraa]

const buffer = new Set();
 
const pool = new Map();

// Допустим выполнялся запрос

const req0 = {from:"Петя", to: "Вася", action:"5 бочек апельсинов"}
// В buffer было добавлено
buffer.add('Петя');
buffer.add('Вася');

// Теперь приходит запрос
// <Вася> решил 1 бочку апельсинов передать <Мише>

const req1 = {from:"Вася", to: "Миша", action:"1 бочек апельсинов"}

// Выясняем есть "Вася" или "Миша" в buffer (Вася есть)
// Если есть то записываем обоих в pool
// Здесь я использую массивы, но лучше нормальную списковую очередь

if (inBuffer(req1.from) || inBuffer(req1.to)) {
	if (!pool.has(req1.from)) pool.set(req1.from, [])
	pool.get(req1.from).push(req1)
	if (!pool.has(req1.to)) pool.set(req1.to, [])
	pool.get(req1.to).push(req1)
}

// Теперь приходит запрос <Вася> решил 1 бочку апельсинов передать <Катя>

const req2 = {from:"Вася", to: "Катя", action:"1 бочек апельсинов"}

// Выясняем есть "Вася" или "Катя" в buffer (Вася есть)
// Если есть то записываем обоих в pool

if (inBuffer(req2.from) || inBuffer(req2.to)) {
	if (!pool.has(req2.from)) pool.set(req2.from, [])
	pool.get(req2.from).push(req2)
	if (!pool.has(req2.to)) pool.set(req2.to, [])
	pool.get(req2.to).push(req2)
}

// В пуле у нас
// Вася => [req1, req2]
// Миша => [req1]
// Катя => [req2]

// Теперь заканчивается запрос req0 = {from:"Петя", to: "Вася", action:"5 бочек апельсинов"}
// Петя и Вася удаляются из буфера
buffer.delete('Петя');
buffer.delete('Вася');

Раз запрос закончился мы проверяем есть ли запросы с Петя и Вася в pool
C Петя - нет.
Берем в пуле у Вася первый запрос
это req1 = {from:"Вася", to: "Миша", action:"1 бочек апельсинов"}
Тут мы должны определить второго участника запроса. Это Миша.
Проверяем Миша в buffer
Если нет, смотрим первый запрос в пуле у Миши
Если это ТОТ ЖЕ запрос, (req1 === req1), то он может быть отправлен на выполнение.
Но сначала удалим его из пулов для Вася и Миша
При этом, если очередь участника пуста, то надо удалить и самого участника из пула

И дальше все в событийных циклах. Пришел запрос - либо на выполнение, либо в пул
Завершился запрос - смотрим в пуле есть ли еще запросы с этими участниками и могут ли они быть исполнены

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

[Alexandroppolus]

Единственное, что мне кажется, когда приходит запрос, мы должны проверять участников не только в buffer (запросы с ними выполняются и еще не закончены), но и в pool

Это если всё-таки требуется строгая очередность выполнения запросов для каждого участника. Я такую схему расписал тут.

Строгая очередность во всём хороша, но добавляет дополнительные ожидания.

По мнению автора топика, это не требуется, если я правильно понял.

[voraa]

Строгая очередность во всём хороша, но добавляет дополнительные ожидания.

Иначе получается "не строгая", но очередность
При поступлении запроса очередности нет, а при поиске запроса в пуле, очередность возникает, когда мы не можем выполнить запрос с участним, т.к перед ним стоит другой запрос

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

Б-Д точно не берём, она должна быть после Б-С.

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

[Alexandroppolus]

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

Само собой. Об этом тоже говорилось ранее.