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

[webgraph]

mid = low + Math.floor( ((t-A[low])*(high-low))/(A[high]-A[low]) )

Походу никак...

[Alexandroppolus]

Какой то парадокс. Безумно долго идет заполнение неотсортированного массива. В разы дольше, чем удаление из него же. Не могу понять почему.

у тебя там на 115 строке баг:

if (!ind>=0)

лишний "!"

в итоге условие всегда истинное, даже когда ind === -1. В этих случаях splice мгновенно, за O(1), удаляет последний элемент. Массив стремительно уменьшается, последующие итерации отрабатывают быстрее.

Если поправить баг, то всё норм.

[Alexandroppolus]

С деревьями тоже не все так просто. Если ключи добавляются в достаточно случайном порядке, то все хорошо. Если же много ключей добавляется в возрастающем порядке, то дерево получается не сбалансированным и поиск по нему уже совсем не log2(N). И большого эффекта дерево не даст.

для этого давным-давно придуманы самобалансирующиеся деревья. Красно-черное, АВЛ, и т.д.

[voraa]

у тебя там на 115 строке баг:

И действительно.
Исправил.

для этого давным-давно придуманы самобалансирующиеся деревья. Красно-черное, АВЛ, и т.д.

Все зависит от работы с этим деревом. Когда мы говорим про O(log2N), то мы оцениваем количество операций сравнений при поиске в дереве. Когда работа - часто-часто ищем и иногда добавляем/удаляем, то все хорошо.
Когда работа - найти, если нашли удалить, если не нашли добавить - то самобалансировка будет происходить очень часто. А она тоже требует времени. А если сравнивать время на операцию сравнения, и время на балансировку, то не понятно сильно ли большим будет выигрыш.

[Alexandroppolus]

voraa,
балансировка - накладные расходы, это да. Но она занимает по времени не более O(ln(n)), т.е. на больших объемах это всё равно копейки по сравнению с возможным растягиванием дерева и временем O(n).

В данном топике, разумеется, лучше юзать хэшмапы для поиска по id. Но если понадобятся запросы вида "наибольшее значение, не превосходящее заданного" и т.д., при условии частых изменений набора, то мимо сбалансированных деревьев не пройти.

[Alexandroppolus]

1. На сервер приходит запрос "<Вася> хочет передать <Пете> то-то".

2. Система ищет Васю и Петю в массиве buffer — если их там нет, то добавляет их в этот массив buffer и реализует запрос. Если хоть один из них есть в buffer, то добавляет этот запрос в массив очереди pool. Когда их очередь подходит, то снова проверяет п.2

3. Сразу же после реализации запроса система удаляет Васю и Петю из массива buffer и, если очередь pool не пуста, то проверяет ее и добавляет в массив buffer следующих Вась и Петь, чтобы выполнить их запросы.

а какая проверка делается в п.3? всей очереди, или только первого элемента?

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

[voraa]

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

[Alexandroppolus]

Логичнее было бы любой приходящий запрос помещать в очередь.

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

а вот кейс проверки всей очереди выглядит как узкое место, если очередь длинная. Здесь и надо как-то оптимизировать. Самое простое - сделать хэшмэп с очередями по каждому участнику. Освободилась пара [Вася, Петя], берем очереди по Васе и Пете и просматриваем их параллельно (в элементах очереди должен быть ещё таймстамп, когда добавили). В итоге мы найдем либо задачу снова [Вася, Петя], либо задачи [Вася, Х] и [Петя, Y], где X и Y отсутствуют в хэшмепе занятых. Вот эти задачи можно запускать в обработку, не забыв удалить элементы из персональных очередей для Вася, Петя, X и Y.
Худший случай - когда в этих очередях будет дохрена пар [Вася, А] и [Петя, Б], где А и Б - занятые. Что с этим делать, как их быстро поскипать, пока не совсем понятно.

про очередь в виде списка согласен. Можно добавить ещё пул элементов, чтобы их переиспользовать, не создавать каждый раз новые объекты.

[voraa]

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

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

[voraa]

Можно добавить ещё пул элементов, чтобы их переиспользовать, не создавать каждый раз новые объекты.

Пул свободных это ведь тоже список.
Нам не ведомо, что быстрее на js создание нового объекта (это какая то внутренняя достаточно быстрая операция) или помещение и извлечение объекта из списка. (это уже программа, с интерпретацией байткода, вызовы функций, что тоже не самая дешевая операция)