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

[webgraph]

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

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

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

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

[webgraph]

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

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

[voraa]

А если представить, что попросту нет возможности

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

[webgraph]

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

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

[voraa]

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

[Alexandroppolus]

можно еще было бы придумать списки для каждого члена и т.п.

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

[voraa]

Такой вариант позволит быстро находить одну или две новые задачи под выполнение,

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

[Alexandroppolus]

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

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

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

[webgraph]

надо будет смотреть два маленьких списка для освободившихся участников

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

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

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

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

[webgraph]

может быть много задач на одни и те же пары участников

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

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