[erlang-questions] [erlang-question] How to comprehend two lists synchronously?
Ladislav Lenart
lenartlad@REDACTED
Fri Nov 18 11:09:49 CET 2011
Please read this:
http://www.erlang.org/doc/efficiency_guide/myths.html
Myth 2.3, especially the fifth paragraph, talks exactly about this
(the emphasis is mine):
In R12B and later releases, there is an optimization that will in many
cases reduces the number of words used on the stack in body-recursive
calls, so that a body-recursive list function and tail-recursive function
that calls lists:reverse/1 at the end will use *exactly the same amount of
memory*. lists:map/2, lists:filter/2, list comprehensions, and many other
recursive functions now use the same amount of space as their tail-recursive
equivalents.
My understanding of this is that if your recursive function produces result
proportional in size to the input (e.g. lists:map/2), use body-recursive call
(which is easier to read and understand) and let the compiler do its job.
HTH,
Ladislav Lenart
On 18.11.2011 09:36, Barco You wrote:
> Umm! I don't think there would be some difference between times consumed by these two functions, but I will assume there are difference in memory consumption.
>
>
>
> On Fri, Nov 18, 2011 at 3:49 PM, Dmitry Demeshchuk <demeshchuk@REDACTED <mailto:demeshchuk@REDACTED>> wrote:
>
> I think it's meant that lists:reverse/1 is called at the end of the
> _optimized_ code.
>
> Here's the module code:
>
> -module(test).
> -export([a/0, b/0]).
>
> a() ->
> L = lists:seq(1, 10000000), map2(fun (I, J) -> I + J end, L, L).
>
> b() ->
> L = lists:seq(1, 10000000),
> map3(fun (I, J) -> I + J end, L, L).
>
>
> map2(Fun, [H1 | T1], [H2 | T2]) ->
> [Fun(H1, H2) | map2(Fun, T1, T2)];
> map2(_, [], []) ->
> [].
>
> map3(_Fun, [], []) ->
> [];
> map3(Fun, L1, L2) ->
> map3(Fun, L1, L2, []).
>
> map3(_Fun, [], [], L) ->
> lists:reverse(L);
> map3(Fun, [H1 | T1], [H2 | T2], L) ->
> map3(Fun, T1, T2, [Fun(H1, H2) | L])
>
> Try to call timer:tc/3 yourself.
>
> On Fri, Nov 18, 2011 at 11:48 AM, Barco You <barcojie@REDACTED <mailto:barcojie@REDACTED>> wrote:
> > According to the instruction attached by Ulf, the body-recursive and
> > tail-recursive list function will be the same in consuming memory only when
> > they call lists:reverse/1 at the end.
> > So, I don't know how did you do the benchmarks. Did you compare these two
> > methods with big enough lists?
> > Or, I misunderstand the optimization instructions?
> >
> > BR,
> > Barco
> >
> > On Fri, Nov 18, 2011 at 3:37 PM, Dmitry Demeshchuk <demeshchuk@REDACTED <mailto:demeshchuk@REDACTED>>
> > wrote:
> >>
> >> Okay, I admit, this isn't an "honest" tail-recursed function, since a
> >> list concatenation operator is going to be called at the end. However,
> >> Erlang compiler optimizes such cases and converts them to
> >> tail-recursive:
> >> http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive
> >>
> >> Also, I've ran benchmarks with both implementations: mine and yours.
> >> And they result in the same performance.
> >>
> >> On Fri, Nov 18, 2011 at 11:06 AM, Barco You <barcojie@REDACTED <mailto:barcojie@REDACTED>> wrote:
> >> > Yes, Ryan's suggestion is a good generic solution for n lists and it's
> >> > tail-recursed.
> >> > Hi Dmitry,
> >> > Your version is just recursed but not tail-recursed, because your
> >> > function
> >> > needs a piece of memory to stack the intermediate result for every round
> >> > of
> >> > recursive calls. To be tail-recursed, the recursive calls should
> >> > eliminate
> >> > the linearly-increased memory consumption by adding an extra variable
> >> > (accumulator) and let the recursive function call it alone for every
> >> > round.
> >> >
> >> > On Fri, Nov 18, 2011 at 2:53 PM, Dmitry Demeshchuk
> >> > <demeshchuk@REDACTED <mailto:demeshchuk@REDACTED>>
> >> > wrote:
> >> >>
> >> >> Hi, Barco.
> >> >>
> >> >> Why do you think my version isn't tail-recursed? :) Take a look at
> >> >> lists:map/2 implementation, for example. It's just the same.
> >> >>
> >> >> List comprehensions just serve different purpose: for combinations
> >> >> from multiple list sources. My guess is that people need this
> >> >> operation more often than mapping over multiple list. Another problem
> >> >> is that you should be sure that all those lists have the same length.
> >> >>
> >> >> On Fri, Nov 18, 2011 at 10:38 AM, Barco You <barcojie@REDACTED <mailto:barcojie@REDACTED>> wrote:
> >> >> > Hi Dmitry,
> >> >> > What your suggested can really solve my problem, but it's not
> >> >> > Tail-Recursion. The tail-recursed solution should look like this;
> >> >> > map2(_Fun, [], []) ->
> >> >> > [];
> >> >> > map2(Fun, L1, L2) ->
> >> >> > map2(Fun, L1, L2, []).
> >> >> > map2(_Fun, [], [], L) ->
> >> >> > lists:reverse(L);
> >> >> > map2(Fun, [H1 | T1], [H2 | T2], L) ->
> >> >> > map2(Fun, T1, T2, [Fun(H1, H2) | L]).
> >> >> >
> >> >> > However, I'm still disappointed with the list comprehension which is
> >> >> > different from what I intuitively imagine about it.
> >> >> >
> >> >> > Regards,
> >> >> > Barco
> >> >> > On Fri, Nov 18, 2011 at 1:49 PM, Dmitry Demeshchuk
> >> >> > <demeshchuk@REDACTED <mailto:demeshchuk@REDACTED>>
> >> >> > wrote:
> >> >> >>
> >> >> >> My guess is you have to zip them together, or just write a
> >> >> >> tail-recursed function:
> >> >> >>
> >> >> >> map2(Fun, [H1 | T1], [H2 | T2]) ->
> >> >> >> [Fun(H1, H2) | map2(Fun, T1, T2)];
> >> >> >> map2(Fun, [], []) ->
> >> >> >> [].
> >> >> >>
> >> >> >> The second option definitely isn't a list comprehension, but it
> >> >> >> requires less memory and has lesser complexity.
> >> >> >>
> >> >> >> On Fri, Nov 18, 2011 at 9:45 AM, Barco You <barcojie@REDACTED <mailto:barcojie@REDACTED>>
> >> >> >> wrote:
> >> >> >> > Dear Erlangers,
> >> >> >> >
> >> >> >> > I hope to get a list from two lists like this:
> >> >> >> > [{a1,b1}, {a2,b2}, {a3,b3}] <- [a1, a2 a3], [b1, b2,
> >> >> >> > b3].
> >> >> >> > But if I use list comprehension, I got:
> >> >> >> > 10> [{D1,D2} || D1 <- [a1,a2,a3], D2 <- [b1,b2,b3]].
> >> >> >> > [{a1,b1},
> >> >> >> > {a1,b2},
> >> >> >> > {a1,b3},
> >> >> >> > {a2,b1},
> >> >> >> > {a2,b2},
> >> >> >> > {a2,b3},
> >> >> >> > {a3,b1},
> >> >> >> > {a3,b2},
> >> >> >> > {a3,b3}]
> >> >> >> >
> >> >> >> > So, my questions is how to comprehend list in synchronous way in
> >> >> >> > order
> >> >> >> > to
> >> >> >> > get what I want, rather than to compose the elements from two
> >> >> >> > lists
> >> >> >> > in
> >> >> >> > all
> >> >> >> > possible situations.
> >> >> >> >
> >> >> >> > Thank you,
> >> >> >> > Barco
> >> >> >> > _______________________________________________
> >> >> >> > erlang-questions mailing list
> >> >> >> > erlang-questions@REDACTED <mailto:erlang-questions@REDACTED>
> >> >> >> > http://erlang.org/mailman/listinfo/erlang-questions
> >> >> >> >
> >> >> >> >
> >> >> >>
> >> >> >>
> >> >> >>
> >> >> >> --
> >> >> >> Best regards,
> >> >> >> Dmitry Demeshchuk
> >> >> >
> >> >> >
> >> >>
> >> >>
> >> >>
> >> >> --
> >> >> Best regards,
> >> >> Dmitry Demeshchuk
> >> >
> >> >
> >>
> >>
> >>
> >> --
> >> Best regards,
> >> Dmitry Demeshchuk
> >
> >
>
>
>
> --
> Best regards,
> Dmitry Demeshchuk
>
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
More information about the erlang-questions
mailing list