第一章網絡算法學概述-在線瀏覽
2024-11-04 09:00本頁面
【正文】 理完。 ? 算法對數(shù)組有兩次遍歷： ? 新的數(shù)據(jù)包開始時，初始化 C為零。 ? 兩次遍歷至少需要 768次讀 /寫操作： ? C數(shù)組讀、寫各一次 ? T數(shù)組讀一次 算法優(yōu)化：取消 URL結束后的遍歷 ? 直觀上，掃描完 URL后檢查每個字符的出現(xiàn)比例是不必要的。 算法優(yōu)化：取消 URL結束后的遍歷 ? 基本思想：只跟蹤最高的相對出現(xiàn)次數(shù) ? 方法： ? 使用一個寄存器記錄到目前為止最高的相對出現(xiàn)次數(shù)： Max = max{C[i]/T[i]} ? 每讀入一個新字符 “ i ”， ? C[i]加 1 ? 若 C[i]/T[i]Max, Max= C[i]/T[i] ? URL掃描結束后，若 Max≥ L，標記分組。 利用硬件特性：消除除法運算 ? 改進后的處理過程： ? T[i]中存放移位的次數(shù) ? 讀入新字符 “ i”后： ? C[i]加 1 ? 左移 T[i]位 ? 若移位后的值大于 Max, 更新 Max ? 當 URL掃描結束后，如果 Max≥ L，標記分組 問題和分析 ? Q：每處理一個字節(jié)需要 2次讀和 1次寫，與樸素方案相比增加了一次讀，能否不增加讀 /寫次數(shù)？ 問題和分析 ? Q：每處理一個字節(jié)需要 2次讀和 1次寫，與樸素方案相比增加了一次讀，能否不增加讀 /寫次數(shù)？ ? 基本思路：將 C數(shù)組和 T數(shù)組合并到一個數(shù)組中，將 2次讀操作合并為 1次讀操作。（ lazy evaluation） ? 當芯片掃描到一個新的 URL、并且第一次遇到字符 “ i”時，設置 C[i]=1 ? 此后再掃描到字符“ i”時， C[i]加 1 初始化 C的開銷能不能降下來？ ? Q：有必要在每開始一個新的數(shù)據(jù)包時，清除整個 C數(shù)組嗎？ ? A：從道理上說， C[i]不需要被清除，直到一個新的數(shù)據(jù)包需要使用它。（ lazy eval
教學課件相關推薦
鄂ICP備17016276號-1