UA SIE545 優化理論基礎9 優先與分治策略1 文件的最優存儲順序

• 單磁帶存儲
• • 相同查詢頻率
  • 相同文件長度
  • 查詢頻率與文件長度均不同

單磁帶存儲

相同查詢頻率

這一章介紹優先策略與分治策略，我們從一個簡單的例子開始介紹優先策略?？紤]非常簡單的磁帶存儲問題：如果我們把$n$個文件存儲在磁帶上，那么這$n$個文件只能按存儲順序進行讀寫，假設$L_i,i=1,?,n$表示第$i$個文件長度，假設查詢每個文件的概率相同，求最優的文件存儲順序。

假設$\sigma$表示一個$n$階的排列，即$\sigma \in P_n$。我們可以用排列來表示文件存儲的順序，即$\sigma (1),?,\sigma (n)$，其中$\sigma (i)\in \{1,?,n\}$表示第$i$個文件被存放在第$\sigma (i)$個位置，記$j=\sigma (i)$，則第$i$個文件前面還有$j?1$個文件，讀完第$i$個文件需要的總長度為
$$\sum _{k=1}^j{L}_{{\sigma }^{?1}(k)}$$

基于這個發現，我們可以計算給定一個排列，查詢一次文件平均需要讀的長度，并且以此定義尋找最優存儲順序的最優化問題：
$$\underset{\sigma \in P_n}{\min }\frac{1}{n}\sum _{j=1}^n\sum _{k=1}^j{L}_{{\sigma }^{?1}(k)}$$

因為查詢每個文件的概率相同，直覺上我們應該把小文件放前面，大文件放在后面，也就是$\sigma$要滿足
$$L_{{\sigma }^{?1}(1)}\le ?\le L_{{\sigma }^{?1}(n)}$$

證明
注意到${\sigma }^{?1}$也是一個$n$階排列，記$\tau ={\sigma }^{?1},\tau \in P_n$。定義
$$S(\tau )=\sum _{j=1}^n\sum _{k=1}^j{L}_{\tau (k)}=\sum _{k=1}^n(n?k+1)L_{\tau (k)}$$

假設$\tau$使得字長滿足
$$L_{\tau (1)}\le ?\le L_{\tau (n)}$$

如果交換${\tau }_i$與${\tau }_j$ ($j>i$)，即定義${\tau }^{\prime }$滿足
$${\tau }^{\prime }=\left(\begin{array}{ccccccc}1& ?& i& ?& j& ?& n\\ \tau (1)& ?& \tau (j)& ?& \tau (i)& ?& \tau (n)\end{array}\right)$$

那么這會導致$S$增加
$$\begin{gathered} S({\tau }^{\prime })?S(\tau )=[(n?i+1)L_{\tau (j)}+(n?j+1)L_{\tau (i)}] \\ ?[(n?i+1)L_{\tau (i)}+(n?j+1)L_{\tau (j)}]=(j?i)(L_{\tau (j)}?L_{\tau (i)})>0 \end{gathered}$$

因此
$$\tau =\underset{\sigma \in P_n}{\mathrm{argmin}}\frac{1}{n}\sum _{j=1}^n\sum _{k=1}^j{L}_{{\sigma }^{?1}(k)}$$
證畢

相同文件長度

假設$n$個文件長度相同，但查詢頻率分別為$f_1,?,f_n$，其中
$$f_1+?+f_n=1$$

則最優存儲順序為查詢頻率高的文件放在前面，查詢頻率低的文件放后面。

證明
同樣用$n$階排列表示存放順序，并且不失一般性，用1表示文件長度，則讀完第$i$個文件需要的總長度為
$$\sum _{k=1}^{j}1=j$$

對應的頻率是$f_{{\sigma }^{?1}(j)}$，因此這時的最優化問題變成了
$$\underset{\sigma \in P_n}{\min }\sum _{j=1}^{n}j{f}_{{\sigma }^{?1}(j)}$$

記$\tau ={\sigma }^{?1},\tau \in P_n$。定義
$$S(\tau )=\sum _{j=1}^{n}j{f}_{\tau (j)}$$

假設$\tau$使得查詢頻率滿足
$$f_{\tau (1)}\ge ?\ge f_{\tau (n)}$$

沿用上一個證明對${\tau }^{\prime }$的證明，計算

$$\begin{gathered} S({\tau }^{\prime })?S(\tau )=[i{f}_{\tau (j)}+j{f}_{\tau (i)}]?[i{f}_{\tau (i)}+j{f}_{\tau (j)}] \\ =(j?i)(f_{\tau (i)}?f_{\tau (j)})>0 \end{gathered}$$

證畢

查詢頻率與文件長度均不同

假設$n$個文件長度不同，并且查詢頻率也不同，最優存儲順序為平均每字查詢頻率高的文件放在前面，平均每字查詢頻率低的文件放后面。
證明
證明方法與前文完全一樣。讀完第$i$個文件需要的總長度為
$$\sum _{k=1}^j{L}_{{\sigma }^{?1}(k)}$$

對應的頻率是$f_{{\sigma }^{?1}(j)}$，因此最優化問題可以寫成
$$\underset{\sigma \in P_n}{\min }\sum _{j=1}^n{f}_{{\sigma }^{?1}(j)}\sum _{k=1}^j{L}_{{\sigma }^{?1}(k)}$$

記$\tau ={\sigma }^{?1},\tau \in P_n$使之滿足
$$f_{\tau (1)}/L_{\tau (1)}\ge ?\ge f_{\tau (n)}/L_{\tau (n)}$$

用前兩個證明的思路，可以說明$\tau$是最優解。

證畢

根據上面的論述，在計算上，我們把最優存儲問題變成了排序問題，這就是優先策略的體現，因為我們是按照平均每字查詢頻率優先的原則對文件進行排序的。對于這一類找最優pecking order的問題，優化的目標是最大化gain或者最小化cost，在確定pecking order的時候，我們應該按每一次pecking的marginal gain最大、或者marginal cost最小的原則進行，這就是優先策略的思想。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的UA SIE545 优化理论基础9 优先与分治策略1 文件的最优存储顺序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。