Home > study > 一个简单的列表操作性能测试

一个简单的列表操作性能测试

May 24th, 2007 :: Arbow
Goto comments Leave a comment

Note:首先要了解，Erlang里面的列表，比如 [1,2,3,4]，其实是这样的方式来存储 [1,[2,[3,[4]]]]，因此在头部插入一个元素，很简单，但是在尾部插入就比较困难了。

闲来对Erlang中的2个列表操作进行了测试，先上代码：

  1. -module(test_list).
  2. -compile(export_all).
  3.  
  4. main() ->
  5. test_concat(),
  6. test_flatten(),
  7. test_append_tail(),
  8. test_append_header().
  9.  
  10. test_concat() ->
  11. statistics(wall_clock),
  12. test_concat(1000000).
  13.  
  14. test_concat(0) ->
  15. {_, Duration} = statistics(wall_clock),
  16. io:format("Concat Duration ~pms~n", [Duration]),
  17. ok;
  18. test_concat(N) ->
  19. "<title>" ++ integer_to_list(N) ++ "</title>",
  20. test_concat(N-1).
  21.  
  22. test_flatten() ->
  23. statistics(wall_clock),
  24. test_flatten(1000000).
  25.  
  26. test_flatten(0) ->
  27. {_, Duration} = statistics(wall_clock),
  28. io:format("Flatten Duration ~pms~n", [Duration]),
  29. ok;
  30. test_flatten(N) ->
  31. lists:flatten(["<title>",integer_to_list(N),"</title>"]),
  32. test_flatten(N-1).
  33.  
  34. test_append_tail() ->
  35. statistics(wall_clock),
  36. test_append_tail(100000).
  37.  
  38. test_append_tail(0) ->
  39. {_, Duration} = statistics(wall_clock),
  40. io:format("Append tail Duration ~pms~n", [Duration]),
  41. ok;
  42. test_append_tail(N) ->
  43. append_last([], 97, 122),
  44. test_append_tail(N-1).
  45.  
  46. append_last(List, N, N) ->
  47. List ++ [N];
  48. append_last(List, Curr, N) ->
  49. append_last(List ++ [Curr], Curr+1, N).
  50.  
  51.  
  52. test_append_header() ->
  53. statistics(wall_clock),
  54. test_append_header(100000).
  55.  
  56. test_append_header(0) ->
  57. {_, Duration} = statistics(wall_clock),
  58. io:format("Append header Duration ~pms~n", [Duration]),
  59. ok;
  60. test_append_header(N) ->
  61. append_header_and_reverse([], 97, 122),
  62. test_append_header(N-1).
  63.  
  64. append_header_and_reverse(List, N, N) ->
  65. lists:reverse([N|List]);
  66. append_header_and_reverse(List, Curr, N) ->
  67. append_header_and_reverse([Curr|List], Curr+1, N).

test_concat() 和 test_flatten()，测试使用 ++ 构造一个 list，和使用 lists:flatten() 构造list的开销；test_append_tail() 和 test_append_header()， 测试使用 ++ 和 [H|T]再lists:reverse() 方式将大量字符构造成一个列表的开销。

  1. 1> c(test_list).
  2. {ok,test_list}
  3. 2> test_list:main().
  4. Concat Duration 1637ms
  5. Flatten Duration 6743ms
  6. Append tail Duration 2144ms
  7. Append header Duration 624ms
  8. ok
  9. 3> c(test_list, [native]).
  10. {ok,test_list}
  11. 4> test_list:main().
  12. Concat Duration 863ms
  13. Flatten Duration 6084ms
  14. Append tail Duration 1974ms
  15. Append header Duration 362ms
  16. ok

可见，使用 ++ 合并列表，比使用 lists:flatten() 高效；而使用[H|T]再lists:reverse()的方式比 ++ 高效。使用HIPE编译后，++操作和[H|T]操作的性能也得到了较大的提高。

经常在Erlang的程序代码里面看到类似

  1. foo([], List) ->
  2. lists:reverse(List);
  3. foo([H|T], List) ->
  4. ...
  5. foo(T, [H|List])

这样的代码，里面就是使用了头部插入，然后反转列表的方式。

study

  1. jackyz
    May 25th, 2007 at 22:38 | #1
    Reply | Quote

    原来如此。难怪看到好多这样的代码。赞。

  2. piggybox
    July 11th, 2007 at 20:45 | #2
    Reply | Quote

    一般都是头插在反转，list内部好象不是循环链表啊。另外erlang既不支持mutable data也不支持monad，好象没法自己实现循环链表？

  3. Arbow
    July 11th, 2007 at 21:40 | #3
    Reply | Quote

    @piggybox
    记得以前看过一份代码，将list拷一份，放到一个递归函数里面

    fun([], List) -> fun(List, List);
    fun([H|T], List) -> ……….. fun(T, List).

    这种方式来实现循环列表的访问。。。

  4. piggybox
    July 12th, 2007 at 00:36 | #4
    Reply | Quote

    哈哈这样伪装成循环链表啊，彻底晕倒~~~看来还是没法构造真正的循环链表

  5. Caoyuan
    August 14th, 2007 at 11:10 | #5
    Reply | Quote

    append() 与 ++ 是等价的，或者说，++在编译时会转换成调用lists:append。
    如果实现知道一个list的深度是1，可以用append而不要用flatten。

    flatten需要遍历list的每一个元素，如果某个元素也是list，那么就要深入下去。

  6. dior
    May 27th, 2010 at 11:41 | #6
    Reply | Quote

    Hello, blogger, your article very good, looking forward to sharing your latest

  1. No trackbacks yet.