Erlang有序和键值数据结构

Question

我想实现一个实时分数排名(订购).我希望我能快速得到每个球员的得分(键值).

这里player_id是关键,得分是值.

我尝试使用有序集类型ETS来存储所有玩家得分的列表,但是在键之后的有序集合命令不是值.

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

Answer 1

我的理解是你需要维护一个你想要执行的对(Key,Score)列表:

• 频繁更新分数,
• 经常显示按分数排序的列表的完整或部分视图

我建议您将数据存储到两个不同的位置:

• 用于快速访问密钥的第一个是将密钥存储在第一个字段中的集合,以及存储在第二个字段中的分数.
• 第二个是有序集,其中存储元组{Score,Key}作为键,没有值.这应该保证每个记录的唯一性,维护按分数排序的列表.

当您需要显示分数时,有序集就足够了.

当您需要更新分数时,您应该使用ets获取Key的先前分数的值,删除记录{PrevScore,Key}并在有序集中插入{NewScore,Key},然后使用new更新第一个ets值.

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

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

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

[edit]我修改了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.

Answer 2

我不会对 erlang 选择排序数据的方式挑剔：它会优化自身或快速查找。然而，您可以做的是读取列表中的 ETS 表，并使用 alists:sort/2对数据进行排序。

List  = ets:tab2list(EtsTable),
lists:sort(SortFun,List).

它仍然会很快：ETS 表和列表驻留在内存中，只要您有足够的内存。但是，我会转储ordered_set，您将失去恒定的访问时间

来自 ETS 手册：

该模块是 Erlang 内置术语存储 BIF 的接口。这些提供了在 Erlang 运行时系统中存储大量数据的能力，并且具有恒定的数据访问时间。（在ordered_set的情况下，见下文，访问时间与存储的对象数量的对数成正比）。

并且不要忘记某种形式的基于磁盘的备份、dets 或 mnesia（如果数据值得保留）。