LRU缓存机制设计与实现(Python、C++、Erlang)

2019-11-23 09:30 分类：Erlang 作者：云诺阅读(2133)

LRU 缓存机制设计和实现一个 LRU（最近最少使用）缓存数据结构，使它应该支持一下操作：get 和 put。 get(key) - 如果 key 存在于缓存中，则获取 key 的 value（总是正数），否则返回 -1。 put(key,value) - 如果 key 不存在，请设置或插入 value。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

python版本：

class LRUCache(object):
    def __init__(self, capacity):
    """
    :type capacity: int
    """
    self.cache = {}
    self.keys = []
    self.capacity = capacity
    
    def visit_key(self, key):
        if key in self.keys:
            self.keys.remove(key)
        self.keys.append(key)
    
    def elim_key(self):
        key = self.keys[0]
        self.keys = self.keys[1:]
        del self.cache[key]
        
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if not key in self.cache:
            return -1
        self.visit_key(key)
        return self.cache[key]
    
    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if not key in self.cache:
        if len(self.keys) == self.capacity:
        self.elim_key()
        self.cache[key] = value
        self.visit_key(key)

def main():
    s =
    [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[
    4,4],[1],[3],[4]]]
    obj = LRUCache(2)
    l=[]
    for i,c in enumerate(s[0]):
        if(c == "get"):
            l.append(obj.get(s[1][i][0]))
        else:
            obj.put(s[1][i][0], s[1][i][1])
    print(l)

if __name__ == "__main__":
    main()

C++版本：

class LRUCache{
    public:
        LRUCache(int capacity) {
            cap = capacity;
        }
        
        int get(int key) {
            auto it = m.find(key);
            if (it == m.end()) return -1;
            l.splice(l.begin(), l, it->second);
            return it->second->second;
        }
        
        void set(int key, int value) {
            auto it = m.find(key);
            if (it != m.end()) l.erase(it->second);
            l.push_front(make_pair(key, value));
            m[key] = l.begin();
            if (m.size() > cap) {
                int k = l.rbegin()->first;
                l.pop_back();
                m.erase(k);
            }
        }
}

Erlang版本：

%%----------------------------------------------------
%% LRU缓存
%%----------------------------------------------------
-module(lru_cache).
-behaviour(gen_server).
-export([start_link/1]).
-export([init/1, handle_call/3, handle_cast/2, handle_info/2, terminate/2, code_change/3]).
-export([
        insert/2
        ,delete/2
        ,lookup/2
        ,info/0
        ,resize/2
        ,clean/1
        ,member/2
    ]
).
-record(cache_cfg, {
        %% 缓存名称
        name            :: atom()
        %% 最大数量，=0表示不限制数量
        ,max_size = 0   :: non_neg_integer()
        %% 缓存对象的主键位置
        ,keypos         :: pos_integer()
    }
).

-record(state, {
        cache_names = []        :: [atom()]
    }
).

-define(CHECK_LRU_CACHE_INTERVLAL, (30*1000)).  %% 检查LRU缓存的间隔时间（毫秒）
-ifdef(debug).
-define(ROLE_CACHE_MAX_NUM, 1).
-else.
-define(ROLE_CACHE_MAX_NUM, 1000).
-endif.


%% ----------------------------------------------------
%% 外部接口
%% ----------------------------------------------------
%% @doc 启动
start_link() ->
    gen_server:start_link({local, ?MODULE}, ?MODULE, [], []).

%% @doc 写入缓存
insert(CacheName, Value) ->
    NewTs = ts(),
    Key = get_key(CacheName, Value),
    ets:insert(CacheName, {Key, Value, NewTs}),
    ok.


%% @doc 删除缓存
delete(CacheName, Key) ->
    ets:delete(CacheName, Key),
    ok.

%% @doc 读取缓存
%% （lookup不影响ts）
-spec lookup(CacheName :: atom(), Key :: term()) -> {ok, term()} | false.
lookup(CacheName, Key) ->
    case ets:lookup(CacheName, Key) of
        [{Key, Value, _Ts}] -> {ok, Value};
        [] -> false
    end.

%% @doc 判断缓存中是否存在
-spec member(CacheName :: atom(), Key :: term()) -> boolean().
member(CacheName, Key) ->
    case ets:member(CacheName, Key) of
        true -> true;
        false -> false
    end.

%% @doc 更新缓存最大记录数
resize(CacheName, MaxSize) ->
    gen_server:cast(?MODULE, {resize, CacheName, MaxSize}).

%% @doc 清除缓存和ts
clean(CacheName) ->
    ets:delete_all_objects(CacheName),
    ok.

%% @doc 显示目前缓存信息
info() ->
    gen_server:cast(?MODULE, info).


