data-structures - Erlang有序和键值数据结构

Question

我想实现一个实时分数排名( 下令 )。我希望我能快速得到每个玩家的分数( key-value )。

这里 player_id 是 key， score 是 value。

我尝试使用有序集合类型 ETS 来存储所有玩家得分的列表，但是键之后的有序集合顺序不是值。

Erlang/OTP 是否有其他数据结构可以解决我的问题？

Answer 1

我的理解是，您需要维护要执行的对 (Key,Score) 列表:

分数更新频繁，

经常显示按分数排序的列表的完整或部分 View

我建议您将数据存储到 2 个不同的 ets 中:

第一个用于快速访问 key 的集合是将 key 存储在第一个字段中，将分数存储在第二个字段中。

第二个是一个有序集，您将元组 {Score,Key} 作为键存储，没有值。这应该保证每个记录的唯一性，并维护按分数排序的列表。

当需要显示分数时，有序集就足够了。

当您需要更新分数时，您应该使用 ets 获取 Key 先前分数的值，删除记录 {PrevScore,Key} 并在有序集中插入 {NewScore,Key} 并简单地用新的更新第一个 ets值(value)。

我在 1 000 000 个项目列表上测试了这个解决方案，在我的笔记本电脑上更新 1 个分数平均需要 3 微秒(Windows XP、核心 i5、2Go ram，所有磁盘已满，许多应用程序在后台运行)。我使用的代码:

注意 为了保证2个表的一致性，我使用私有(private)表和单台服务器访问它们，因此并发进程可以访问服务器(命名分数)而不冲突，请求将按照到达服务器的顺序执行.可以优先回答具有 2 个接收 block 的任何 get(N) 请求。

这是我家用 PC 上的测试结果(ubuntu 12.04, 8gb ddr, AMD phenom II X6)...

[编辑] 我修改了 update/2 函数以实现同步，因此该度量现在很重要，并且结果更易于理解。似乎对于小于 10000 条记录的表，ets 管理和消息传递的开销是主要的。

-module (score).

-export ([start/0]).
-export ([update/2,delete/1,get/1,stop/0]).

score ! {update,M,S,self()},
    receive
        ok -> ok
    end.

delete(M) ->
    score ! {delete,M}.

get(N) ->
    score ! {getbest,N,self()},
    receive
        {ok,L} -> L
    after 5000 ->
        timeout
    end.

stop() ->
    score ! stop.


start() ->
    P = spawn(fun() -> initscore() end),
    register(score,P).


initscore() ->
    ets:new(score,[ordered_set,private,named_table]),
    ets:new(member,[set,private,named_table]),
    loop().

loop() ->
    receive
        {getbest,N,Pid} when is_integer(N), N > 0 ->
            Pid ! {ok,lists:reverse(getbest(N))},
            loop();
            {update,M,S,P} ->
                    update_member(M,S),
                    P ! ok,
            loop();
        {delete,M} ->
            delete_member(M),
            loop();
        stop ->
            ok
    end.



update_member(M,S) ->
    case ets:lookup(member,M) of
        [] -> 
            ok;
        [{M,S1}] ->
            ets:delete(score,{S1,M})
    end,
    ets:insert(score,{{S,M}}),
    ets:insert(member,{M,S}).

delete_member(M) ->
    case ets:lookup(member,M) of
        [] -> 
            ok;
        [{M,S}] ->
            ets:delete(score,{S,M}),
            ets:delete(member,M)
    end.

getbest(N) ->
    K= ets:last(score),
    getbest(N-1,K,[]).

getbest(_N,'$end_of_table',L) -> L;
getbest(0,{S,M},L) -> [{M,S}|L];
getbest(N,K={S,M},L) ->
    K1 = ets:prev(score,K),
    getbest(N-1,K1,[{M,S}|L]).

和测试代码:

-module (test_score).

-compile([export_all]).

init(N) ->
    score:start(),
    random:seed(erlang:now()),
    init(N,10*N).

stop() ->
    score:stop().

init(0,_) -> ok;
init(N,M) ->
    score:update(N,random:uniform(M)),
    init(N-1,M).

test_update(N,M) ->
    test_update(N,M,0).

test_update(0,_,T) -> T;
test_update(N,M,T) -> test_update(N-1,M,T+update(random:uniform(M),random:uniform(10*M))).

update(K,V) ->
    {R,_} = timer:tc(score,update,[K,V]),
    R.