There is an array of the form

ar=[283462197, 191777391, 243143621, 451231707, 217268739, ] // и там их 1 310 341 штук

it is necessary to select unique values, I do through this function

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

IMHO works very quickly for 80.774ms As a result, I have 114262 elements, I do my business and it turns out that 73928 should be removed from them, and then the problems begin, I do this:

 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("исключение банов");

And it took 893288.239мс it is simply unacceptable, forgive 893288.239мс to explain how it goes, why the unique procedure of the same complexity is done 4 orders of magnitude faster with a size of 10 times a large array.

  • Well, in the second case, you get a cycle in a cycle, which increases the number of passes through the cycle, hence your time increases. - Sergey Glazirin

1 answer 1

In the first case, you use a hash table, which is any large object. You have only one pass through the array, and the running time is proportional to the size of the array.

In the second case, you use a linear array search every time — and therefore the running time is proportional to the product of the lengths of the arrays.

You cannot use linear search for this task. Instead, you need to convert the second array into a hash table, just as you did when searching for unique records. And only then do a search on this table.

  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 I still recommend using Set or Map instead of objects - on modern browsers they should work faster:

  const bansSet = new Set(banIds); for (let i = grdb.user_ids_clear.length; i--;) { const exist = bansSet.has(grdb.user_ids_clear[i]); // ... }
  • Made through hasOwnProperty, it became less than 200 ms, even I am afraid to consider how much it is faster. new Set test, on the last node works 20% slower than my function. - Roman Berezhnov
  • You can still slightly speed up if you create an object with a null prototype, and access it through a simple access operator. - ReklatsMasters