lru算法java代碼 lru算法 js

LRU算法 O(1)時間復雜度

實現LRU算法，查找刪除時間復雜度都為O(1)

鳳慶網站制作公司哪家好，找成都創新互聯！從網頁設計、網站建設、微信開發、APP開發、成都響應式網站建設等網站項目制作，到程序開發，運營維護。成都創新互聯自2013年創立以來到現在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網站建設就選成都創新互聯。

LRU Cache是一個Cache置換算法，含義是“最近最少使用”，當Cache滿（沒有空閑的cache塊）時，把滿足“最近最少使用”的數據從Cache中置換出去，并且保證Cache中第一個數據是最近剛剛訪問的

實現思路

利用hashmap加鏈表來實現這個原理

鏈表元素node由兩個元素構成（key-value），在hashmap中存入node的key值，以及node；hashmap的構成為Integer,Node

為保證每次查找為O(1)并要判斷雙向鏈表里面是否含有元素，所以要將node設為兩個值，key和value，其中node的key與map的值相同，當hashmap中存在key的時候，則雙向鏈表中也存在key。利用這個特質，能完成查找刪除都為O(1)

將最小使用的元素刪除，核心就是每次插入的時候，都插入到鏈表的頭結點；每次get一個元素時候，將get的那個元素刪除，然后將元素插入到頭結點

java代碼怎么設定啟動時的JVM參數

不管是YGC還是Full GC,GC過程中都會對導致程序運行中中斷,正確的選擇不同的GC策略,調整JVM、GC的參數，可以極大的減少由于GC工作，而導致的程序運行中斷方面的問題，進而適當的提高Java程序的工作效率。但是調整GC是以個極為復雜的過程，由于各個程序具備不同的特點，如：web和GUI程序就有很大區別（Web可以適當的停頓，但GUI停頓是客戶無法接受的），而且由于跑在各個機器上的配置不同（主要cup個數，內存不同），所以使用的GC種類也會不同(如何選擇見GC種類及如何選擇)。本文將注重介紹JVM、GC的一些重要參數的設置來提高系統的性能。

GC性能方面的考慮

對于GC的性能主要有2個方面的指標：吞吐量throughput（工作時間不算gc的時間占總的時間比）和暫停pause（gc發生時app對外顯示的無法響應）。

1. Total Heap

默認情況下，vm會增加/減少heap大小以維持free space在整個vm中占的比例，這個比例由MinHeapFreeRatio和MaxHeapFreeRatio指定。

一般而言，server端的app會有以下規則：

對vm分配盡可能多的memory；

將Xms和Xmx設為一樣的值。如果虛擬機啟動時設置使用的內存比較小，這個時候又需要初始化很多對象，虛擬機就必須重復地增加內存。

處理器核數增加，內存也跟著增大。

2. The Young Generation

另外一個對于app流暢性運行影響的因素是young generation的大小。young generation越大，minor collection越少；但是在固定heap size情況下，更大的young generation就意味著小的tenured generation，就意味著更多的major collection(major collection會引發minor collection)。

NewRatio反映的是young和tenured generation的大小比例。NewSize和MaxNewSize反映的是young generation大小的下限和上限，將這兩個值設為一樣就固定了young generation的大小（同Xms和Xmx設為一樣）。

如果希望，SurvivorRatio也可以優化survivor的大小，不過這對于性能的影響不是很大。SurvivorRatio是eden和survior大小比例。

一般而言，server端的app會有以下規則：

首先決定能分配給vm的最大的heap size，然后設定最佳的young generation的大小；

如果heap size固定后，增加young generation的大小意味著減小tenured generation大小。讓tenured generation在任何時候夠大，能夠容納所有live的data（留10%-20%的空余）。

經驗規則

年輕代大小選擇

響應時間優先的應用:盡可能設大,直到接近系統的最低響應時間限制(根據實際情況選擇).在此種情況下,年輕代收集發生的頻率也是最小的.同時,減少到達年老代的對象.

吞吐量優先的應用:盡可能的設置大,可能到達Gbit的程度.因為對響應時間沒有要求,垃圾收集可以并行進行,一般適合8CPU以上的應用.

避免設置過小.當新生代設置過小時會導致:1.YGC次數更加頻繁 2.可能導致YGC對象直接進入舊生代,如果此時舊生代滿了,會觸發FGC.

