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
其它Set模块
sets 提供了和ordsets一样的接口;它的实现和
dict类似,只是存储的数据元素从键值对变成了值,
支持的数据量比ordsets更大一些;和
dict一样特别适用于
读密集的场景,比如判断一个元素是否在集合中.
gb_sets接口包含了ordsets和
gb_trees所提供的接口, gb_sets和
gb_trees实现类似,只是存储的数据元素从键值对变成了值;gb_sets与sets相比除了读操作性能差一些,其它操作都更快!gb_sets实现了sets和ordsets相同的接口,并新增了一些方法.
实际应用中你会看到绝大多数时候都是在使用gb_sets,需要"=:="比较的时候使用sets.
官方文档:
[1] lists
http://www.erlang.org/doc/man/lists.html
[2] efficiency guide
http://www.erlang.org/doc/efficiency_guide/commoncaveats.html
