CODEWITHSUNDEEP
javascriptarraysperformanceloopsindexof
C. Ubkcah
C. Ubkcah

Reputation: 273

JavaScript Performance: Loop and indexOf with large Arrays

I currently have a problem with the performance of a JavaScript operation.

I want to clean up an object array (aEmployees) for those objects whose ID is already in the array aInvited or which are not in the aInvitationAllowed array: 

var iLength = aEmployees.length - 1;
for (var i = iLength; i >= 0; --i) {
   if (aInvited.indexOf(aEmployees[i].id) !== -1 || aInvitationAllowed.indexOf(aEmployees[i].id) === -1) {
      aEmployees.splice(i, 1);
   }
}

You can imagine that I have Employee objects (aEmployees). I also have a list of Employee IDs that have already been invited to an event (aInvited) and a list of Employee IDs that are allowed to be invited to the event (aInvitationAllowed). I want to have all Employees as a result that I can still invite to the event.

The problem is the line with the indexOf queries. I have to assume that the arrays have very many entries (~ 100,000 entries). Then it may be that taking the loop takes a while.

So my question to you: How can I make the loop faster? Are there faster alternatives for indexOf?

Thanks for your tips!

Upvotes: 0

Views: 125

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370929

Consider using a Set to compare instead. Set.has is an O(1) operation, whereas indexOf is an O(n) operation, reducing the computational complexity overall to O(n) instead of O(n^2):

const aInvitedSet = new Set(aInvited);
const aAllowedSet = new Set(aAllowed);

const iLength = aEmployees.length - 1;
for (let i = iLength; i >= 0; --i) {
  const { id } = aEmployees[i];
  if (aInvitedSet.has(id) || !aAllowedSet.has(id)) {
    aEmployees.splice(i, 1);
  }
}

Also, splice is slow-ish. Unless you have to mutate the exising array, you might consider .pushing to a new array instead (which looks to be faster than Array.prototype.filter):

const aInvitedSet = new Set(aInvited);
const aAllowedSet = new Set(aAllowed);
const newArr = [];

const iLength = aEmployees.length;
for (let i = 0; i < iLength; i++) {
  const employee = aEmployees[i];
  const { id } = employee;
  if (!aInvitedSet.has(id) && aAllowedSet.has(id)) {
    newArr.push(employee);
  }
}

Upvotes: 5

Related Questions