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

[webgraph]

ошибочка у меня вышла. Недоглядел

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

[voraa]

Сделал тесты с массивами отсортированным и несортированным.
Для поиска в сортированном массиве использовал функцию, которую предлагал ранее, немного изменив ее.
Число элементов сделал 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))

Результаты такие

Проверка и добавление для объекта 62
Проверка и добавление для Set 23
Проверка и добавление для массива 1443
Проверка и добавление для несорт. массива 181184
Проверка и удаление для объекта 26
Проверка и удаление для Set 23
Проверка и удаление для массива 4620
Проверка и удаление для несорт. массива 28313

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

[Aetae]

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

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

[webgraph]

Какой то парадокс

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


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

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

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

//

[webgraph]

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

[Aetae]

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

[webgraph]

отражается как-то на разнице

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

[voraa]

из-за безумия хозяев стандарта числовые ключи в объекте сортируются и кладутся в начало

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

[voraa]

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

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

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

для строк?

[voraa]

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

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

Для объекта лучше Object.create(null) использовать.

Попробовал - эффекта не дало.