orddict 是用List实现的有序Dictionary. orddict按照Key进行排序,
Key值不重复(对比一下proplists).每一次增加新数据项都会进行重新排序,所以通常情况查找会非常快.由于也是List和tuple实现,所以和proplists一样orddict也不适合大数据量的情况.注意orddict进行Key比较使用的是
相等(==).通过模块暴露出来的接口完成对orddict的处理,不要当作普通的list直接处理,因为一些操作会涉及到重排序.
LYSE上提到orddict在复杂性和效率上达到折中,元素最好不要超过
75个.
Orddicts are a generally good compromise between complexity and efficiency up to about 75 elements (see my benchmark). After that amount, you should switch to different key-value stores.
由于orddict实际上就是一个List的实现,相比proplists它的实现要简单很多.大多数方法都是下面逻辑的微调:
store(Key, New, [{K,_}=E|Dict]) when Key < K -> [{Key,New},E|Dict]; store(Key, New, [{K,_}=E|Dict]) when Key > K -> [E|store(Key, New, Dict)]; store(Key, New, [{_K,_Old}|Dict]) -> %Key == K [{Key,New}|Dict]; store(Key, New, []) -> [{Key,New}].
比如:
append(Key, New, [{K,_}=E|Dict]) when Key < K -> [{Key,[New]},E|Dict]; append(Key, New, [{K,_}=E|Dict]) when Key > K -> [E|append(Key, New, Dict)]; append(Key, New, [{_K,Old}|Dict]) -> %Key == K [{Key,Old ++ [New]}|Dict]; append(Key, New, []) -> [{Key,[New]}].
再比如:
append_list(Key, NewList, [{K,_}=E|Dict]) when Key < K -> [{Key,NewList},E|Dict]; append_list(Key, NewList, [{K,_}=E|Dict]) when Key > K -> [E|append_list(Key, NewList, Dict)]; append_list(Key, NewList, [{_K,Old}|Dict]) -> %Key == K [{Key,Old ++ NewList}|Dict]; append_list(Key, NewList, []) -> [{Key,NewList}].
Practice
Eshell V5.9.1 (abort with ^G) 1> D0 = orddict:new(). [] 2> D1 = orddict:store(files, [], D0), D2 = orddict:append(files, f1, D1), D3 = orddict:append(files, f2, D2), D4 = orddict:append(files, f3, D3), orddict:fetch(files, D4). [f1,f2,f3] 3> b(). D0 = [] D1 = [{files,[]}] D2 = [{files,[f1]}] D3 = [{files,[f1,f2]}] D4 = [{files,[f1,f2,f3]}] ok 4> D5 = orddict:append(dirs, dd, D4), D5. [{dirs,[dd]},{files,[f1,f2,f3]}] 5> D6 = orddict:append(a, abc, D5). [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]}] 6> D7 = orddict:append(z, abc, D6). [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc]}] 7> orddict:fetch_keys(D7). [a,dirs,files,z] 8> orddict:fetch(a,D7). [abc] 9> orddict:fetch(files,D7). [f1,f2,f3] 10> D7. [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc]}] 11> orddict:append(z, qqq, D7). [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc,qqq]}] 12> orddict:store(z, qqq, D7). [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,qqq}] 13> orddict:store 17> D7. [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc]}] 18> orddict:store(k,lala, D7). [{a,[abc]}, {dirs,[dd]}, {files,[f1,f2,f3]}, {k,lala}, {z,[abc]}] 20> orddict:append_list(k, [qqq], v(18)). ** exception error: bad argument in operator ++/2 called as lala ++ [qqq] in call from orddict:append_list/3 in call from orddict:append_list/3 21> orddict:append_list(k, qqq, v(18)). ** exception error: bad argument in operator ++/2 called as lala ++ qqq in call from orddict:append_list/3 in call from orddict:append_list/3 22> orddict:erase 22> D7. [{a,[abc]},{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc]}] 23> orddict:erase(a,D7). [{dirs,[dd]},{files,[f1,f2,f3]},{z,[abc]}] 24> orddict:filter filter(Pred, Orddict1) -> Orddict2 Pred = fun(Key, Value) -> bool() 28> orddict:filter(fun(K,N)->is_list(N) andalso length(N) >1 end ,D7). [{files,[f1,f2,f3]}] 29> orddict:fold fold(Fun, Acc0, Orddict) -> Acc1 Fun = fun(Key, Value, AccIn) -> AccOut 29> orddict:fold(fun(K,V,N)-> length(V)+N end ,0,D7). 6 30> orddict:from_list from_list(List) -> Orddict List = [{Key, Value}] 注意:重复数据项出现的时候,会采用最后出现的Value值 30> orddict:from_list([{a,1},{b,2},{c,3}]). [{a,1},{b,2},{c,3}] 31> orddict:from_list([{z,1},{b,2},{c,3}]). [{b,2},{c,3},{z,1}] 32> orddict:from_list([{"zen",1},{b,2},{c,3}]). [{b,2},{c,3},{"zen",1}] 33> orddict:from_list([{"zen",1},{b,2},{c,3},{1.0,p},{1,q}]). [{1,q},{b,2},{c,3},{"zen",1}] 34> orddict:is_key 34> orddict:is_key(z,D7). true 35> orddict:is_key(p,D7). false 36> orddict:map map(Fun, Orddict1) -> Orddict2 Fun = fun(Key, Value1) -> Value2 36> orddict:map(fun(K,V)->{K,{K,V,term_to_binary(V)}} end ,D7). [{a,{a,{a,[abc],<<131,108,0,0,0,1,100,0,3,97,98,99,106>>}}}, {dirs,{dirs,{dirs,[dd], <<131,108,0,0,0,1,100,0,2,100,100,106>>}}}, {files,{files,{files,[f1,f2,f3], <<131,108,0,0,0,3,100,0,2,102,49,100,0,2,102,50,100,0, 2,...>>}}}, {z,{z,{z,[abc],<<131,108,0,0,0,1,100,0,3,97,98,99,106>>}}}] 37> orddict:update 38> orddict:update(a,fun(V)-> term_to_binary(V) end,D7). [{a,<<131,108,0,0,0,1,100,0,3,97,98,99,106>>}, {dirs,[dd]}, {files,[f1,f2,f3]}, {z,[abc]}] 39> orddict:update(dvd,fun(V)-> term_to_binary(V) end,D7). ** exception error: no function clause matching orddict:update(dvd,#Fun<erl_eval.6.13229925>, [{files,[f1,f2,f3]},{z,[abc]}]) in function orddict:update/3 40> orddict:update(dvd,fun(V)-> term_to_binary(V) end,not_found,D7). [{a,[abc]}, {dirs,[dd]}, {dvd,not_found}, {files,[f1,f2,f3]}, {z,[abc]}] 41> orddict:update_counter update_counter(Key, Incr, D) -> update(Key, fun (Old) -> Old + Incr end, Incr, D). 47> orddict:update_counter(a,1,[{a,10},{b,13},{c,16}]). [{a,11},{b,13},{c,16}] 48>
晚安!
