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

[Aetae]

webgraph, я сказал чем. Splice двигает (условно) половину массива чтоб вставить в середину, в дереве же просто добавится ещё одна ветка.
Но в большинстве случаев splice будет достаточно.

Если это прям такое узкое место - то сидите и разбирайтесь с математикой.
Мб кто-нить тут вам напишет, но не я.)

[voraa]

Если он такой "тяжёлый", то чем его заменить?

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

Есть вариант большой массив, по которому часто выполняется поиск, и иногда добавление. Для этого может быть пригоден такой вариант. Есть массив на 10000 (порядок) элементов. Он отсортирован. И есть маленький массив на 50 элементов. Добавление всегда в маленький. Поиск - сначала по большому, если не нашли - в маленьком. Когда маленький заполняется происходит слияние и сортировка массивов, маленький обнуляется и по новой...

Оптимальность зависит от условий использования.

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

[webgraph]

какие именно операции и в какой последовательности выполняются у вас. И с какими целями.

Данный прототип массива необходим для создания буфера элементов (buffer) и очереди операций (pool). Когда элемент добавлен в буфер, то последующие операции с ним блокируются и отправляются в массив очереди. Когда операция завершена, то элемент удаляется из буфера и при достижении своей очереди снова может быть добавлен в буфер для совершения требуемых с ним действий.

Это своего рода "транзакции".


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

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

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

//объекты, с которыми проводятся операции в реальном времени
let buffer = ['Вася', 'Петя', 'Маша', 'Таня'];

//запросы в очереди, потому что их объекты from или to в настоящий момент заняты
let pool = [{from: 'Вася', to: 'Таня', action: 'Действие'}, {from: 'Вася', to: 'Ваня', action: 'Действие'}];

[voraa]

И насколько велик может быть массив buffer?
Там действительно только строки? Если так, то может быть рассмотреть возможность использования Set для таких операций. Операции с Set оптимизированы на уровне js машины.
Все операции - добавление, проверка наличия и удаления есть.

[webgraph]

И насколько велик может быть массив buffer?
Там действительно только строки?

Т.к. buffer постоянно обновляется, то большим не должен быть. До 30,000 (на основе сопутствующего алгоритма, который может, в текущей ситуации, проверять до 30к элементов. Это значение может быть значительно увеличено). Здесь больше важна скорость поиска, добавления и удаления элементов.

Действительно ли там только строки? — Да, одинаковой длины.

[voraa]

Здесь больше важна скорость поиска, добавления и удаления элементов.

Действительно ли там только строки? — Да, одинаковой длины.

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

[voraa]

В принципе, можно бы было использовать и объекты, где строки были свойствами
{'aaa":true,
'aab':true,
....
}
эксперименты (можно найти в инете) показывали, что на каком то количестве ключей (до 100_000) поиск (для проверки наличия) выполнялся даже быстрее, чем в Set. Но вот про скорость операций вставки и удаления ничего сказать не могу.

[webgraph]

использовать и объекты

Вот как раз хотели вам показать тест, где с объектами сравнивается:
https://jsbench.me/3pkjlwzhbr/1

Там до 800 млн операций в секунду производительность.

Что скажете?)

[voraa]

Хорошо. Причем это только поиск. А операции вставки или удаления с массивами будут еще медленнее. Там двигать часть массива нужно.

У меня что на obj, что на Set поиск показал 730 млн

[webgraph]

voraa, раз Object показывает наивысшую производительность поиска по ключу, то как лучше протестировать добавление в него и удаление?