一个简单的列表操作性能测试
Note:首先要了解，Erlang里面的列表，比如 [1,2,3,4]，其实是这样的方式来存储 [1,[2,[3,[4]]]]，因此在头部插入一个元素，很简单，但是在尾部插入就比较困难了。
闲来对Erlang中的2个列表操作进行了测试，先上代码：
- -module(test_list).
- -compile(export_all).
- main() ->
- test_concat(),
- test_flatten(),
- test_append_tail(),
- test_append_header().
- test_concat() ->
- statistics(wall_clock),
- test_concat(1000000).
- test_concat(0) ->
- {_, Duration} = statistics(wall_clock),
- io:format("Concat Duration ~pms~n", [Duration]),
- ok;
- test_concat(N) ->
- "<title>" ++ integer_to_list(N) ++ "</title>",
- test_concat(N-1).
- test_flatten() ->
- statistics(wall_clock),
- test_flatten(1000000).
- test_flatten(0) ->
- {_, Duration} = statistics(wall_clock),
- io:format("Flatten Duration ~pms~n", [Duration]),
- ok;
- test_flatten(N) ->
- lists:flatten(["<title>",integer_to_list(N),"</title>"]),
- test_flatten(N-1).
- test_append_tail() ->
- statistics(wall_clock),
- test_append_tail(100000).
- test_append_tail(0) ->
- {_, Duration} = statistics(wall_clock),
- io:format("Append tail Duration ~pms~n", [Duration]),
- ok;
- test_append_tail(N) ->
- append_last([], 97, 122),
- test_append_tail(N-1).
- append_last(List, N, N) ->
- List ++ [N];
- append_last(List, Curr, N) ->
- append_last(List ++ [Curr], Curr+1, N).
- test_append_header() ->
- statistics(wall_clock),
- test_append_header(100000).
- test_append_header(0) ->
- {_, Duration} = statistics(wall_clock),
- io:format("Append header Duration ~pms~n", [Duration]),
- ok;
- test_append_header(N) ->
- append_header_and_reverse([], 97, 122),
- test_append_header(N-1).
- append_header_and_reverse(List, N, N) ->
- lists:reverse([N|List]);
- append_header_and_reverse(List, Curr, N) ->
- 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> c(test_list).
- {ok,test_list}
- 2> test_list:main().
- Concat Duration 1637ms
- Flatten Duration 6743ms
- Append tail Duration 2144ms
- Append header Duration 624ms
- ok
- 3> c(test_list, [native]).
- {ok,test_list}
- 4> test_list:main().
- Concat Duration 863ms
- Flatten Duration 6084ms
- Append tail Duration 1974ms
- Append header Duration 362ms
- ok
可见，使用 ++ 合并列表，比使用 lists:flatten() 高效；而使用[H|T]再lists:reverse()的方式比 ++ 高效。使用HIPE编译后，++操作和[H|T]操作的性能也得到了较大的提高。
经常在Erlang的程序代码里面看到类似
- foo([], List) ->
- lists:reverse(List);
- foo([H|T], List) ->
- ...
- foo(T, [H|List])
这样的代码，里面就是使用了头部插入，然后反转列表的方式。
Comments
原来如此。难怪看到好多这样的代码。赞。
一般都是头插在反转，list内部好象不是循环链表啊。另外erlang既不支持mutable data也不支持monad，好象没法自己实现循环链表？
@piggybox
记得以前看过一份代码，将list拷一份，放到一个递归函数里面
fun([], List) -> fun(List, List);
fun([H|T], List) -> ……….. fun(T, List).
这种方式来实现循环列表的访问。。。
哈哈这样伪装成循环链表啊，彻底晕倒~~~看来还是没法构造真正的循环链表
append() 与 ++ 是等价的，或者说，++在编译时会转换成调用lists:append。
如果实现知道一个list的深度是1，可以用append而不要用flatten。
flatten需要遍历list的每一个元素，如果某个元素也是list，那么就要深入下去。
Write a Comment