年老代大小選擇

響應時間優先的應用:年老代使用并發收集器,所以其大小需要小心設置,一般要考慮并發會話率和會話持續時間等一些參數.如果堆設置小了,可以會造成內存碎 片,高回收頻率以及應用暫停而使用傳統的標記清除方式;如果堆大了,則需要較長的收集時間.最優化的方案,一般需要參考以下數據獲得:

并發垃圾收集信息、持久代并發收集次數、傳統GC信息、花在年輕代和年老代回收上的時間比例。

吞吐量優先的應用:一般吞吐量優先的應用都有一個很大的年輕代和一個較小的年老代.原因是,這樣可以盡可能回收掉大部分短期對象,減少中期的對象,而年老代盡存放長期存活對象.

較小堆引起的碎片問題

因為年老代的并發收集器使用標記,清除算法,所以不會對堆進行壓縮.當收集器回收時,他會把相鄰的空間進行合并,這樣可以分配給較大的對象.但是,當堆空間較小時,運行一段時間以后,就會出現"碎片",如果并發收集器找不到足夠的空間,那么并發收集器將會停止,然后使用傳統的標記,清除方式進行回收.如果出現"碎片",可能需要進行如下配置:

-XX:+UseCMSCompactAtFullCollection:使用并發收集器時,開啟對年老代的壓縮.

-XX:CMSFullGCsBeforeCompaction=0:上面配置開啟的情況下,這里設置多少次Full GC后,對年老代進行壓縮

用64位操作系統，Linux下64位的jdk比32位jdk要慢一些，但是吃得內存更多，吞吐量更大

XMX和XMS設置一樣大，MaxPermSize和MinPermSize設置一樣大，這樣可以減輕伸縮堆大小帶來的壓力

使用CMS的好處是用盡量少的新生代，經驗值是128M－256M， 然后老生代利用CMS并行收集， 這樣能保證系統低延遲的吞吐效率。 實際上cms的收集停頓時間非常的短，2G的內存， 大約20－80ms的應用程序停頓時間

系統停頓的時候可能是GC的問題也可能是程序的問題，多用jmap和jstack查看，或者killall -3 java，然后查看java控制臺日志，能看出很多問題。(相關工具的使用方法將在后面的blog中介紹)

仔細了解自己的應用，如果用了緩存，那么年老代應該大一些，緩存的HashMap不應該無限制長，建議采用LRU算法的Map做緩存，LRUMap的最大長度也要根據實際情況設定。

采用并發回收時，年輕代小一點，年老代要大，因為年老大用的是并發回收，即使時間長點也不會影響其他程序繼續運行，網站不會停頓

