Erlang訂購和鍵值數據結構

Question

我想實現實時評分排名（訂購）。我希望我能快速得到每個球員的得分（鍵值）。

在這裏player_id是關鍵和得分是價值。

我嘗試使用有序集合類型的ETS來存儲所有玩家得分的列表，但是在鍵值之後的有序集合順序不是值。

是否Erlang/OTP有一些其他的數據結構可以解決我的問題？

Answer 1

我不會挑剔erlang選擇訂購數據的方式：它優化自己或快速查找。但是，您可以執行的操作是在列表中讀取您的ETS表格，並使用lists:sort/2對數據進行排序。

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

它仍然很快：ETS表和列表駐留在內存中，只要你有足夠的空間。不過，我會傾有序集，你將失去持續訪問時間

From the ETS manual：

該模塊內置於Erlang的接口長期儲存的BIF。 這些提供了在Erlang運行時系統中存儲大量數據的能力，並且具有對數據的持續訪問時間。 （在命令集的情況下，見下文，訪問時間正比於 存儲對象的數量的對數）。

不要忘記某種形式的基於磁盤的備份，dets或mnesia（如果數據值得保留）。

Answer 2

我的理解是，你需要保持對與您要執行列表（鍵，分數）：

• 比分的頻繁更新，
• 經常顯示的全部或部分查看列表中按分數

排序我建議您將數據存儲到2個不同的ETS：

• 快速訪問密鑰的第一個功能是將密鑰存儲在第一個字段中的集合以及第二個字段中的Score。
• 第二個是有序集，您在其中存儲元組{Score，Key}作爲鍵，並且沒有值。這應該保證每個記錄的唯一性維護按分數排序的列表。

當您需要顯示分數時，有序集合就足夠了。

當您需要更新分數時，您應該使用ets獲取Key以前得分的值，刪除記錄{PrevScore，Key}並在有序集合中插入{NewScore，Key}，並簡單地更新首先會帶來新的價值。我在我的筆記本電腦上（windows XP，core i5，2Go ram，所有磁盤已滿並且許多應用程序在後臺運行）上的平均值爲3μs，我在1 000 000個項目列表上測試了此解決方案。我使用的代碼：

注我使用的專用桌子和一臺服務器來訪問它們，以保證2代表的一致性，所以併發進程可以在不衝突的接入服務器（稱爲分數）時，請求將按照到達服務器的順序執行。有可能優先回答具有2個接收塊的任何獲得（N）請求。

這裏是我家電腦上的測試結果（Ubuntu的12.04，8GB DDR，AMD羿龍II X6）...

[編輯]我修改了更新/ 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 3

有三種解決方案：

• ETS有序集

• 只在RAM上的Mnesia表與二次索引

• NIF

1）有序集，在ETS表中的記錄應該是{分數，player_id}，{不player_id，比分}，讓他們通過得分排序。要獲得一名球員的分數，只需使用匹配。儘管比賽需要掃描整個桌子，但仍然非常快。分析：假設有10k玩家，將10k記錄插入ets表，然後ets：match_object（Table，{'_'，PlayerID}）。每場比賽需要0.7到1.1毫秒，這在大多數情況下都足夠好。 （CPU：i5 750）

1. match_object比匹配稍快;
2. 選擇一個匹配規格比匹配慢，可能是因爲這裏的選擇非常簡單，fun2ms的開銷超過了它的收益。請注意，select通常優於match。

2）的Mnesia表，使其只在RAM，並使用一個二級指數player_id：

mnesia:create_table(user, [{type, ordered_set}, {attributes, record_info(fields, user)}, {index, [playerid]}]) 

平均得到的時間使用Mnesia的：在Mnesia中閱讀：交易是0.09ms。但是，插入10k條記錄比它的對應記錄（2820ms vs 15ms）慢大約180倍。

如果ets和mnesia都不能滿足您的性能要求，那麼使用nif可以是另一種選擇。但個人而言，我認爲過度優化在這裏是不值得的，除非它真的是你的瓶頸。