%% ----------------------------------------------------
%% 内部处理
%% ----------------------------------------------------
init([]) ->
    ?INFO("[~w] 正在启动...", [?MODULE]),
    process_flag(trap_exit, true),
    {ok, State} = do_init(),
    erlang:send_after(?CHECK_LRU_CACHE_INTERVLAL, self(), check),
    ?INFO("[~w] 启动完成", [?MODULE]),
    {ok, State}.

handle_call(_Request, _From, State) ->
    {noreply, State}.

handle_cast({resize, CacheName, MaxSize}, State) ->
    case get({cfg, CacheName}) of
        Cfg = #cache_cfg{max_size = OldSize} ->
            put({cfg, CacheName}, Cfg#cache_cfg{max_size = MaxSize}),
            ?INFO("LRU缓存[~w]的MaxSize变化: ~w => ~w", [CacheName, OldSize, MaxSize]);
        _ ->
            ?ERR("找不到[~w]的LRU缓存配置", [CacheName])
    end,
    {noreply, State};

handle_cast(info, State = #state{cache_names = L}) ->
    ?INFO("LRU缓存信息:"),
    lists:foreach(fun(CacheName) ->
                #cache_cfg{keypos = KeyPos, max_size = MaxSize} = get({cfg, CacheName}),
                ?INFO("[~w] Ets Size=~w, keypos=~w, MaxSize=~w", [CacheName, ets:info(CacheName, size), KeyPos, MaxSize])
        end, L),
    {noreply, State};

handle_cast(_Msg, State) ->
    {noreply, State}.

handle_info(check, State = #state{cache_names = L}) ->
    lists:foreach(fun(CacheName) ->
                do_check(CacheName)
        end, L),
    erlang:send_after(?CHECK_LRU_CACHE_INTERVLAL, self(), check),
    {noreply, State};

handle_info(_Info, State) ->
    {noreply, State}.

terminate(_Reason, _State) ->
    ?INFO("[~w] 正在关闭...", [?MODULE]),
    ?INFO("[~w] 关闭完成", [?MODULE]),
    ok.

code_change(_OldVsn, State, _Extra) ->
    {ok, State}.

%% ----------------------------------------------------
%% 私有函数
%% ----------------------------------------------------
do_init() ->
    put(cache_names, []),
    %% 角色缓存（离线）
    create(role_cache, [public, named_table, set, compressed, {keypos, get_keypos(role_cache)}, {write_concurrency, true}], ?ROLE_CACHE_MAX_NUM),
    {ok, #state{cache_names = erase(cache_names)}};
do_init() ->
    {ok, #state{}}.

get_keypos(role_cache) -> #role.id;
get_keypos(account_id_index) -> 1.

get_key(CacheName, Value) ->
    KeyPos = get_keypos(CacheName),
    erlang:element(KeyPos, Value).

%% 创建缓存
%% ets表的结构统一为：{Key, Object, Ts}
create(CacheName, CacheOpts, MaxSize) ->
    {ok, NewOpts, KeyPos} = deal_opts(CacheOpts, []),
    ets:new(CacheName, NewOpts),
    Cfg = #cache_cfg{name = CacheName, max_size = MaxSize, keypos = KeyPos},
    put({cfg, CacheName}, Cfg),
    put(cache_names, [CacheName | get(cache_names)]),
    ok.

deal_opts([], _) -> false;
deal_opts([{keypos, Pos} | T], Result) -> {ok, lists:concat([Result, T, [{keypos, 1}]]), Pos};
deal_opts([H | T], Result) ->
    deal_opts(T, [H|Result]).

%% 检查缓存大小是否需要调整
%% 检查缓存大小是否需要调整
do_check(CacheName) ->
    %% ?DEBUG("正在检查LRU缓存:~w", [CacheName]),
    #cache_cfg{max_size = MaxSize} = get({cfg, CacheName}),
    Keys = util:get_all_ets_key(CacheName),
    Len = length(Keys),
    case Len > MaxSize of
        true ->
            L = lists:foldl(fun(Key, Result) ->
                        case catch ets:lookup_element(CacheName, Key, 3) of
                            OldTs = {_, _, _} ->
                                [{OldTs, Key} | Result];
                            _ ->
                                Result
                        end
                end, [], Keys),
            L1 = lists:keysort(1, L),
            {L2, _L3} = lists:split(Len-MaxSize, L1),
            lists:foreach(fun({_Ts, Key}) ->
                        ets:delete(CacheName, Key)
                end, L2),
            ?DEBUG("清理缓存[~w], ~w => ~w", [CacheName, Len, ets:info(CacheName, size)]);
        false ->
            ignore
    end,
    ok.

%% 生成操作时间戳
ts() -> os:timestamp().

祝生活愉快！

「创作不易，你的支持是本站持续更新最大的动力！」

赞(0) 打赏