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

// есть отсортированный большой массив
let arr = ['ABC','BCD','CAE','CBA'];

Как добавить элемент 'BAS' сразу в нужное место, т.е. после 'ABC'?

// методы arr.push() и arr.unshift() подразумевают использование дальнейшей сортировки массива

Как добавить упорядоченно без сортировки?

:)

webgraph,

let arr = ['ABC', 'BCD', 'CAE', 'CBA'],
            el = 'BAS';
            len = arr.length;
            i = 0;
        for (; i < len; i++) if (el < arr[i]) break;
        arr.splice(i, 0, el);
        alert(arr)

arr.splice()

Если же нужно прям оптимально и супер быстро, ту тут уж придётся бинароное дерево городить вместо массива или типа того.

Зачем дерево?
Бинарный поиск по отсортированному массиву.

Как то так

// ищет в отсортированном массиве arr 
// индекс первого элемента >= val 
// выдает arr.length, если все элементы < val
const findBinIndex =(arr, val) => {
	let nb=0, ne=arr.length-1;
	if (val<=arr[0]) return 0;
	if (val >= arr[ne]) return ne+1;
	let index;
	while (true) {
		index = ((ne + nb) / 2) | 0;
		if (arr[index] <= val)
			nb = index;
		else 
			ne = index;
			
		if (ne - nb == 1) {
			if (val<=arr[nb]) return nb;
			if (val >= arr[ne]) return ne+1;
			return ne;
		}
	}
}

const arr =  ['ABC', 'BCD','BCD', 'CAE', 'CBA']
let k, el;
el = 'BAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'AAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CCS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'BCD';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CAF';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

console.log(arr)

Да, именно оптимально и супер быстро нужно) Можете подробнее рассказать/показать об этом бинарном древе?)

А если интерполирующий?) И в чем принципиальное отличие бинарного дерева от бинарного поиска (что лучше/быстрее)?

webgraph, да вон вариант от voraa оптимальный для поставленных условий.

voraa, дерево будет нужно если таких операций много - всё-таки splice сам по себе "тяжёлый".

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

webgraph, массив в дерево - проводим добавления - дерево растёт - собираем в конце дерево в массив.
Конкретную реализацию писать лень, поугули.)

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

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

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

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

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

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

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

Данный прототип массива необходим для создания буфера элементов (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: 'Действие'}];

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

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

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

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

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

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

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

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

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

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

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

По идее Set и объект должны иметь идентичную производительность на современных движках, т.к. под капотом там одно и то же. Так что логично использовать именно Set. Объект может быть даже медленнее на v8 из-за заморочек с базовым классом.

Тестирование проводилось на основе https://jsbench.me/3pkjlwzhbr/1

// Входные данные для тестирования на jsbench.me

var theArr = Array.from({ length: 10000 }, (_, el) => el)
var theSet = new Set(theArr)
var theObj = Object.assign({}, ...theArr.map(num => ({ [num]: true })))
var theMap = new Map(theArr.map(num => [num, true]))
var theKey = 5000


// Тестирование поиска 

theArr.includes(theKey)   // 17% slower — 660,699,003.59 ops/s
theMap.has(theKey)        // 1.1% slower — 785,347,360.36 ops/s
theSet.has(theKey)        // 0.8% slower — 787,801,318.7 ops/s
theObj[theKey]            // FASTEST — 794,522,297.06 ops/s


// Тестирование добавления 

theArr.push(theKey)       // 95% slower — 39,049,698.98 ops/s
theMap.set(theKey, true)  // 89% slower — 82,050,365.52 ops/s
theSet.add(theKey)        // 87% slower — 99,994,802.31 ops/s
theObj[theKey] = true     // SUPER FASTEST — 792,917,323.61 ops/s


// Тестирование удаления 

delete theArr[theKey]     // 69% slower — 28,602,351.93 ops/s
theMap.delete(theKey)     // 3% slower — 90,739,199.4 ops/s
theSet.delete(theKey)     // FASTEST — 93,412,121 ops/s
delete theObj[theKey]     // 68% slower — 29,350,950.47 ops/s

/*

ИТОГИ:

Производительность Set и Map высокая и практически идентичная во всех случаях.
У Object наивысшая и значительно опережающая производительность добавления, но низкая при удалении.
Arrays просто покинули чат с наименьшей производительностью

*/

