js 簡單實作 LFU

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

<code>/* ======================================== LFU 最近最少使用 ======================================== */</code>

<code>function</code> <code>LFUCache(limit){</code>

<code>    </code><code>limit = limit||10;</code>

<code>    </code><code>var</code> <code>_store = []; </code><code>// 存儲資料 {count:1,data:""}</code>

<code>    </code><code>var</code> <code>index = {};</code>

<code>    </code><code>this</code><code>.get = </code><code>function</code><code>(key){</code>

<code>        </code><code>var</code> <code>ind = index[key];</code>

<code>        </code> 

<code>        </code><code>var</code> <code>result = _store[ind];</code>

<code>                </code> 

<code>        </code><code>if</code><code>(result==</code><code>null</code><code>){ </code><code>// 未命中</code>

<code>            </code><code>return</code> <code>null</code><code>;</code>

<code>        </code><code>}</code>

<code>        </code><code>var</code> <code>count = ++result.count;</code>

<code>        </code><code>var</code> <code>newInd = -1;</code>

<code>        </code><code>for</code><code>(</code><code>var</code> <code>i=0;i&lt;ind;i++){</code>

<code>            </code><code>if</code><code>(_store[i].count&lt;=count){</code>

<code>                </code><code>newInd = i;</code>

<code>                </code><code>break</code><code>;</code>

<code>            </code><code>}</code>

<code>        </code><code>// 将命中的元素移動到指定的位置</code>

<code>        </code><code>_store.splice(ind,1);</code>

<code>        </code><code>_store.splice(newInd,0,result);</code>

<code>        </code><code>for</code><code>(</code><code>var</code> <code>k </code><code>in</code> <code>index){</code>

<code>            </code><code>if</code><code>(index[k]&gt;=newInd){</code>

<code>                </code><code>index[k]=++index[k];</code>

<code>        </code><code>index[key] = newInd;</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>};</code>

<code>    </code> 

<code>    </code><code>this</code><code>.set = </code><code>function</code><code>(key,value){</code>

<code>        </code><code>if</code><code>(_store.length&gt;=limit){</code>

<code>            </code><code>_store.pop();      </code>

<code>        </code><code>// 擷取count為1的第一個數組索引</code>

<code>        </code><code>var</code> <code>oneCountIndex = -1;</code>

<code>        </code><code>for</code><code>(</code><code>var</code> <code>i=0;i&lt;_store.length;i++){</code>

<code>            </code><code>var</code> <code>count = _store[i].count;</code>

<code>            </code><code>if</code><code>(count==1){</code>

<code>                </code><code>oneCountIndex = i;</code>

<code>        </code><code>var</code> <code>item = {count:1,data:value};</code>

<code>        </code><code>if</code><code>(oneCountIndex&gt;-1){</code>

<code>            </code><code>_store.splice(oneCountIndex,0,item);</code>

<code>            </code> 

<code>            </code><code>for</code><code>(</code><code>var</code> <code>k </code><code>in</code> <code>index){</code>

<code>                </code><code>if</code><code>(index[k]&gt;=oneCountIndex){</code>

<code>                    </code><code>index[k]=++index[k];</code>

<code>                </code><code>}</code>

<code>            </code><code>index[key] = oneCountIndex;</code>

<code>        </code><code>}</code><code>else</code><code>{</code>

<code>            </code><code>_store.push(item);</code>

<code>            </code><code>index[key] = _store.length-1;</code>

<code>    </code><code>this</code><code>.list = </code><code>function</code><code>(){</code>

<code>        </code><code>console.log(JSON.stringify(_store));</code>

<code>    </code><code>};     </code>

<code>}</code>

本文轉自 antlove 51CTO部落格，原文連結:http://blog.51cto.com/antlove/1978343