Erlang/OTP Forums
Author Message

<  Erlang  ~  list comprehension question
Roman2K
Posted: Sat Aug 11, 2007 7:50 pm Reply with quote
Joined: 10 Aug 2007 Posts: 3
A little late, but to extend alexaandru's benchmark, here's another variant of the sort of zip function.

Code:
manual_reverse(L1, L2) -> manual_reverse(L1, L2, []).
manual_reverse([H1|T1], [H2|T2], Acc) ->
    manual_reverse(T1, T2, [[H1,H2] | Acc]);
manual_reverse([], [], Acc) ->
    lists:reverse(Acc).

It's basically the same as the last function in alexaandru's benchmark script, named "manual", but optimized (accumulates pairs at the top of a list, and returns this list reversed when the work is done).

The speed difference becomes perceivable when the lists to zip are at least five elements long (for example [1,2,3,4,5] and [6,7,8,9,10]).
Back to top View user's profile Send private message
parijat
Posted: Mon Aug 20, 2007 9:58 am Reply with quote
Joined: 19 Aug 2007 Posts: 4 Location: Singapore
The ++ operator is frowned upon in Programming Erlang. In Section 3.11:
Quote:

If you ever see code like this:
List ++ [H]
it should set alarm bells off in your brain—this is very inefficient and
acceptable only if List is very short.


So I could not resist adding:

Code:

manual1([Ha|Ta], [Hb|Tb]) ->
    manual1(Ta, Tb, [[Ha,Hb]]).

manual1([Ha|Ta], [Hb|Tb], Acc) ->
    manual1(Ta, Tb, [[Ha,Hb]|Acc]);
manual1([], [], Acc) ->
    lists:reverse(Acc).


And timed it:

Code:

4> benchmarks_are_fun:test(10000).
{{map_zip,15000},
 {list_comprehension_zip_and_pattern_matching,1},
 {list_comprehension_zip_tuple_to_list,15997},
 {list_comprehension_nth,15999},
 {manual_recursive,1},
 {manual1_recursive,1}}


Not much difference. But then, our lists are small. How about we define the lists to be:
Code:

-define(A, [1,2,3,...,100]).
-define(B, [1001,1002,1003,...,1100]).
-define(Control, [[1,1001],[2,1002],...,[100,1100]]).



(That is, three lists with 100 elements each. The ... are added by me. The code contains the full list.)

Code:

3> benchmarks_are_fun:test(10000).
{{map_zip,265000},
 {list_comprehension_zip_and_pattern_matching,155999},
 {list_comprehension_zip_tuple_to_list,171999},
 {list_comprehension_nth,5327999},
 {manual_recursive,765999},
 {manual1_recursive,155999}}


Now you can see the difference between ++ and |, reverse. But zip_and_pattern_matching and manual1 take the same time? Let's try.

Code:

4> benchmarks_are_fun:test(20000).
{{map_zip,547000},
 {list_comprehension_zip_and_pattern_matching,327999},
 {list_comprehension_zip_tuple_to_list,358999},
 {list_comprehension_nth,10671999},
 {manual_recursive,1515999},
 {manual1_recursive,295999}}


Now manual1 comes out the fastest, even faster than zip_and_pattern_matching.

I guess we could say:

  • The zip solutions are most generic because they can handle any number of lists, not just two.
  • Of the three strategies to convert tuple to list, a fun is the slowest (map_zip) presumably because of the function call overhead, followed by tuple_to_list (again function call overhead, but the function is a BIF), followed by pattern matching (because it does the same thing as tuple_to_list without a function call?).
  • ++ is clearly slower than add-to-head/reverse idiom.
Back to top View user's profile Send private message

Display posts from previous:  

All times are GMT
View next topic
View previous topic
Page 2 of 2
Goto page Previous  1, 2
Erlang Forum - Trap Exit Forum Index  ~  Erlang
This forum is locked: you cannot post, reply to, or edit topics.

Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
Hosted by Erlang Solutions    |    Powered by phpBB and NoseBleed 1.14