На сколько правильно проведено тестирование?

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

Так на jsbench.me он же прогоняет эту одну операцию сколько-то раз и в итоге выводит результаты тестирования или нет? Предлагаете через for() прогнать или как?

Вот мой тест.
Генерируем 1 000 000 строковых ключей. Потом добавляем их в объект и Set.
Потом удаляем их

const genKeys = (n) => {
	const keys = []
	while (n--) {
		const nkey = Math.round(Math.round()*1_000_000);
		const key = (''+nkey).padStart(7, '0');
		keys.push(key)
	}
	return keys;
}

const N = 1_000_000;
let t0;

// Генерация ключей для заполнения
const keys = genKeys(N);
const obj = {};
const set = new Set();

// Проверка и добавление для объекта
t0 = performance.now();
for (const key of keys) 
	if (!(key in obj))	obj[key] = true;
const tsetobj = performance.now() - t0;

// Проверка и добавление для Set
t0 = performance.now();
for (const key of keys) 
	if (!set.has(key)) set.add(key);
const tsetset = performance.now() - t0;  
  
// Проверка и удаление для объекта
t0 = performance.now();
for (const key of keys) 
	if (key in obj) delete obj[key]
const tdelobj = performance.now() - t0; 
     
// Проверка и удаление для Set
t0 = performance.now();
for (const key of keys) 
	if (set.has(key)) set.delete (key);
const tdelset = performance.now() - t0;  

console.log('Проверка и добавление для объекта', tsetobj.toFixed(0))
console.log('Проверка и добавление для Set', tsetset.toFixed(0))
console.log('Проверка и удаление для объекта', tdelobj.toFixed(0))
console.log('Проверка и удаление для Set', tdelset.toFixed(0))

Результат показывает, что Set быстрее
У меня так

Как так получается-то, что если поменять их местами, то "Проверка и добавление" выполняются практически одинаково и даже у Obj время меньше становится, чем у Set? В то же время если сначала проверять и добавлять объект (как изначально сделано) — разница существенная — более x2. Это как понимать?

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

Вот попробуйте

let genKeys = (n) => {
        const keys = []
        while (n--) {
            const nkey = Math.round(Math.round() * 1_000_000);
            const key = (''+nkey).padStart(7, '0');
            keys.push(key)
        }
        return keys;
    }

    // Генерация ключей для заполнения
    let keys = genKeys(1_000_000);
    const obj = {};
    const set = new Set();


    // Проверка и добавление для Set
    console.time('has_add_Set')
    for (const key of keys)
        if (!set.has(key)) set.add(key);
    console.timeEnd('has_add_Set')


    // Проверка и добавление для объекта
    console.time('has_add_Obj')
    for (const key of keys)
        if (!(key in obj))	obj[key] = true;
    console.timeEnd('has_add_Obj')


    // Проверка и удаление для объекта
    console.time('has_delete_Obj')
    for (const key of keys)
        if (key in obj) delete obj[key]
    console.timeEnd('has_delete_Obj')


    // Проверка и удаление для Set
    t0 = performance.now();
    console.time('has_delete_Set')
    for (const key of keys)
        if (set.has(key)) set.delete (key);
    console.timeEnd('has_delete_Set')

Трудно понять работу движка. Я посмотрел, что временами он прерывается на сборку мусора (хотя по идеи его быть не должно) + он в какой то момент запускает оптимизацию кода. И что до оптимизации, что после - понять трудно.
Конечно сами циклы добавляют время (цикл for-of более медленный, чем обычный for(; ; ) )
Я попробовал заменить циклы (и поменять местами тесты для объектов и Set

const genKeys = (n) => {
	const keys = []
	while (n--) {
		const nkey = Math.round(Math.round()*1_000_000);
		const key = (''+nkey).padStart(7, '0');
		keys.push(key)
	}
	return keys;
}

const N = 1_000_000;
let t0;

// Генерация ключей для заполнения
const keys = genKeys(N);
const obj = {};
const set = new Set();
let key;

// Проверка и добавление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!set.has(key)) set.add(key);
}
const tsetset = performance.now() - t0;  

// Проверка и добавление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!(key in obj))	obj[key] = true;
}
const tsetobj = performance.now() - t0;

  
// Проверка и удаление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (set.has(key)) set.delete (key);
}
const tdelset = performance.now() - t0;  

