{"id":568,"date":"2024-11-16T21:42:46","date_gmt":"2024-11-16T13:42:46","guid":{"rendered":"https:\/\/womeifei.cn\/?p=568"},"modified":"2024-11-18T20:48:48","modified_gmt":"2024-11-18T12:48:48","slug":"lru%e7%bc%93%e5%ad%98-%e5%8a%9b%e6%89%a3146","status":"publish","type":"post","link":"https:\/\/womeifei.cn\/index.php\/2024\/11\/16\/lru%e7%bc%93%e5%ad%98-%e5%8a%9b%e6%89%a3146\/","title":{"rendered":"LRU\u7f13\u5b58-\u529b\u6263146"},"content":{"rendered":"\n

\u8fd9\u662f\u4e00\u9053\u9762\u8bd5\u4e2d\u5e38\u8003\u7684\u7b97\u6cd5\u9898 \u8003\u5bdf\u9891\u5ea6\u975e\u5e38\u9ad8 \u6240\u4ee5\u5fc5\u987b\u8981\u4e86\u89e3<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u4f46\u662f\u6211\u4eec\u4e5f\u4e0d\u8981\u90a3\u4e48\u529f\u5229 \u65e2\u7136\u8fd9\u4e2a\u9898\u8003\u5bdf\u9891\u7387\u5982\u6b64\u4e4b\u9ad8 \u90a3\u5b83\u7684\u80cc\u540e\u80af\u5b9a\u6709\u66f4\u591a\u6709\u4ef7\u503c\u7684\u4e1c\u897f\u7b49\u7740\u6211\u4eec\u53bb\u63a2\u7d22 \u6240\u4ee5\u5148\u7b80\u5355\u4ecb\u7ecd\u4e00\u4e0bLRU\u5230\u5e95\u662f\u4ec0\u4e48<\/p>\n\n\n\n

\u7b80\u5355\u4ecb\u7ecd<\/p>\n\n\n\n

LRU\u7f13\u5b58(Least Recently Used Cache<\/strong>) \u662f\u4e00\u79cd\u5e38\u7528\u7684\u7f13\u5b58\u6dd8\u6c70\u7b56\u7565<\/strong> \u5176\u6838\u5fc3\u601d\u60f3\u662f\u4f18\u5148\u79fb\u9664\u957f\u65f6\u95f4\u672a\u88ab\u8bbf\u95ee\u7684\u6570\u636e\u9879 \u4ee5\u786e\u4fdd\u7f13\u5b58\u4e2d\u59cb\u7ec8\u5b58\u50a8\u6700\u65b0\u548c\u6700\u9891\u7e41\u4f7f\u7528\u7684\u6570\u636e<\/strong> <\/p>\n\n\n\n

LRU\u7f13\u5b58\u57fa\u4e8e\u201c\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\u201d<\/strong>\u7684\u539f\u5219\uff0c\u5f53\u4e00\u4e2a\u6570\u636e\u9879\u88ab\u8bbf\u95ee\u65f6\uff0c\u5982\u679c\u8be5\u6570\u636e\u5df2\u7ecf\u5728\u7f13\u5b58\u4e2d\uff0c\u5219\u5c06\u5176\u79fb\u52a8\u5230\u7f13\u5b58\u7684\u6700\u524d\u9762\uff0c\u8868\u793a\u6700\u8fd1\u88ab\u8bbf\u95ee\u8fc7\uff1b\u5982\u679c\u7f13\u5b58\u5df2\u6ee1\uff0c\u5219\u79fb\u9664\u6700\u4e45\u672a\u88ab\u8bbf\u95ee\u7684\u6570\u636e\u9879\uff0c\u4e3a\u65b0\u7684\u6570\u636e\u9879\u817e\u51fa\u7a7a\u95f4\u200c<\/p>\n\n\n\n

\u5de5\u4f5c\u539f\u7406<\/p>\n\n\n\n

LRU\u7f13\u5b58\u901a\u8fc7\u7ef4\u62a4\u4e00\u4e2a\u6709\u5e8f\u7684\u8bbf\u95ee\u961f\u5217\u6765\u5b9e\u73b0\u5176\u529f\u80fd\u3002\u5177\u4f53\u6765\u8bf4\uff0c\u53ef\u4ee5\u4f7f\u7528\u53cc\u5411\u94fe\u8868<\/strong><\/a>\u6765\u7ef4\u62a4\u8fd9\u4e2a\u8bbf\u95ee\u961f\u5217\uff0c\u94fe\u8868\u4e2d\u7684\u8282\u70b9\u6309\u7167\u6570\u636e\u7684\u8bbf\u95ee\u987a\u5e8f\u6392\u5217\u3002\u6700\u8fd1\u88ab\u8bbf\u95ee\u7684\u6570\u636e\u9879\u4f4d\u4e8e\u94fe\u8868\u7684\u524d\u90e8\uff0c\u800c\u6700\u4e45\u672a\u88ab\u8bbf\u95ee\u7684\u6570\u636e\u9879\u4f4d\u4e8e\u94fe\u8868\u7684\u5c3e\u90e8<\/strong>\u3002\u5f53\u67d0\u4e2a\u6570\u636e\u88ab\u8bbf\u95ee\u65f6\uff0c\u5982\u679c\u8be5\u6570\u636e\u5df2\u7ecf\u5b58\u5728\u4e8e\u7f13\u5b58\u4e2d\uff0c\u5c31\u5c06\u5176\u79fb\u52a8\u5230\u94fe\u8868\u7684\u5934\u90e8\uff1b\u5982\u679c\u7f13\u5b58\u5df2\u6ee1\uff0c\u5219\u79fb\u9664\u94fe\u8868\u5c3e\u90e8\u7684\u6570\u636e\u9879\u200c<\/p>\n\n\n\n

\u5177\u4f53\u7684\u5e94\u7528\u573a\u666f<\/p>\n\n\n\n

\u200c Web\u670d\u52a1\u5668<\/a>\u9875\u9762\u7f13\u5b58<\/strong>\u200c\uff1a\u5728Web\u670d\u52a1\u5668\u4e2d\uff0cLRU\u7f13\u5b58\u5e38\u7528\u4e8e\u5b58\u50a8\u9875\u9762\u5185\u5bb9\u6216\u8d44\u6e90\u6587\u4ef6\uff0c\u5982HTML\u3001CSS\u3001JavaScript\u7b49\u3002\u5f53\u7528\u6237\u8bf7\u6c42\u8bbf\u95ee\u67d0\u4e2a\u9875\u9762\u65f6\uff0cWeb\u670d\u52a1\u5668\u4f1a\u9996\u5148\u68c0\u67e5\u7f13\u5b58\u4e2d\u662f\u5426\u5b58\u5728\u8be5\u9875\u9762\u7684\u7f13\u5b58\u526f\u672c\uff0c\u5982\u679c\u5b58\u5728\uff0c\u5219\u76f4\u63a5\u8fd4\u56de\u7f13\u5b58\u7684\u9875\u9762\u5185\u5bb9\u200c<\/strong><\/p>\n\n\n\n

\u200c \u6570\u636e\u5e93\u67e5\u8be2\u4f18\u5316<\/a><\/strong>\u200c\uff1a\u5728\u6570\u636e\u5e93\u67e5\u8be2\u4e2d\uff0cLRU\u7f13\u5b58\u53ef\u4ee5\u4f18\u5316\u67e5\u8be2\u6548\u7387\uff0c\u51cf\u5c11\u5bf9\u78c1\u76d8\u7684\u8bbf\u95ee\u6b21\u6570<\/p>\n\n\n\n

\u200c\u7f51\u7edc\u670d\u52a1\u5668\u6027\u80fd\u63d0\u5347<\/a><\/strong>\u200c\uff1a\u901a\u8fc7\u4f7f\u7528LRU\u7f13\u5b58\uff0c\u53ef\u4ee5\u63d0\u5347\u7f51\u7edc\u670d\u52a1\u5668\u7684\u54cd\u5e94\u901f\u5ea6\u548c\u6027\u80fd\u200c<\/p>\n\n\n\n

\u5b9e\u73b0LRU\u7f13\u5b58\u7684\u7b97\u6cd5\u8fd8\u662fvue\u4e2dkeep-alive\u7ec4\u4ef6\u7684\u6838\u5fc3\u7b97\u6cd5<\/strong> \u548c\u6211\u4eec\u5373\u5c06\u5b66\u4e60\u7684vue\u6846\u67b6\u4e5f\u6709\u7740\u5f88\u5927\u7684\u5173\u7cfb \u6240\u4ee5\u524d\u7aefer\u4e5f\u8981\u91cd\u89c6\u8d77\u6765!!!<\/p>\n\n\n\n

\u4e0a\u9898!!!<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u5230\u5e95\u8981\u600e\u4e48\u53bb\u5b9e\u73b0\u6ee1\u8db3LRU\u7f13\u5b58\u7ea6\u675f\u7684\u6570\u636e\u7ed3\u6784\u5462?<\/p>\n\n\n\n

\u8fd9\u5e76\u4e0d\u7b80\u5355 \u4f46\u662f\u6211\u4eec\u53ef\u4ee5\u5c06\u95ee\u9898\u8f6c\u5316\u4e00\u4e0b \u53ef\u4ee5\u7528\u79fb\u52a8\u4e00\u645e\u4e66\u7684\u4f8b\u5b50\u6765\u611f\u53d7\u4e00\u4e0b\u8fd9\u4e2a\u673a\u5236<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u662f\u4e0d\u662f\u5f88\u5de7\u5999\u5462? \u53c8\u6839\u636e\u6211\u4eec\u521a\u521a\u63d0\u5230\u7684LRU\u7f13\u5b58\u5de5\u4f5c\u539f\u7406 \u53ef\u4ee5\u7528\u53cc\u5411\u94fe\u8868\u6765\u6a21\u62df\u8fd9\u4e00\u645e\u4e66<\/strong> \u53c8\u56e0\u4e3a\u6211\u4eec\u9700\u8981\u6839\u636ekey\u6765\u627e\u5230\u5bf9\u5e94\u7684\u8282\u70b9\u8fdb\u884c\u64cd\u4f5c \u5f88\u5bb9\u6613\u60f3\u5230\u4f7f\u7528\u54c8\u5e0c\u8868\u6765\u5b9e\u73b0\u5feb\u901f\u5b9a\u4f4d<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u8fd9\u91cc\u63d0\u5230\u7684\u54e8\u5175\u5f88\u91cd\u8981 \u6839\u636e\u56fe\u7247\u6240\u793a \u6211\u4eec\u628a\u54e8\u5175\u7684\u540e\u7ee7\u8282\u70b9 \u8bb0\u4e3a\u9996\u8282\u70b9 \u54e8\u5175\u7684\u524d\u9a71\u8282\u70b9\u8bb0\u4e3a\u5c3e\u90e8\u8282\u70b9 \u5c31\u5f62\u6210\u4e86\u4e00\u4e2a\u5b8c\u6574\u7684\u590d\u5408\u6761\u4ef6\u6570\u636e\u7ed3\u6784<\/p>\n\n\n\n

\u5206\u6790\u5230\u6b64\u7ed3\u675f \u63a5\u4e0b\u6765\u5c31\u662f\u5b9e\u73b0\u4e86 \u6211\u4eec\u9700\u8981\u6709\u53cc\u5411\u94fe\u8868\u7684\u6dfb\u52a0,\u5220\u9664,\u548c\u67e5\u627e\u65b9\u6cd5 \u67e5\u627e\u5f88\u7b80\u5355 \u5c31\u4e0d\u8bf4\u660e\u4e86 \u4e0b\u9762\u662f\u5220\u9664\u8282\u70b9<\/strong>\u548c\u589e\u52a0\u8282\u70b9\u5230\u94fe\u8868\u5934<\/strong>\u7684\u64cd\u4f5c\u8bf4\u660e<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u63a5\u4e0b\u6765\u662f\u4ee3\u7801\u7684\u9010\u6b65\u5206\u6790<\/p>\n\n\n\n

1.\u6784\u9020\u8282\u70b9(\u4e66)<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

2.\u8bbe\u7f6e\u5bb9\u91cf,\u54e8\u5175\u8282\u70b9,hashMap<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

3.\u5220\u9664\u548c\u589e\u6dfb\u8282\u70b9\u5230\u94fe\u8868\u5934<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

4.\u83b7\u53d6key\u5bf9\u5e94\u7684\u8282\u70b9 \u540c\u65f6\u628a\u8be5\u8282\u70b9\u79fb\u52a8\u5230\u94fe\u8868\u5934\u90e8<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

5.\u6784\u9020\u51fd\u6570 \u521d\u59cb\u5316capacity \u521b\u5efa\u865a\u62df\u5934\u7ed3\u70b9dummy \u521d\u59cb\u5316\u94fe\u8868\u6307\u9488<\/strong><\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

6.\u5b9e\u73b0get\u51fd\u6570<\/strong><\/p>\n\n\n\n

\u627e\u5230\u8fd4\u56de\u5bf9\u5e94\u503c \u672a\u627e\u5230\u8fd4\u56de-1<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

7.\u5b9e\u73b0put\u51fd\u6570<\/strong><\/p>\n\n\n\n

\u5148\u770b\u5f53\u524d\u94fe\u8868\u4e2d\u6709\u6ca1\u6709\u8fd9\u4e2a\u8282\u70b9(\u6709\u6ca1\u6709\u8fd9\u672c\u4e66) \u5982\u679c\u6709 \u5c31\u5c06\u5bf9\u5e94\u503c\u66f4\u65b0 \u6ca1\u6709\u5c31\u521b\u5efa\u65b0\u8282\u70b9\u653e\u5728\u94fe\u8868\u5934(\u628a\u65b0\u4e66\u653e\u5728\u6700\u4e0a\u9762) \u5982\u679c\u8d85\u8fc7\u8282\u70b9\u6570\u91cf\u8d85\u8fc7capacity \u53bb\u6389\u672b\u5c3e\u8282\u70b9\u7684(key,value)(\u62ff\u6389\u6700\u5e95\u4e0b\u7684\u4e66)<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u5230\u8fd9\u91cc\u5c31\u5b9e\u73b0\u5b8c\u6210\u5566^_^!<\/p>\n\n\n\n

\u5b8c\u6574\u4ee3\u7801\u8d34\u5728\u8fd9\u91cc <\/p>\n\n\n\n

class Node {\npublic:\n    int key;\n    int value;\n    Node* prev;\n    Node* next;\n    Node(int k = 0, int v = 0) : key(k), value(v) {}\n};\n\nclass LRUCache {\nprivate:\n    int capacity;\n    Node* dummy; \/\/ \u54e8\u5175\u8282\u70b9\n    unordered_map<int, Node*> key_to_node;\n\n    \/\/ \u5220\u9664\u4e00\u4e2a\u8282\u70b9\uff08\u62bd\u51fa\u4e00\u672c\u4e66\uff09\n    void remove(Node* x) {\n        x->prev->next = x->next;\n        x->next->prev = x->prev;\n    }\n\n    \/\/ \u5728\u94fe\u8868\u5934\u6dfb\u52a0\u4e00\u4e2a\u8282\u70b9\uff08\u628a\u4e00\u672c\u4e66\u653e\u5728\u6700\u4e0a\u9762\uff09\n    void push_front(Node* x) {\n        x->prev = dummy;\n        x->next = dummy->next;\n        x->prev->next = x;\n        x->next->prev = x;\n    }\n    \n\n    \/\/ \u83b7\u53d6 key \u5bf9\u5e94\u7684\u8282\u70b9\uff0c\u540c\u65f6\u628a\u8be5\u8282\u70b9\u79fb\u5230\u94fe\u8868\u5934\u90e8\n    Node* get_node(int key) {\n        auto it = key_to_node.find(key);\n        if (it == key_to_node.end()) { \/\/ \u6ca1\u6709\u8fd9\u672c\u4e66\n            return nullptr;\n        }\n        Node* node = it->second; \/\/ \u6709\u8fd9\u672c\u4e66\n        remove(node); \/\/ \u628a\u8fd9\u672c\u4e66\u62bd\u51fa\u6765\n        push_front(node); \/\/ \u653e\u5728\u6700\u4e0a\u9762\n        return node;\n    }\n\npublic:\n    LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {\n        dummy->prev = dummy;\n        dummy->next = dummy;\n    }\n\n    int get(int key) {\n        Node* node = get_node(key);\n        return node ? node->value : -1;\n    }\n\n    void put(int key, int value) {\n        Node* node = get_node(key);\n        if (node) { \/\/ \u6709\u8fd9\u672c\u4e66\n            node->value = value; \/\/ \u66f4\u65b0 value\n            return;\n        }\n        key_to_node[key] = node = new Node(key, value); \/\/ \u65b0\u4e66\n        push_front(node); \/\/ \u653e\u5728\u6700\u4e0a\u9762\n        if (key_to_node.size() > capacity) { \/\/ \u4e66\u592a\u591a\u4e86\n            Node* back_node = dummy->prev;\n            key_to_node.erase(back_node->key);\n            remove(back_node); \/\/ \u53bb\u6389\u6700\u540e\u4e00\u672c\u4e66\n            delete back_node; \/\/ \u91ca\u653e\u5185\u5b58\n        }\n    }\n};\n<\/code><\/pre>\n\n\n\n
\u8fd9\u4e00\u9898\u641e\u4e0b\u6765\u771f\u4e0d\u7b80\u5355\u5440 \u4f46\u662f\u518d\u56f0\u96be\u7684\u95ee\u9898\u6211\u4eec\u90fd\u8981\u514b\u670d \u6211\u4eec\u8981\u4e3a\u66f4\u597d\u7684\u672a\u6765\u594b\u6597<\/p>\n\n\n\n
\u7559\u4e00\u53e5\u52b1\u5fd7\u7684\u8bd7\u53e5\u5427 \u671b\u4f60\u6211\u5171\u52c9<\/p>\n\n\n\n
\u5343\u6dd8\u4e07\u6f09\u867d\u8f9b\u82e6,\u5439\u5c3d\u72c2\u6c99\u59cb\u5230\u91d1<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8fd9\u662f\u4e00\u9053\u9762\u8bd5\u4e2d\u5e38\u8003\u7684\u7b97\u6cd5\u9898 \u8003\u5bdf\u9891\u5ea6\u975e\u5e38\u9ad8 \u6240\u4ee5\u5fc5\u987b\u8981\u4e86\u89e3 \u4f46\u662f\u6211\u4eec\u4e5f\u4e0d\u8981\u90a3\u4e48\u529f\u5229 \u65e2\u7136\u8fd9\u4e2a\u9898\u8003\u5bdf\u9891\u7387\u5982\u6b64\u4e4b\u9ad8 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,7],"tags":[],"class_list":["post-568","post","type-post","status-publish","format-standard","hentry","category-4","category-7"],"_links":{"self":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/568","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=568"}],"version-history":[{"count":2,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/568\/revisions"}],"predecessor-version":[{"id":602,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/568\/revisions\/602"}],"wp:attachment":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=568"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=568"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=568"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}