我想實現實時評分排名(訂購)。我希望我能快速得到每個球員的得分(鍵值)。Erlang訂購和鍵值數據結構
在這裏player_id是關鍵和得分是價值。
我嘗試使用有序集合類型的ETS來存儲所有玩家得分的列表,但是在鍵值之後的有序集合順序不是值。
是否Erlang/OTP有一些其他的數據結構可以解決我的問題?
我想實現實時評分排名(訂購)。我希望我能快速得到每個球員的得分(鍵值)。Erlang訂購和鍵值數據結構
在這裏player_id是關鍵和得分是價值。
我嘗試使用有序集合類型的ETS來存儲所有玩家得分的列表,但是在鍵值之後的有序集合順序不是值。
是否Erlang/OTP有一些其他的數據結構可以解決我的問題?
我不會挑剔erlang選擇訂購數據的方式:它優化自己或快速查找。但是,您可以執行的操作是在列表中讀取您的ETS表格,並使用lists:sort/2
對數據進行排序。
List = ets:tab2list(EtsTable),
lists:sort(SortFun,List).
它仍然很快:ETS表和列表駐留在內存中,只要你有足夠的空間。不過,我會傾有序集,你將失去持續訪問時間
該模塊內置於Erlang的接口長期儲存的BIF。 這些提供了在Erlang運行時系統中存儲大量數據的能力,並且具有對數據的持續訪問時間。 (在命令集的情況下,見下文,訪問時間正比於 存儲對象的數量的對數)。
不要忘記某種形式的基於磁盤的備份,dets或mnesia(如果數據值得保留)。
對不起。該值非常頻繁地變化,所以我希望當它改變時(O(n))插入/更新鍵值,並在需要時獲得值(O(logn))。但在你的情況下,我必須1)tab2list 2)排序3)list2tab(O(n * logn))。 – mingchaoyan
那麼,如果速度那麼重要,那麼爲什麼不去純粹的C呢?無論如何,Erlang並不是特別快。從來沒有打算。 http://stackoverflow.com/questions/6964392/speed-comparison-with-project-euler-c-vs-python-vs-erlang-vs-haskell – Berzemus
或者你可以使用你自己的二進制格式,並使用erlang的位語法有效管理它。儘管如此,仍然會比一些智能內存管理/黑客入侵更慢。 – Berzemus
我的理解是,你需要保持對與您要執行列表(鍵,分數):
排序我建議您將數據存儲到2個不同的ETS:
當您需要顯示分數時,有序集合就足夠了。
當您需要更新分數時,您應該使用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.
該措施是錯誤的,我從外部的角度來衡量時間,並且對於更新,它只是發送消息所需的時間,這就是爲什麼它如此穩定。我會盡量在以後再重新測量... – Pascal
有三種解決方案:
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)
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可以是另一種選擇。但個人而言,我認爲過度優化在這裏是不值得的,除非它真的是你的瓶頸。
(1)不適合相同的分數。它將被替換,因爲相同的密鑰。 – goofansu
@goofansu解決方法是使用'{score,player_id}'元組作爲關鍵字 –
查看oddict http://erldocs.com/R15B/stdlib/orddict.html。我沒有檢查它是否支持你需要的功能,但它看起來你可以創建一個包裝它來實現你的功能 – Arunmu
@ArunMu對不起,它似乎orddict「列表是按照鍵後排序」。我想要在值 – mingchaoyan
之後引用,我只是很想知道,爲什麼要按價值排序。它如何幫助獲取鍵值對? – Arunmu