Что именно тяжелого в этих вычислениях?

231

17 марта 2018, 19:44

Есть массив вида

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 раз большим массивом.

Answer 1

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

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

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

        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]);
            // ...
        }