回圈嵌套陣列時發生沖突的基準測驗

資訊

我正在嘗試創建一種有效的方法來回圈使用嵌套物件/陣列的陣列，因為回圈資料的函式將頻繁運行并根據它們是否匹配包含物件的另一個陣列中的記錄來過濾值。

我正在使用的資料有以下型別。

type WatchedShows = {
    showId: number;
    season: number;
    episode: number;
}[];

type Shows = {
    id: number;
    seasons: {
        season: {
            season_number: number;
            episodes: {
                episode_number: number;
            }[];
        };
    }[];
}[];

資料在WatchedShows我自己的資料庫中，所以我可以控制它如何發送到前端，但是，資料Shows來自外部 API。

我要做的是過濾Shows與資料匹配的所有劇集，WatchedShows如果所有內容都標記為已觀看，則還過濾季節和整個節目。

問題

目前我有 3 個不同的解決方案，但第一個是 3 個嵌套回圈，并且由于一些資料而變得很慢，所以實際上我有 2 個解決方案。我還需要以以下格式回傳資料Shows

我現在嘗試通過基準測驗運行它們，并使用計時器進行了一些測驗，并檢查了它們每個人有多少次迭代。看看我自己做的測驗結果，有一個明顯的贏家，因為一個運行時間為 ，~5ms and 42637 iterations而另一個運行時間為~15ms and 884052 iterations.

然后我嘗試通過JSBench.me運行它，當我這樣做時，它的相反解決方案作為贏家出現，網站說它的速度提高了 90%。當該解決方案具有 884052 次迭代和其他 42637 次迭代時，怎么會發生這種情況？是我的解決方案優化得很差，還是我還缺少其他東西？改進解決方案的提示將不勝感激。

兩項測驗都是使用相同的代碼生成資料集完成的，該資料集包含大約 20 000 集記錄，分布在 26 個節目中，每季 20 季，每季 40 集。如果需要，可以在基準站點上查看生成資料集的代碼。基準可以在這里看到

代碼

具有 884052 次迭代和 ~15ms 運行時間的解決方案看起來像這樣

const newShowObject = {};

for (const show of shows) {
    newShowObject[show.id] = { ...show };
}

for (const show of watchedShows) {
    for (const season of newShowObject[show.showId].seasons) {
        if (season.season_number !== show.season) {
            continue;
        }
        season.episodes = season.episodes.filter(
            (episode) => episode.episode !== show.episode
        );
    }

    newShowObject[show.showId].seasons = newShowObject[show.showId].seasons.filter(
        (season) => season.episodes.length > 0
    );
}

const unwatchedShows = [...Object.values(newShowObject)].filter(
    (show) => show.seasons.length > 0
);

具有 42637 次迭代和 ~5ms 運行時間的解決方案看起來像這樣

const newShowObject = {};

for (const show of shows) {
    newShowObject[show.id] = { ...show };

    const newSeasons = {};

    for (const seasons of show.seasons) {
        newSeasons[seasons.season_number] = { ...seasons };

        const newEpisodes = {};

        for (const episodes of seasons.episodes) {
            newEpisodes[episodes.episode] = { ...episodes };
        }

        newSeasons[seasons.season_number].episodes = { ...newEpisodes };
    }
    newShowObject[show.id].seasons = { ...newSeasons };
}

for (const show of watchedShows) {
    delete newShowObject[show.showId].seasons[show.season].episodes[show.episode];
}

let unwatchedShows = [...Object.values(newShowObject)];

for (const show of unwatchedShows) {
    show.seasons = [...Object.values(show.seasons)];
    for (const season of show.seasons) {
        season.episodes = [...Object.values(season.episodes)];
    }
    show.seasons = show.seasons.filter((season) => season.episodes.length > 0);
}

unwatchedShows = unwatchedShows.filter((show) => show.seasons.length > 0);

uj5u.com熱心網友回復：

問題是您的基準測驗存在缺陷。請注意，jsbench 確實每個測驗用例只運行一次“設定代碼”，而不是每次測驗回圈迭代。

您的第一個解決方案確實改變了輸入（特別是season.episodes- 雖然它確實克隆了每個節目），所以只有在第一次運行時它才會真正給出正確的輸出。在測驗回圈的所有后續運行中，它基本上在空輸入上運行，這要快得多。

我在這里解決了這個問題，現在第二種解決方案是預期最快的。（請注意，現在還包括創建物件的時間）。

uj5u.com熱心網友回復：

我不確定您如何使用第二種解決方案獲得更快的結果，我會三重檢查結果。JSBench 結果是合法的，并且與 Big-O 表示法一致。

第一個解決方案回圈shows創建一個查找表。然后，回圈通過具有四元復雜度 O(n^2) 的嵌套回圈。

第二種解決方案通過三次復雜度 O(n^3) 的嵌套回圈回圈，因為它嵌套了三次。所以，我希望這個演算法能花更多的時間。

其原因被稱為總和規則。當兩個回圈并排放置時，它們不會相乘而是相加。這使得復雜度 O(n n^2)，可以進一步降低到 O(n^2)，因為隨著n接近無窮大，第一個回圈變得可以忽略不計。

標籤：javascript

上一篇：如何使用標頭重定向

下一篇：在rails6.0.0中使用外部javascript庫時遇到問題