// Проверка и удаление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (key in obj) delete obj[key];
}
const tdelobj = performance.now() - t0; 
     

console.log('Проверка и добавление для объекта', tsetobj.toFixed(0))
console.log('Проверка и добавление для Set', tsetset.toFixed(0))
console.log('Проверка и удаление для объекта', tdelobj.toFixed(0))
console.log('Проверка и удаление для Set', tdelset.toFixed(0))

Результаты стали получше
Но Set все равно побыстрее

voraa, а можете поподробнее рассказать про этот алгоритм заполнения массива? В частности про переменную nkey

const genKeys = (n) => {
        const keys = []
        while (n--) {
            const nkey = Math.round(Math.round() * 1_000_000);
            const key = (''+nkey).padStart(7, '0');
            keys.push(key)
        }
        return keys;
    }

ошибочка у меня вышла. Недоглядел :(
Тогда результаты совсем другие по временам

const genKeys = (n) => {
	const keys = []
	while (n--) {
		const nkey = Math.round(Math.random()*1_000_000);
		const key = (''+nkey).padStart(7, '0');
		keys.push(key)
	}
	return keys;
}

const N = 1_000_000;
let t0;

// Генерация ключей для заполнения
const keys = genKeys(N);
const obj = {};
const set = new Set();
let key;

// Проверка и добавление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!set.has(key)) set.add(key);
}
const tsetset = performance.now() - t0;  

// Проверка и добавление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!(key in obj))	obj[key] = true;
}
const tsetobj = performance.now() - t0;

  
// Проверка и удаление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (set.has(key)) set.delete (key);
}
const tdelset = performance.now() - t0;  

// Проверка и удаление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (key in obj) delete obj[key];
}
const tdelobj = performance.now() - t0; 
     

console.log('Проверка и добавление для объекта', tsetobj.toFixed(0))
console.log('Проверка и добавление для Set', tsetset.toFixed(0))
console.log('Проверка и удаление для объекта', tdelobj.toFixed(0))
console.log('Проверка и удаление для Set', tdelset.toFixed(0))

Получается, что добавление для Set быстрее, а удаление быстрее для объектов

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

Сначала не удавалось догнать что за ошибочка XD, А потом стало понятно — random. Кстати после этого тесты стали более детерминированными — перестановка местами перестала влиять на результаты. Ибо до этого в массиве было миллион NaN — JS наверняка был в шоке от такого.

Сделал тесты с массивами отсортированным и несортированным.
Для поиска в сортированном массиве использовал функцию, которую предлагал ранее, немного изменив ее.
Число элементов сделал 100_000, что бы не ждать часами.

const genKeys = (n) => {
	const keys = []
	while (n--) {
		const nkey = Math.round(Math.random()*100_000);
		const key = (''+nkey).padStart(6, '0');
		keys.push(key)
	}
	return keys;
}

// Поиск значения val в отсортированном массиве arr
// возвращает {ind, has} 
// has == true, если элемент есть и ind - индекс элемента
// has == false, если элемента нет и ind - индекс большего элемента
const findBinIndex =(arr, val) => {
	if (arr.length == 0) return {ind: 0, has:false}
    let nb=0, ne=arr.length-1;
    if (val<=arr[0]) return {ind:0, has:val==arr[0]};
    if (val > arr[ne]) return {ind: ne+1, has: false};
    if (val == arr[ne]) return {ind: ne, has: true};
    let index;
    while (true) {
        index = ((ne + nb) / 2) | 0;
        if (arr[index] <= val)
            nb = index;
        else
            ne = index;
             
        if (ne - nb == 1) {
            if (val<=arr[nb]) return {ind:nb,has:val==arr[nb]};
            if (val > arr[ne]) return {ind:ne+1, has: false};
            if (val == arr[ne]) return {ind:ne, has: true};
            return {ind: ne, has:false};
        }
    }
}


const N = 100_000;
let t0;

// Генерация ключей для заполнения
const keys = genKeys(N);
const obj = {};
const set = new Set();
const arr = [];
const arrns = [];
let key;

// Проверка и добавление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!set.has(key)) set.add(key);
}
const tsetset = performance.now() - t0;  

