2 回答

TA貢獻2036條經驗 獲得超8個贊
無需再次檢查每個元素,.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);

TA貢獻1848條經驗 獲得超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;
添加回答
舉報