JavaScript for 循环性能问题

Question

循环数据集合的最佳方法是什么。我面临的问题是性能低下。请参阅示例代码片段。以下两种方法存在性能问题。

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

在我工作的应用程序中，我需要对数组进行 3 到 4 次迭代。这会导致应用程序性能低下。任何人都可以建议什么是最好的循环方式。

Answer 1

无需再次检查每个元素，.some您可以将您的值传播到 an 中Set并检查set.has()其内部女巫是否更快你的时间复杂度从下降O(n^2)到O(n)// sample datalet 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 1let start = performance.now()for (let day of monthDays) {    day.disabled = disabledDates.some(d => d === day.date);}console.log(performance.now() - start);//resetmonthDays = 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 dataconst 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 1let 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 dataconst 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 generatedconst lookup: Record<number, true> = {    1: true,    2: true,    3: true,    /*...*/ }/*...*///fetch from lookup or set `false` if not in the lookupconst disabled: boolean = lookup[day.date] ?? false;