a791. 13. Least Recently Used
Tags :
Accepted rate : 53人/73人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-10-26 14:28

Content
我們總想要更快、更便宜、容量更大的電腦,最少使用法則( The Least Recently Used algorithm )提供了電腦設計者一個同樣成本但能提升系統效能的方式,這當然不是拿讀寫快速的記憶體取代讀寫較慢的硬碟,但很接近這個想法。

我們常用Byte或者GB來當作記憶體和硬體容量的單位,記憶體一個分頁只有4KB而已,而硬碟的儲存量卻比記憶體分頁多得多,而且儲存時的消耗也比較少,但是硬碟的讀寫速度明顯比記憶體慢。我們都希望有朝一日硬碟讀取速度能比的上記憶體,但至少現在還做不到。

現在有一個方式可以提升硬碟的效能--學者們指出電腦在使用硬碟分頁時,會重複使用一些分頁,而其他分頁變得很少被使用--這些沒被用到的區塊恰好被設計者拿來存放常用硬碟分頁的資料,而這些幾乎未被用到的記憶空間被稱為快取( cache ),當然有快取也得有演算法搭配,當程式在使用硬碟資料時會先查看這個資料分頁是不是快取,如果是的話,則稱為"快取命中"( cache hit ),這塊快取就會被轉換成記憶體使用,這非常快。若不是,則稱為"快取失效"( cache miss ),系統會再抓其他分頁來看。各種快取演算的重點是快取的汰換策略。在本題中,我們的策略是把快取失敗的分頁取代最長時間內未使用的快取分頁。如此一來,則無論命中或失效,現有的快取分頁都會變成最近使用過的分頁。
 
假設硬碟容量有1024個分頁( 從0開始 ),且有16個分頁的記憶體可當快取,請寫一個程式算出快取命中率。 

Input
輸入多行,每行20個數字,由左而右代表系統要求的分頁編號。
Output
請輸出累積過後的快取命中率,用百分比表示,可以假設一開始沒有分頁被用過。
Sample Input #1
390 444 390 591 556 635 259 960 701 398 344 396 339 690 874 960 418 635 875 390
390 581 960 14 390 960 500 390 731 398 623 344 398 960 417 390 390 355 344 134
Sample Output #1
cache hit rate: 20.00%
cache hit rate: 40.00%
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (25%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
公開 測資點#2 (25%): 1.0s , <1K
公開 測資點#3 (25%): 1.0s , <1K
Hint :
Tags:
出處:
HP CodeWars2008 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」