Erlang ordered and key-value data struct

Question

I want to implement a real-time score ranking(ordered). I hope I can get every player's score fast(key-value).

Here player_id is key and score is value.

I try to use ordered-set type ETS to store the list of all the player's score, But ordered set orders after the key not the value.

Does Erlang/OTP have some other data struct that can solve my problem?

Answer 1

What I understand is that you need to maintain a list of pair (Key,Score) with which you want to perform:

• frequent update of the score,
• frequently display a complete or partial view of the list sorted by score

I propose you to store your data into 2 different ets:

• The first one for fast access to the key is a set where you store the Key in the first field, and the Score in the second field.
• The second is an ordered set where you store a tuple {Score,Key} as key, and no value. This should guarantee the uniqueness of each record a maintain the list ordered by score.

When you need to display scores, the ordered set is sufficient.

when you need to update a score you should use the ets to get the value of the previous score for Key, delete the record {PrevScore,Key} and insert {NewScore,Key} in the ordered set and simply update the first ets with new value.

I tested this solution on a 1 000 000 item list, the update of 1 score takes an average of 3µs on my laptop (windows XP, core i5, 2Go ram ,all disks full and many app running in background). the code I used :

note I used private tables and a single server to access them in order to guarantee the consistency of the 2 tables, so concurrent processes can access to the server (named score) without conflict, the requests will be executed in the order they arrive to the server. It could be possible to answer in priority to any get(N) request with 2 receive blocks.

here is the test result on my home PC (ubuntu 12.04, 8gb ddr, AMD phenom II X6)...

[edit] I modified the update/2 function in order to be synchronous, so the measure is now significant, and the result more understandable. It appears that for table smaller than 10000 records, the overhead of ets management and message passing is preponderant.

-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]).

and the code for test:

-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.