[Erlang 0069] Erlang ordsets

更新时间：2022-08-22 08:28:11

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

[Erlang 0069] Erlang ordsets

上一篇 : ：派生类的例子下一篇 : PP代码生成器(四) 使用解决方案生成代码

[Erlang 0069] Erlang ordsets

性能相关

其它Set模块

相关阅读

推荐文章