Есть массив вида
ar=[283462197, 191777391, 243143621, 451231707, 217268739, ] // и там их 1 310 341 штук
нужно выделить уникальные значения, делаю через эту функцию
var uniqueAr = function(ar) {
var existing = {},
result = [];
var length = ar.length;
for (i = length; i--;) {
if (!existing.hasOwnProperty(ar[i])) {
result.push(ar[i]);
existing[ar[i]] = true; //any value will do
}
}
return result;};
Работает имхо очень быстро за 80.774ms
В итоге имею 114262 элементов, делаю свои дела и выясняется что из них нужно удалить 73928, и тут начинаются проблемы, я делаю так:
grdb.user_ids_clear//массив после уникализации
banIds// те что нужно удалить, само собой тоже уникальны
console.time("исключение банов");
var tar = [];
var exist = false;
var banIdslength = banIds.length;
for (let i = grdb.user_ids_clear.length; i--;) {
exist = false;
for (let ii = banIdslength; ii--;) {
if (banIds[ii] === grdb.user_ids_clear[i]) {
exist = true;
break;
}
}
if (!exist) tar.push(grdb.user_ids_clear[i]);
}
console.timeEnd("исключение банов");
И это заняло 893288.239мс это просто неприемлемо, прощу объяснить как так выходит, почему уникализация процедура той же сложности делается на 4 порядка быстрее с размером в 10 раз большим массивом.
Ответ
В первом случае вы используете хеш-таблицу, которой являются любые большие объекты. У вас всего один проход по массиву, и время работы пропорционально размеру массива.
Во втором случае вы каждый раз используете линейный поиск по массиву - а потому время работы оказывается пропорционально произведению длин массивов.
Вам в этой задаче нельзя использовать линейный поиск. Вместо этого нужно преобразовать второй массив в хеш-таблицу так же как это делалось при поиске уникальных записей. А уже потом делать по этой таблице поиск.
const bansSet = {};
for (let ii = banIdslength; ii--;) {
bansSet[banIds[ii]] = true;
}
for (let i = grdb.user_ids_clear.length; i--;) {
const exist = bansSet.hasOwnProperty(grdb.user_ids_clear[i]);
// ...
}
PS все-таки рекомендую использовать Set или Map вместо объектов - на современных браузерах они должны работать шустрее:
const bansSet = new Set(banIds);
for (let i = grdb.user_ids_clear.length; i--;) {
const exist = bansSet.has(grdb.user_ids_clear[i]);
// ...
}
Комментариев нет:
Отправить комментарий