erlang中数据结构list的subtract性能分析

对于lists:substract（-- 操作）的性能，官方文档中解释说与两列表的乘积成正比，如果列表太长，用ordsets:substract更合适，网上也有一些文章提到，比如

http://blog.csdn.net/mycwq/article/details/32160581

这篇文章提到

那么，问题就来了，列表多长算太长，什么时候lists:substract，什么时候用改进方案，还是lists:subtract就直接废掉了呢。

对于以上的疑问做了以下测试。测试代码如下，对不同的列表长度进行用两种方法进行了实测。Len为列表长度，N为每个长度取样本次数，N越大误差超小，最后的时间为N次样本的总和。

-module(test).
-compile(export_all).

lists_subtract(N, Len) ->

    List1 = List2 = lists:seq(1, Len),
    Fun = fun() -> List1 -- List2 end,
    run(N, Len, Fun).


lists_gb_set_subtract(N, Len) ->
    List1 = List2 = lists:seq(1, Len),
    Fun = fun() ->
        Set = gb_sets:from_list(List2),
        [E || E <- List1, not gb_sets:is_element(E, Set)]
    end,
    run(N, Len, Fun).

run(N, Len, Fun) ->
    {T, _} = timer:tc(fun() -> loop(N, Fun) end),
    io:format("~w ~w~n",[Len,T]).

loop(N, Fun) when N > 0 ->
    Fun(),
    loop(N - 1, Fun);

loop(_, _) ->
    done.

测试分两阶段，

第一阶段，列表起始长度Len为100，按步长为10递增至1000。结果显示，

1. 当Len<550，lists:subtract优于gb_set，而且Len越小lists:subtract优势超明显。
2. 当550gb_set 反转优于lists:subtract ，但二者相差不大。
3. 当 650
4. 当 900

第二阶段，列表起始长度Len为100，按步长为100递增至5000。该阶段重点关注Len>1000的情况。结果显示，lists:subtract性能退化非常严重，gb_set的优势得以体现，以绝对优势取胜。

综上所述，开篇的疑问就都一一得出答案了。什么情况下使用使用哪一种方法，还是要看具体的需求：

1. 对于有大量的、频繁的小列表（建议长度一般在500以下 ）操作，建议使用lists:subtract更高效。
2. 对于有少量小列表操作，使用哪种都无所谓。
3. 对于长度在500至900区间的列表，使用哪种都可以，性能在伯仲之间。
4. 对于列表长度在900以上的长列表，建议使用gb_set优化方案。