0

What is the best way to loop over a collection of data. The problem i am facing is the low performance. See the example code snippets. Following two methods has the performance issue.

interface Day {
    date: number;
    disabled: boolean;
}

// sample data
const monthDays: Day[] = Array.from({ length: 30 }, (v: unknown, k: number) => ({ date: k + 1, disabled: false }));
const disabledDates: number[] = Array.from({ length: 30 }, (v, k) => k + 1);

//set disabled dates
// method 1
let counter = 0;
for (let day of monthDays) {
    day.disabled = disabledDates.some(d => d === day.date);
    counter++;
}

console.log(counter) // logs 30

// method 2
counter = 0;
for (let day of monthDays) {
    for (let date of disabledDates) {
        counter++;
        if (day.date === date) {
            day.disabled = true;
            break;
        }
    }
}

console.log(counter); // logs 494

In the app i am working , i need to iterate on array 3 to 4 times . This results in low performance of the app. Can anyone suggest whats is the best way to loop.

Gyan
  • 140
  • 2
  • 11
  • Please add what you want to achieve. – brk Oct 23 '20 at 06:01
  • Use a set for disabled days. You could also use a map for month days but I'd start with just disabled days and see where that takes you. – Brenden Oct 23 '20 at 06:02
  • In both cases it's a `O(n*m)` performance. Your first method 1 *only* counts the outer iterations but not the inner ones by `.some()`. – VLAZ Oct 23 '20 at 06:04
  • could you explain what you want to achive i cannot get it clearly – bill.gates Oct 23 '20 at 06:06
  • @brk and ifaruki lopping over the array, cost in performance of app. My question is how to iterate over an array without performance issue. – Gyan Oct 23 '20 at 06:17
  • @Gyan i was trying to know what you want to do in the loop – brk Oct 23 '20 at 06:25

2 Answers2

1

Instead of checking each element again with .some you can spread your values into an Set and check with set.has() if its inside witch is much faster

Your time complexity drops from O(n^2) to O(n)

// sample data
let monthDays = Array.from({ length: 10000 }, (v, k) => ({ date: k + 1, disabled: false }));
const disabledDates = Array.from({ length: 10000 }, (v, k) => k + 1);

//set disabled dates
// method 1

let start = performance.now()
for (let day of monthDays) {
    day.disabled = disabledDates.some(d => d === day.date);
}
console.log(performance.now() - start);

//reset
monthDays = Array.from({ length: 10000 }, (v, k) => ({ date: k + 1, disabled: false }));

start = performance.now();
let set = new Set([ ...disabledDates ]);
for (let day of monthDays) {
   if(set.has(day.date)) {
      day.disabled = true;
   }else {
      day.disabled = false;
   }
}

console.log(performance.now() - start);
bill.gates
  • 14,145
  • 3
  • 19
  • 47
0

You have the exact same performance characteristics with both method 1 and method 2, however, your way of measuring them is flawed. With method 2, you count the outer and inner iterations made by the code, while with method 1, you only count the outer iterations. However, .some() still does an iteration over the data:

// sample data
const monthDays = Array.from({ length: 30 }, (v, k) => ({ date: k + 1, disabled: false }));
const disabledDates = Array.from({ length: 30 }, (v, k) => k + 1);

//set disabled dates
// method 1
let counter = 0;
for (let day of monthDays) {
    day.disabled = disabledDates.some(d => {
      counter++;
      return d === day.date
    });
    counter++;
}

console.log(counter) // logs 495

See also on TypeScript Playground

Since you have two nested iterations, both methods exhibit an O(n*m) time complexity, where n is the length of monthDays and m is the length of disabledDates. This is basically quadratic complexity for close values of n and m and actually quadratic for n = m (as is the example).

The way to correct that is to eliminate the nested loops and only process the data once. This is easily achievable by first pre-computing a Set object that contains all disabledDates, that way you don't have to loop over an array only to check if they exist instead using Set#has.

// sample data
const monthDays = Array.from({ length: 30 }, (v, k) => ({ date: k + 1, disabled: false }));
const disabledDates = new Set(Array.from({ length: 30 }, (v, k) => k + 1));

for (const day of monthDays) {
  day.disabled = disabledDates.has(day.date);
}

console.log(monthDays);

See also on TypeScript Playground

The one time conversion to a set has a complexity of O(m) and then each time you loop over you only have an O(n) iteration.

  • If you can create set once only, then repeatedly iterating monthDays don't need to include that operation. Thus the complexity of the operation becomes O(n).
  • If you need to create a set every time before you loop, then the complexity becomes an O(n+m) which is still better than quadratic and essentially linear.

As a note here, this assumes that .has() is a O(1) operation. This is a reasonable assumption that probably holds true most of the time. However, technically, that's not guaranteed - the specifications define a sub-linear complexity on set operations, so you might have O(log n) complexity, which means that the iteration over monthDays and looking up disabledDates will be O(n * log m). Even then, using a set is probably the easiest optimisation path. If performance is still a problem, then perhaps generating an object as a lookup table could be better:

//this should be generated
const lookup: Record<number, true> = {
    1: true,
    2: true,
    3: true,
    /*...*/ 
}

/*...*/

//fetch from lookup or set `false` if not in the lookup
const disabled: boolean = lookup[day.date] ?? false;
VLAZ
  • 26,331
  • 9
  • 49
  • 67