JVM參數的設置(特別是 –Xmx –Xms –Xmn -XX:SurvivorRatio -XX:MaxTenuringThreshold等參數的設置沒有一個固定的公式，需要根據PV old區實際數據 YGC次數等多方面來衡量。為了避免promotion faild可能會導致xmn設置偏小，也意味著YGC的次數會增多，處理并發訪問的能力下降等問題。每個參數的調整都需要經過詳細的性能測試，才能找到特定應用的最佳配置。

promotion failed:

垃圾回收時promotion failed是個很頭痛的問題，一般可能是兩種原因產生，第一個原因是救助空間不夠，救助空間里的對象還不應該被移動到年老代，但年輕代又有很多對象需要放入救助空間；第二個原因是年老代沒有足夠的空間接納來自年輕代的對象；這兩種情況都會轉向Full GC，網站停頓時間較長。

解決方方案一：

第一個原因我的最終解決辦法是去掉救助空間，設置-XX:SurvivorRatio=65536 -XX:MaxTenuringThreshold=0即可，第二個原因我的解決辦法是設置CMSInitiatingOccupancyFraction為某個值（假設70），這樣年老代空間到70%時就開始執行CMS，年老代有足夠的空間接納來自年輕代的對象。

解決方案一的改進方案：

又有改進了，上面方法不太好，因為沒有用到救助空間，所以年老代容易滿，CMS執行會比較頻繁。我改善了一下，還是用救助空間，但是把救助空間加大，這樣也不會有promotion failed。具體操作上，32位Linux和64位Linux好像不一樣，64位系統似乎只要配置MaxTenuringThreshold參數，CMS還是有暫停。為了解決暫停問題和promotion failed問題，最后我設置-XX:SurvivorRatio=1 ，并把MaxTenuringThreshold去掉，這樣即沒有暫停又不會有promotoin failed，而且更重要的是，年老代和永久代上升非常慢（因為好多對象到不了年老代就被回收了），所以CMS執行頻率非常低，好幾個小時才執行一次，這樣，服務器都不用重啟了。

-Xmx4000M -Xms4000M -Xmn600M -XX:PermSize=500M -XX:MaxPermSize=500M -Xss256K -XX:+DisableExplicitGC -XX:SurvivorRatio=1 -XX:+UseConcMarkSweepGC -XX:+UseParNewGC -XX:+CMSParallelRemarkEnabled -XX:+UseCMSCompactAtFullCollection -XX:CMSFullGCsBeforeCompaction=0 -XX:+CMSClassUnloadingEnabled -XX:LargePageSizeInBytes=128M -XX:+UseFastAccessorMethods -XX:+UseCMSInitiatingOccupancyOnly -XX:CMSInitiatingOccupancyFraction=80 -XX:SoftRefLRUPolicyMSPerMB=0 -XX:+PrintClassHistogram -XX:+PrintGCDetails -XX:+PrintGCTimeStamps -XX:+PrintHeapAtGC -Xloggc:log/gc.log

CMSInitiatingOccupancyFraction值與Xmn的關系公式

上面介紹了promontion faild產生的原因是EDEN空間不足的情況下將EDEN與From survivor中的存活對象存入To survivor區時,To survivor區的空間不足，再次晉升到old gen區，而old gen區內存也不夠的情況下產生了promontion faild從而導致full gc.那可以推斷出：eden+from survivor old gen區剩余內存時，不會出現promontion faild的情況，即：

(Xmx-Xmn)*(1-CMSInitiatingOccupancyFraction/100)=(Xmn-Xmn/(SurvivorRatior+2)) 進而推斷出：

CMSInitiatingOccupancyFraction =((Xmx-Xmn)-(Xmn-Xmn/(SurvivorRatior+2)))/(Xmx-Xmn)*100

例如：

當xmx=128 xmn=36 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((128.0-36)-(36-36/(1+2)))/(128-36)*100 =73.913

當xmx=128 xmn=24 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((128.0-24)-(24-24/(1+2)))/(128-24)*100=84.615…

當xmx=3000 xmn=600 SurvivorRatior=1時 CMSInitiatingOccupancyFraction=((3000.0-600)-(600-600/(1+2)))/(3000-600)*100=83.33

CMSInitiatingOccupancyFraction低于70% 需要調整xmn或SurvivorRatior值。

C++實現LRU算法

#includeiostream

using namespace std;

int size;

int *w;

//定義一個動態數組

struct mem

{

int num;

int count;

}memBlock[3]={0,0,0,0,0,0};

void LRU()

{

for( int i = 0; i size; i++ )

{

int maxCount = memBlock[0].count;

int maxPos = 0;

int j = 0;

bool bFind = false;

for( j = 0; j 3; j++ )

{

// 標記出count值最大的位置

if( maxCount memBlock[j].count )

{

maxCount = memBlock[j].count;

maxPos = j;

}

// 將所有的count值都+1

memBlock[j].count++;

// 如果命中，將其count值置為0

if( w[i] == memBlock[j].num )

{

memBlock[j].count = 0;

bFind = true;

}

}

// 未命中，將count最大的拿來替換

if( !bFind )

{

memBlock[maxPos].num = w[i];

memBlock[maxPos].count = 0;

}

for(j = 0; j 3; j++) //輸出

cout memBlock[j].num " ";

cout " " endl;

}

}

int main() //主函數

{

cout"請輸入需訪問的頁面數量:"endl;

cinsize;

w = new int[size];

cout"請輸入需要訪問的頁面"endl;

for(int a=0;asize;a++)

{

cinw[a];//輸入數組

}

coutendl"(LRU)"endl;

LRU();

return 0;

}

引用 ： 回答者： floxer | 三級

分享文章：lru算法java代碼 lru算法 js
網頁鏈接：http://m.kartarina.com/article22/hgjjcc.html

成都網站建設公司_創新互聯，為您提供App開發、全網營銷推廣、用戶體驗、網站營銷、建站公司、

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