JavaScript for 循环性能问题

Question

循环数据集合的最佳方法是什么。我面临的问题是性能低下。请参阅示例代码片段。以下两种方法存在性能问题。interface Day {    date: number;    disabled: boolean;}// sample dataconst 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 1let counter = 0;for (let day of monthDays) {    day.disabled = disabledDates.some(d => d === day.date);    counter++;}console.log(counter) // logs 30// method 2counter = 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在我工作的应用程序中，我需要对数组进行 3 到 4 次迭代。这会导致应用程序性能低下。任何人都可以建议什么是最好的循环方式。

Answer 1

无需再次检查每个元素，.some您可以将您的值传播到 an 中Set并检查set.has()其内部女巫是否更快

你的时间复杂度从下降O(n^2)到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);

Answer 2

方法 1 和方法 2 具有完全相同的性能特征，但是，您测量它们的方法存在缺陷。使用方法 2，您计算代码进行的外部和内部迭代，而使用方法 1，您只计算外部迭代。但是，.some()仍然对数据进行迭代：

// 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

由于您有两个嵌套迭代，这两种方法都表现出O(n*m)时间复杂度，其中n是的长度monthDays，m是 的长度disabledDates。这基本上是 的接近值的二次复杂度n并且m实际上是 的二次复杂度n = m（如示例所示）。

纠正这个问题的方法是消除嵌套循环，只处理一次数据。这很容易通过首先预先计算一个包含所有对象的Set对象disabledDates来实现，这样您就不必遍历数组来检查它们是否存在而不是使用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);

一次转换为一组的复杂度为O(m)，然后每次循环时您只有一次O(n)迭代。

• 如果您只能创建一次集合，则重复迭代monthDays不需要包含该操作。这样操作的复杂度就变成了O(n)。

• 如果您每次都需要在循环之前创建一个集合，那么复杂性将变得O(n+m)比二次和线性更好。

请注意，这假定这.has()是一个O(1)操作。这是一个合理的假设，可能在大多数情况下都是正确的。然而，从技术上讲，这并不能保证——规范定义了集合操作的次线性复杂度，所以你可能有O(log n)复杂度，这意味着迭代monthDays和查找disabledDates将是O(n * log m). 即便如此，使用集合可能是最简单的优化路径。如果性能仍然是一个问题，那么生成一个对象作为查找表可能会更好：

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