Erlang ordsets
[Erlang 0069] Erlang ordsets
ordsets 是lists实现的有序集合.由于数据元素的变动都会触发重新排序,所以ordsets效率不高,只适用于数据量比较小的场景.ordsets中包含了常见的集合操作:求交集,并集,是否为子集,是否存在交集
6 > ordsets: intersection([ 1 , 2 , 3 , 4 ],[ 3 , 4 , 5 , 6 ]). [ 3 , 4 ] 7 > ordsets: union([ 1 , 2 , 3 , 4 ],[ 3 , 4 , 5 , 6 ]). [ 1 , 2 , 3 , 4 , 5 , 6 ] 8 > ordsets: is_disjoint([ 1 , 2 , 3 , 4 ],[ 3 , 4 , 5 , 6 ]). false 9 > ordsets: is_disjoint([ 1 , 2 , 3 , 4 ],[ 31 , 41 , 5 , 6 ]). true 10 > ordsets: is_subset([ 1 , 2 , 3 , 4 ],[ 31 , 41 , 5 , 6 ]). false 11 > ordsets: is_subset([ 1 , 2 , 3 , 4 ],[ 1 , 3 ]). false 12 > ordsets: is_subset([ 1 , 2 , 3 , 4 ],[ 1 , 2 , 3 , 4 , 5 , 31 ]). true
这些方法的实现大同小异,都会遍历两个集合(实际上就是处理两个lists):
union([E1|Es1], [E2|_]=Set2) when E1 < E2 ->
[E1|union(Es1, Set2)] ;
union([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
[E2|union(Es2, Set1)] ; % switch arguments!
union([E1|Es1], [_E2|Es2]) -> %E1 == E2
[E1|union(Es1, Es2)] ;
union([], Es2) -> Es2 ;
union(Es1, []) -> Es1.
看一下ordsets数据元素时的处理逻辑:
add_element(E, [H|Es]) when E > H -> [H|add_element(E, Es)] ; add_element(E, [H|_]=Set) when E < H -> [E|Set] ; add_element(_E, [_H|_]=Set) -> Set ; %E == H add_element(E, []) -> [E]. del_element(E, [H|Es]) when E > H -> [H|del_element(E, Es)] ; del_element(E, [H|_]=Set) when E < H -> Set ; del_element(_E, [_H|Es]) -> Es ; %E == H del_element(_, []) -> [].
其它的方法实现多是简单封装了lists的方法而已比如:from_list实际上就是执行list:usort,is_set判断是List且已经排序;
is_subset([E1|_], [E2|_]) when E1 < E2 -> %E1 not in Set2
false ;
is_subset([E1|_]=Set1, [E2|Es2]) when E1 > E2 ->
is_subset(Set1, Es2) ;
is_subset([_E1|Es1], [_E2|Es2]) -> %E1 == E2
is_subset(Es1, Es2) ;
is_subset([], _) -> true ;
is_subset(_, []) -> false.
%% 下面两个方法仅仅是对lists方法的简单封装
fold(F, Acc, Set) ->
lists: foldl(F, Acc, Set).
filter(F, Set) ->
lists: filter(F, Set).
lists:usort的处理过程包含了数据排重:
1 > lists: usort([ 2 , 1 , 3 , 4 , 2 , 3 , 8 , 9 ,a,v,c]).
[ 1 , 2 , 3 , 4 , 8 , 9 ,a,c,v]
2 > lists: usort([ 2 , 1 , 3 , 4 , 2 , 3 , 8 , 9 ,[a,c,q,m,x],a,v,c]).
[ 1 , 2 , 3 , 4 , 8 , 9 ,a,c,v,[a,c,q,m,x]]
3 > lists: usort([ 2 , 1 , 3 , 4 , 2 , 3 , 8 , 9 ,[ 0 ,c,q,m,x],a,v,c]).
[ 1 , 2 , 3 , 4 , 8 , 9 ,a,c,v,[ 0 ,c,q,m,x]]
4 > lists: usort([ 2 , 1 , 3 ,{zen}, 4 , 2 , 3 , 8 , 9 ,[ 0 ,c,q,m,x],a,v,c]).
[ 1 , 2 , 3 , 4 , 8 , 9 ,a,c,v,{zen},[ 0 ,c,q,m,x]]
性能相关
OTP文档中有一点和ordsets相关的内容 lists:substract(A,B),该操作的复杂度和leng(A)*length(B)成正比,当参与运算的两个都是长列表的时候就会非常慢了;使用ordsets会好很多:
> lists: subtract( " 123212 " , " 212 " ). %% lists: subtract(A, B) is equivalent to A -- B. " 312 " .
不要这样做:
HugeList1 -- HugeList2
替代方案:
HugeSet1 = ordsets: from_list(HugeList1),
HugeSet2 = ordsets: from_list(HugeList2),
ordsets: subtract(HugeSet1, HugeSet2)
显然lists中的元素原始顺序非常重要上面的方法就不适用了,要保持数据原始顺序,可以这样做:
Set = gb_sets: from_list(HugeList2),
[E || E <- HugeList1, not gb_sets: is_element(E, Set)]
两个细节:
1.如果lists中包含重复的元素时,两种运算不是等价的,HugeList2会移除所有在HugeList1中出现的元素
2.下面的方法比较lists中的元素使用的是相等== 而'--'操作使用的是匹配操作符'=:=';如果这个地方要求苛刻的话,可以使用sets替换为gb_sets,但要注意sets:from_list/1要比gb_sets:from_list/1慢得多.
注意:'--'操作符在处理单个元素时并无大碍:
HugeList1 -- [Element] %%OK
官方文档:
[1] lists http://www.erlang.org/doc/man/lists.html
[2] efficiency guide http://www.erlang.org/doc/efficiency_guide/commoncaveats.html
More Sharing Services Share | Share on facebook Share on myspace Share on google Share on twitter
分类: Erlang
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息