2 回答
TA貢獻(xiàn)2036條經(jīng)驗 獲得超8個贊
無需再次檢查每個元素,.some您可以將您的值傳播到 an 中Set并檢查set.has()其內(nèi)部女巫是否更快
你的時間復(fù)雜度從下降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貢獻(xiàn)1848條經(jīng)驗 獲得超2個贊
方法 1 和方法 2 具有完全相同的性能特征,但是,您測量它們的方法存在缺陷。使用方法 2,您計算代碼進(jìn)行的外部和內(nèi)部迭代,而使用方法 1,您只計算外部迭代。但是,.some()仍然對數(shù)據(jù)進(jìn)行迭代:
// 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
由于您有兩個嵌套迭代,這兩種方法都表現(xiàn)出O(n*m)時間復(fù)雜度,其中n是的長度monthDays,m是 的長度disabledDates。這基本上是 的接近值的二次復(fù)雜度n并且m實(shí)際上是 的二次復(fù)雜度n = m(如示例所示)。
糾正這個問題的方法是消除嵌套循環(huán),只處理一次數(shù)據(jù)。這很容易通過首先預(yù)先計算一個包含所有對象的Set對象disabledDates來實(shí)現(xiàn),這樣您就不必遍歷數(shù)組來檢查它們是否存在而不是使用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);
一次轉(zhuǎn)換為一組的復(fù)雜度為O(m),然后每次循環(huán)時您只有一次O(n)迭代。
如果您只能創(chuàng)建一次集合,則重復(fù)迭代
monthDays不需要包含該操作。這樣操作的復(fù)雜度就變成了O(n)。如果您每次都需要在循環(huán)之前創(chuàng)建一個集合,那么復(fù)雜性將變得
O(n+m)比二次和線性更好。
請注意,這假定這.has()是一個O(1)操作。這是一個合理的假設(shè),可能在大多數(shù)情況下都是正確的。然而,從技術(shù)上講,這并不能保證——規(guī)范定義了集合操作的次線性復(fù)雜度,所以你可能有O(log n)復(fù)雜度,這意味著迭代monthDays和查找disabledDates將是O(n * log m).?即便如此,使用集合可能是最簡單的優(yōu)化路徑。如果性能仍然是一個問題,那么生成一個對象作為查找表可能會更好:
//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;
添加回答
舉報
