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

[Aetae]

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

[webgraph]

По идее 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 просто покинули чат с наименьшей производительностью

*/

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

[Aetae]

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

[webgraph]

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

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

[voraa]

Вот мой тест.
Генерируем 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 быстрее
У меня так

Проверка и добавление для объекта 131
Проверка и добавление для Set 50
Проверка и удаление для объекта 41
Проверка и удаление для Set 27

[webgraph]

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))

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

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

[webgraph]

недетерминированные результаты

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

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')

[voraa]

Трудно понять работу движка. Я посмотрел, что временами он прерывается на сборку мусора (хотя по идеи его быть не должно) + он в какой то момент запускает оптимизацию кода. И что до оптимизации, что после - понять трудно.
Конечно сами циклы добавляют время (цикл 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))

Результаты стали получше

Проверка и добавление для объекта 86
Проверка и добавление для Set 80
Проверка и удаление для объекта 30
Проверка и удаление для Set 17

Но Set все равно побыстрее

[webgraph]

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;
    }

[voraa]

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

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))

Проверка и добавление для объекта 870
Проверка и добавление для Set 534
Проверка и удаление для объекта 322
Проверка и удаление для Set 489

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

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