Chinaunix首页 | 论坛 | 博客
  • 博客访问: 131203
  • 博文数量: 12
  • 博客积分: 102
  • 博客等级: 入伍新兵
  • 技术积分: 150
  • 用 户 组: 普通用户
  • 注册时间: 2008-04-25 09:03
个人简介

80后程序员

文章分类

全部博文(12)

文章存档

2020年(1)

2018年(3)

2013年(5)

2011年(1)

2010年(2)

我的朋友

分类: Erlang

2018-01-03 17:39:02

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

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

这篇文章提到


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

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

点击(此处)折叠或打开

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

  3. lists_subtract(N, Len) ->
  4.     List1 = List2 = lists:seq(1, Len),
  5.     Fun = fun() -> List1 -- List2 end,
  6.     run(N, Len, Fun).

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

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

  17. loop(N, Fun) when N > 0 ->
  18.     Fun(),
  19.     loop(N - 1, Fun);
  20. loop(_, _) ->
  21.     done.



测试分两阶段,

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

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



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


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


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



阅读(40135) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~