Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4b4d770

Browse files
committed
Add an example of the LRU Cache based on the Map.
1 parent69c3a16 commit4b4d770

File tree

4 files changed

+216
-3
lines changed

4 files changed

+216
-3
lines changed

‎src/data-structures/lru-cache/LRUCache.js

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ class LinkedListNode {
2424
* Implementation of the LRU (Least Recently Used) Cache
2525
* based on the HashMap and Doubly Linked List data-structures.
2626
*
27-
* Current implementation allows to have fast(O(1)) read and write operations.
27+
* Current implementation allows to have fast O(1) (in average) read and write operations.
2828
*
2929
* At any moment in time the LRU Cache holds not more that "capacity" number of items in it.
3030
*/
@@ -43,7 +43,7 @@ class LRUCache {
4343

4444
/**
4545
* Returns the cached value by its key.
46-
* Time complexity: O(1).
46+
* Time complexity: O(1) in average.
4747
*@param {string} key
4848
*@returns {any}
4949
*/
@@ -56,7 +56,7 @@ class LRUCache {
5656

5757
/**
5858
* Sets the value to cache by its key.
59-
* Time complexity: O(1).
59+
* Time complexity: O(1) in average.
6060
*@param {string} key
6161
*@param {any} val
6262
*/
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/* eslint-disable no-restricted-syntax, no-unreachable-loop */
2+
3+
/**
4+
* Implementation of the LRU (Least Recently Used) Cache
5+
* based on the (ordered) Map data-structure.
6+
*
7+
* Current implementation allows to have fast O(1) (in average) read and write operations.
8+
*
9+
* At any moment in time the LRU Cache holds not more that "capacity" number of items in it.
10+
*/
11+
classLRUCacheOnMap{
12+
/**
13+
* Creates a cache instance of a specific capacity.
14+
*@param {number} capacity
15+
*/
16+
constructor(capacity){
17+
this.capacity=capacity;// How many items to store in cache at max.
18+
this.items=newMap();// The ordered hash map of all cached items.
19+
}
20+
21+
/**
22+
* Returns the cached value by its key.
23+
* Time complexity: O(1) in average.
24+
*@param {string} key
25+
*@returns {any}
26+
*/
27+
get(key){
28+
if(!this.items.has(key))returnundefined;
29+
constval=this.items.get(key);
30+
this.items.delete(key);
31+
this.items.set(key,val);
32+
returnval;
33+
}
34+
35+
/**
36+
* Sets the value to cache by its key.
37+
* Time complexity: O(1).
38+
*@param {string} key
39+
*@param {any} val
40+
*/
41+
set(key,val){
42+
this.items.delete(key);
43+
this.items.set(key,val);
44+
if(this.items.size>this.capacity){
45+
for(constheadKeyofthis.items.keys()){
46+
this.items.delete(headKey);
47+
break;
48+
}
49+
}
50+
}
51+
}
52+
53+
exportdefaultLRUCacheOnMap;

‎src/data-structures/lru-cache/README.md

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,8 @@ The functions `get()` and `set()` must each run in `O(1)` average time complexit
1616

1717
##Implementation
1818

19+
###Version 1: Doubly Linked List + Hash Map
20+
1921
See the`LRUCache` implementation example in[LRUCache.js](./LRUCache.js). The solution uses a`HashMap` for fast`O(1)` (in average) cache items access, and a`DoublyLinkedList` for fast`O(1)` (in average) cache items promotions and eviction (to keep the maximum allowed cache capacity).
2022

2123
![Linked List](./images/lru-cache.jpg)
@@ -24,6 +26,16 @@ See the `LRUCache` implementation example in [LRUCache.js](./LRUCache.js). The s
2426

2527
You may also find more test-case examples of how the LRU Cache works in[LRUCache.test.js](./__test__/LRUCache.test.js) file.
2628

29+
###Version 2: Ordered Map
30+
31+
The first implementation that uses doubly linked list is good for learning purposes and for better understanding of how the average`O(1)` time complexity is achievable while doing`set()` and`get()`.
32+
33+
However, the simpler approach might be to use a JavaScript[Map](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map) object. The`Map` object holds key-value pairs and**remembers the original insertion order** of the keys. We can use this fact in order to keep the recently-used items in the "end" of the map by removing and re-adding items. The item at the beginning of the`Map` is the first one to be evicted if cache capacity overflows. The order of the items may checked by using the`IterableIterator` like`map.keys()`.
34+
35+
See the`LRUCacheOnMap` implementation example in[LRUCacheOnMap.js](./LRUCacheOnMap.js).
36+
37+
You may also find more test-case examples of how the LRU Cache works in[LRUCacheOnMap.test.js](./__test__/LRUCacheOnMap.test.js) file.
38+
2739
##Complexities
2840

2941
|| Average|
Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
importLRUCachefrom'../LRUCacheOnMap';
2+
3+
describe('LRUCacheOnMap',()=>{
4+
it('should set and get values to and from the cache',()=>{
5+
constcache=newLRUCache(100);
6+
expect(cache.get('key-1')).toBeUndefined();
7+
8+
cache.set('key-1',15);
9+
cache.set('key-2',16);
10+
cache.set('key-3',17);
11+
expect(cache.get('key-1')).toBe(15);
12+
expect(cache.get('key-2')).toBe(16);
13+
expect(cache.get('key-3')).toBe(17);
14+
expect(cache.get('key-3')).toBe(17);
15+
expect(cache.get('key-2')).toBe(16);
16+
expect(cache.get('key-1')).toBe(15);
17+
18+
cache.set('key-1',5);
19+
cache.set('key-2',6);
20+
cache.set('key-3',7);
21+
expect(cache.get('key-1')).toBe(5);
22+
expect(cache.get('key-2')).toBe(6);
23+
expect(cache.get('key-3')).toBe(7);
24+
});
25+
26+
it('should evict least recently used items from cache with cache size of 1',()=>{
27+
constcache=newLRUCache(1);
28+
expect(cache.get('key-1')).toBeUndefined();
29+
30+
cache.set('key-1',15);
31+
expect(cache.get('key-1')).toBe(15);
32+
33+
cache.set('key-2',16);
34+
expect(cache.get('key-1')).toBeUndefined();
35+
expect(cache.get('key-2')).toBe(16);
36+
37+
cache.set('key-2',17);
38+
expect(cache.get('key-2')).toBe(17);
39+
40+
cache.set('key-3',18);
41+
cache.set('key-4',19);
42+
expect(cache.get('key-2')).toBeUndefined();
43+
expect(cache.get('key-3')).toBeUndefined();
44+
expect(cache.get('key-4')).toBe(19);
45+
});
46+
47+
it('should evict least recently used items from cache with cache size of 2',()=>{
48+
constcache=newLRUCache(2);
49+
expect(cache.get('key-21')).toBeUndefined();
50+
51+
cache.set('key-21',15);
52+
expect(cache.get('key-21')).toBe(15);
53+
54+
cache.set('key-22',16);
55+
expect(cache.get('key-21')).toBe(15);
56+
expect(cache.get('key-22')).toBe(16);
57+
58+
cache.set('key-22',17);
59+
expect(cache.get('key-22')).toBe(17);
60+
61+
cache.set('key-23',18);
62+
expect(cache.get('key-21')).toBeUndefined();
63+
expect(cache.get('key-22')).toBe(17);
64+
expect(cache.get('key-23')).toBe(18);
65+
66+
cache.set('key-24',19);
67+
expect(cache.get('key-21')).toBeUndefined();
68+
expect(cache.get('key-22')).toBeUndefined();
69+
expect(cache.get('key-23')).toBe(18);
70+
expect(cache.get('key-24')).toBe(19);
71+
});
72+
73+
it('should evict least recently used items from cache with cache size of 3',()=>{
74+
constcache=newLRUCache(3);
75+
76+
cache.set('key-1',1);
77+
cache.set('key-2',2);
78+
cache.set('key-3',3);
79+
expect(cache.get('key-1')).toBe(1);
80+
expect(cache.get('key-2')).toBe(2);
81+
expect(cache.get('key-3')).toBe(3);
82+
83+
cache.set('key-3',4);
84+
expect(cache.get('key-1')).toBe(1);
85+
expect(cache.get('key-2')).toBe(2);
86+
expect(cache.get('key-3')).toBe(4);
87+
88+
cache.set('key-4',5);
89+
expect(cache.get('key-1')).toBeUndefined();
90+
expect(cache.get('key-2')).toBe(2);
91+
expect(cache.get('key-3')).toBe(4);
92+
expect(cache.get('key-4')).toBe(5);
93+
});
94+
95+
it('should promote the node while calling set() method',()=>{
96+
constcache=newLRUCache(2);
97+
98+
cache.set('2',1);
99+
cache.set('1',1);
100+
cache.set('2',3);
101+
cache.set('4',1);
102+
expect(cache.get('1')).toBeUndefined();
103+
expect(cache.get('2')).toBe(3);
104+
});
105+
106+
it('should promote the recently accessed item with cache size of 3',()=>{
107+
constcache=newLRUCache(3);
108+
109+
cache.set('key-1',1);
110+
cache.set('key-2',2);
111+
cache.set('key-3',3);
112+
expect(cache.get('key-1')).toBe(1);
113+
114+
cache.set('key-4',4);
115+
expect(cache.get('key-1')).toBe(1);
116+
expect(cache.get('key-3')).toBe(3);
117+
expect(cache.get('key-4')).toBe(4);
118+
expect(cache.get('key-2')).toBeUndefined();
119+
});
120+
121+
it('should promote the recently accessed item with cache size of 4',()=>{
122+
constcache=newLRUCache(4);
123+
124+
cache.set('key-1',1);
125+
cache.set('key-2',2);
126+
cache.set('key-3',3);
127+
cache.set('key-4',4);
128+
expect(cache.get('key-4')).toBe(4);
129+
expect(cache.get('key-3')).toBe(3);
130+
expect(cache.get('key-2')).toBe(2);
131+
expect(cache.get('key-1')).toBe(1);
132+
133+
cache.set('key-5',5);
134+
expect(cache.get('key-1')).toBe(1);
135+
expect(cache.get('key-2')).toBe(2);
136+
expect(cache.get('key-3')).toBe(3);
137+
expect(cache.get('key-4')).toBeUndefined();
138+
expect(cache.get('key-5')).toBe(5);
139+
140+
cache.set('key-6',6);
141+
expect(cache.get('key-1')).toBeUndefined();
142+
expect(cache.get('key-2')).toBe(2);
143+
expect(cache.get('key-3')).toBe(3);
144+
expect(cache.get('key-4')).toBeUndefined();
145+
expect(cache.get('key-5')).toBe(5);
146+
expect(cache.get('key-6')).toBe(6);
147+
});
148+
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp