[erlang-questions] [erlang-question] How to comprehend two lists synchronously?

Barco You <>
Fri Nov 18 16:37:38 CET 2011


Probably because the recursions over lists have been already optimized by
the compiler, there is almost no difference between body-recursion and
tail-recursion.
On Nov 18, 2011 11:29 PM, "Dmitry Demeshchuk" <> wrote:

> If it's garbage collected on your system, try to decrease the lists
> size so GC won't be run automatically. On my laptop, as you can see,
> each process eats about 40MB of RAM, which seems to be more or less
> correct.
>
> On Fri, Nov 18, 2011 at 7:08 PM, Barco You <> wrote:
> > Seemingly our methods are all not correct for measuring memory
> consumption.
> > If measuring in the middle as I did, we just get the instant value at a
> > moment, whereas if measuring after the function returns by waiting for
> > several seconds as you did, all the memory ever used have been garbage
> > collected. So I think what we need to do for profiling the functions is
> to
> > draw a curve with memory consumption against time elapsed. But I dont
> know
> > how to do that.
> >
> > On Nov 18, 2011 5:41 PM, "Dmitry Demeshchuk" <>
> wrote:
> >>
> >> That's not the correct way. You were measuring the processes memory in
> >> the middle of calculations.
> >>
> >> 1> A = spawn(fun () -> test:a(), receive _ -> ok end end).
> >> <0.46.0>
> >> 2> B = spawn(fun () -> test:b(), receive _ -> ok end end).
> >> <0.48.0>
> >> 3> process_info(A, memory).
> >> {memory,391814792}
> >> 4> process_info(B, memory).
> >> {memory,401610112}
> >>
> >> Note that I waited for several seconds before entering commands 3 and 4.
> >>
> >> On Fri, Nov 18, 2011 at 1:32 PM, Barco You <> wrote:
> >> > Very strange! By using another measuring method as below I got that
> your
> >> > function is far better than mine in memory consumption.
> >> >
> >> > -module(test).
> >> > -export([a/0, b/0]).
> >> > a() ->
> >> >         L = lists:seq(1, 10000000),
> >> >         map2(fun (I, J) -> I + J end, L, L),
> >> >         receive
> >> >                 stop ->
> >> >                         ok
> >> >         end.
> >> > b() ->
> >> >         L = lists:seq(1, 10000000),
> >> >         map3(fun (I, J) -> I + J end, L, L),
> >> >         receive
> >> >                 stop ->
> >> >                         ok
> >> >         end.
> >> >
> >> > 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]).
> >> >
> >> > Eshell V5.8.4  (abort with ^G)
> >> > 1> A = spawn(test,a,[]).
> >> > <0.32.0>
> >> > 2> B = spawn(test,b,[]).
> >> > <0.34.0>
> >> > 3> erlang:process_info(A,memory).
> >> > {memory,176316700}
> >> > 4> erlang:process_info(B,memory).
> >> > {memory,306105040}
> >> >
> >> >
> >> >
> >> > On Fri, Nov 18, 2011 at 4:53 PM, Dmitry Demeshchuk
> >> > <>
> >> > wrote:
> >> >>
> >> >> I'm not sure it is so. Try running this function several times:
> >> >>
> >> >> memtest() ->
> >> >>    erlang:garbage_collect(),
> >> >>    M1 = proplists:get_value(total, erlang:memory()),
> >> >>    a(),
> >> >>    M2 = proplists:get_value(total, erlang:memory()),
> >> >>    b(),
> >> >>    M3 = proplists:get_value(total, erlang:memory()),
> >> >>    {M2 - M1, M3 - M2}.
> >> >>
> >> >> The results are pretty the same.
> >> >>
> >> >> On Fri, Nov 18, 2011 at 12:36 PM, 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
> >> >> > <>
> >> >> > 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 <>
> >> >> >> 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
> >> >> >> > <>
> >> >> >> > 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 <
> >
> >> >> >> >> 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
> >> >> >> >> > <>
> >> >> >> >> > 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
> >> >> >> >> >> <>
> >> >> >> >> >> 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
> >> >> >> >> >> > <>
> >> >> >> >> >> > 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
> >> >> >> >> >> >> <>
> >> >> >> >> >> >> 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
> >> >> >> >> >> >> > 
> >> >> >> >> >> >> > http://erlang.org/mailman/listinfo/erlang-questions
> >> >> >> >> >> >> >
> >> >> >> >> >> >> >
> >> >> >> >> >> >>
> >> >> >> >> >> >>
> >> >> >> >> >> >>
> >> >> >> >> >> >> --
> >> >> >> >> >> >> Best regards,
> >> >> >> >> >> >> Dmitry Demeshchuk
> >> >> >> >> >> >
> >> >> >> >> >> >
> >> >> >> >> >>
> >> >> >> >> >>
> >> >> >> >> >>
> >> >> >> >> >> --
> >> >> >> >> >> Best regards,
> >> >> >> >> >> Dmitry Demeshchuk
> >> >> >> >> >
> >> >> >> >> >
> >> >> >> >>
> >> >> >> >>
> >> >> >> >>
> >> >> >> >> --
> >> >> >> >> Best regards,
> >> >> >> >> Dmitry Demeshchuk
> >> >> >> >
> >> >> >> >
> >> >> >>
> >> >> >>
> >> >> >>
> >> >> >> --
> >> >> >> Best regards,
> >> >> >> Dmitry Demeshchuk
> >> >> >
> >> >> >
> >> >>
> >> >>
> >> >>
> >> >> --
> >> >> Best regards,
> >> >> Dmitry Demeshchuk
> >> >
> >> >
> >>
> >>
> >>
> >> --
> >> Best regards,
> >> Dmitry Demeshchuk
> >
>
>
>
> --
> Best regards,
> Dmitry Demeshchuk
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111118/f08cdab8/attachment.html>


More information about the erlang-questions mailing list