// Проверка и добавление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (!(key in obj))	obj[key] = true;
}
const tsetobj = performance.now() - t0;

// Проверка и добавление для массива
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	const res = findBinIndex(arr, key)
	if (!res.has)	arr.splice(res.ind, 0, key)
}
const tsetarr = performance.now() - t0;

// Проверка и добавление для несортированного массива
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	const ind =  arrns.indexOf(key);
	if (ind<0)	arrns.push(key)
}
const tsetarrns = performance.now() - t0;

  
// Проверка и удаление для Set
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (set.has(key)) set.delete (key);
}
const tdelset = performance.now() - t0;  

// Проверка и удаление для объекта
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	if (key in obj) delete obj[key];
}
const tdelobj = performance.now() - t0; 

// Проверка и удаление для  массива
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	const res = findBinIndex(arr, key);
	if (res.has)	arr.splice(res.ind, 1);
}
const tdelarr = performance.now() - t0; 

// Проверка и удаление для несортированного массива
t0 = performance.now();
for (let i=0; i<N; i++) {
	key = keys[i];
	const ind = arrns.indexOf(key);
	if (!ind>=0) arrns.splice(ind, 1);
}
const tdelarrns = performance.now() - t0;
     

console.log('Проверка и добавление для объекта', tsetobj.toFixed(0))
console.log('Проверка и добавление для Set', tsetset.toFixed(0))
console.log('Проверка и добавление для массива', tsetarr.toFixed(0))
console.log('Проверка и добавление для несорт. массива', tsetarrns.toFixed(0))
console.log('Проверка и удаление для объекта', tdelobj.toFixed(0))
console.log('Проверка и удаление для Set', tdelset.toFixed(0))
console.log('Проверка и удаление для массива', tdelarr.toFixed(0))
console.log('Проверка и удаление для несорт. массива', tdelarrns.toFixed(0))

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

Для объекта лучше Object.create(null) использовать. Тогда с Set более-менее сравняется.)

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

И не говори...


Если искать число в строковом obj/set, то побеждает Object.
Если искать строку в строковом obj/set, то побеждает Set.
Если искать число в числовом obj/set, то побеждает Object.
Если искать строку в числовом obj/set, то побеждает Object.

Победа означает +- x2 производительность. Причём у Object производительность бывает выше до 80%

НО! Если искать очень большое число (сильно выходящее за границы элементов массивов) среди строкового или числового obj/set, то obj сильно начинает проигрывать!...

//

voraa,

Раз тебя так заинтриговали массивы, может стоит поробовать интерполирующий поиск?

function InterpolationSearch(t,A)          // t - искомый элемент,
{                                          // A - упорядоченный массив, в котором ищем.
    var mid, low = 0, high = A.length-1;

    while (A[low] < t && A[high] > t)
    {  mid = low + Math.floor( ((t-A[low])*(high-low))/(A[high]-A[low]) );
       if (A[mid] < t) low = mid+1;
       else if (A[mid] > t) high = mid-1;
       else return mid;
    }

    if (A[low] === t) return low;           // На выходе индекс искомого элемента.
    else if (A[high] === t) return high;    // Если искомого элемента нет в массиве, то -1.
    else return -1;
}

Интерполирующий поиск похож на то, как мы ищем контакт в адресной книге (бумажной). Например, если нам надо найти Ваню, то наврядли мы будет открывать конец или середину книги (как это делается в бинарном поиске) — мы откроем на первых страницах.

//

P.S. у него скорость тоже низкая по сравнению с Set или Map

webgraph, из-за безумия хозяев стандарта числовые ключи в объекте сортируются и кладутся в начало, что скорее всего и отражается как-то на разнице.

"Как-то"? "Как-то" - это когда +- 10% выше производительность. А когда это доходит до 80%, то это уже не "как-то". Это уже ОГОГО

Устройство движка вещь непредсказуемая.
У меня нет твердой уверенности, что они так кладутся и хранятся.
Вот выбираются они так - сначала числовые, потом строковые в порядке добавления.
К тому же оптимизации всякие. Файрфокс на неотсортированном массиве показывает гораздо лучшие результаты, чем Хром.

Вот только как реализовать это

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

для строк?

У объектов нет чисел. Они все равно преобразуются в строки. Свойством может быть только строка или Symbol.
Попробовал - эффекта не дало.