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.<div><br></div><div><br><div><br><div class="gmail_quote">On Fri, Nov 18, 2011 at 3:49 PM, Dmitry Demeshchuk <span dir="ltr"><<a href="mailto:demeshchuk@gmail.com">demeshchuk@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">I think it's meant that lists:reverse/1 is called at the end of the<br>
_optimized_ code.<br>
<br>
Here's the module code:<br>
<br>
-module(test).<br>
-export([a/0, b/0]).<br>
<br>
a() -><br>
L = lists:seq(1, 10000000), map2(fun (I, J) -> I + J end, L, L).<br>
<br>
b() -><br>
L = lists:seq(1, 10000000),<br>
map3(fun (I, J) -> I + J end, L, L).<br>
<div class="im"><br>
<br>
map2(Fun, [H1 | T1], [H2 | T2]) -><br>
[Fun(H1, H2) | map2(Fun, T1, T2)];<br>
</div>map2(_, [], []) -><br>
[].<br>
<br>
map3(_Fun, [], []) -><br>
[];<br>
map3(Fun, L1, L2) -><br>
map3(Fun, L1, L2, []).<br>
<br>
map3(_Fun, [], [], L) -><br>
lists:reverse(L);<br>
map3(Fun, [H1 | T1], [H2 | T2], L) -><br>
map3(Fun, T1, T2, [Fun(H1, H2) | L])<br>
<br>
Try to call timer:tc/3 yourself.<br>
<div class="HOEnZb"><div class="h5"><br>
On Fri, Nov 18, 2011 at 11:48 AM, Barco You <<a href="mailto:barcojie@gmail.com">barcojie@gmail.com</a>> wrote:<br>
> According to the instruction attached by Ulf, the body-recursive and<br>
> tail-recursive list function will be the same in consuming memory only when<br>
> they call lists:reverse/1 at the end.<br>
> So, I don't know how did you do the benchmarks. Did you compare these two<br>
> methods with big enough lists?<br>
> Or, I misunderstand the optimization instructions?<br>
><br>
> BR,<br>
> Barco<br>
><br>
> On Fri, Nov 18, 2011 at 3:37 PM, Dmitry Demeshchuk <<a href="mailto:demeshchuk@gmail.com">demeshchuk@gmail.com</a>><br>
> wrote:<br>
>><br>
>> Okay, I admit, this isn't an "honest" tail-recursed function, since a<br>
>> list concatenation operator is going to be called at the end. However,<br>
>> Erlang compiler optimizes such cases and converts them to<br>
>> tail-recursive:<br>
>> <a href="http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive" target="_blank">http://www.erlang.org/doc/efficiency_guide/myths.html#tail_recursive</a><br>
>><br>
>> Also, I've ran benchmarks with both implementations: mine and yours.<br>
>> And they result in the same performance.<br>
>><br>
>> On Fri, Nov 18, 2011 at 11:06 AM, Barco You <<a href="mailto:barcojie@gmail.com">barcojie@gmail.com</a>> wrote:<br>
>> > Yes, Ryan's suggestion is a good generic solution for n lists and it's<br>
>> > tail-recursed.<br>
>> > Hi Dmitry,<br>
>> > Your version is just recursed but not tail-recursed, because your<br>
>> > function<br>
>> > needs a piece of memory to stack the intermediate result for every round<br>
>> > of<br>
>> > recursive calls. To be tail-recursed, the recursive calls should<br>
>> > eliminate<br>
>> > the linearly-increased memory consumption by adding an extra variable<br>
>> > (accumulator) and let the recursive function call it alone for every<br>
>> > round.<br>
>> ><br>
>> > On Fri, Nov 18, 2011 at 2:53 PM, Dmitry Demeshchuk<br>
>> > <<a href="mailto:demeshchuk@gmail.com">demeshchuk@gmail.com</a>><br>
>> > wrote:<br>
>> >><br>
>> >> Hi, Barco.<br>
>> >><br>
>> >> Why do you think my version isn't tail-recursed? :) Take a look at<br>
>> >> lists:map/2 implementation, for example. It's just the same.<br>
>> >><br>
>> >> List comprehensions just serve different purpose: for combinations<br>
>> >> from multiple list sources. My guess is that people need this<br>
>> >> operation more often than mapping over multiple list. Another problem<br>
>> >> is that you should be sure that all those lists have the same length.<br>
>> >><br>
>> >> On Fri, Nov 18, 2011 at 10:38 AM, Barco You <<a href="mailto:barcojie@gmail.com">barcojie@gmail.com</a>> wrote:<br>
>> >> > Hi Dmitry,<br>
>> >> > What your suggested can really solve my problem, but it's not<br>
>> >> > Tail-Recursion. The tail-recursed solution should look like this;<br>
>> >> > map2(_Fun, [], []) -><br>
>> >> > [];<br>
>> >> > map2(Fun, L1, L2) -><br>
>> >> > map2(Fun, L1, L2, []).<br>
>> >> > map2(_Fun, [], [], L) -><br>
>> >> > lists:reverse(L);<br>
>> >> > map2(Fun, [H1 | T1], [H2 | T2], L) -><br>
>> >> > map2(Fun, T1, T2, [Fun(H1, H2) | L]).<br>
>> >> ><br>
>> >> > However, I'm still disappointed with the list comprehension which is<br>
>> >> > different from what I intuitively imagine about it.<br>
>> >> ><br>
>> >> > Regards,<br>
>> >> > Barco<br>
>> >> > On Fri, Nov 18, 2011 at 1:49 PM, Dmitry Demeshchuk<br>
>> >> > <<a href="mailto:demeshchuk@gmail.com">demeshchuk@gmail.com</a>><br>
>> >> > wrote:<br>
>> >> >><br>
>> >> >> My guess is you have to zip them together, or just write a<br>
>> >> >> tail-recursed function:<br>
>> >> >><br>
>> >> >> map2(Fun, [H1 | T1], [H2 | T2]) -><br>
>> >> >> [Fun(H1, H2) | map2(Fun, T1, T2)];<br>
>> >> >> map2(Fun, [], []) -><br>
>> >> >> [].<br>
>> >> >><br>
>> >> >> The second option definitely isn't a list comprehension, but it<br>
>> >> >> requires less memory and has lesser complexity.<br>
>> >> >><br>
>> >> >> On Fri, Nov 18, 2011 at 9:45 AM, Barco You <<a href="mailto:barcojie@gmail.com">barcojie@gmail.com</a>><br>
>> >> >> wrote:<br>
>> >> >> > Dear Erlangers,<br>
>> >> >> ><br>
>> >> >> > I hope to get a list from two lists like this:<br>
>> >> >> > [{a1,b1}, {a2,b2}, {a3,b3}] <- [a1, a2 a3], [b1, b2,<br>
>> >> >> > b3].<br>
>> >> >> > But if I use list comprehension, I got:<br>
>> >> >> > 10> [{D1,D2} || D1 <- [a1,a2,a3], D2 <- [b1,b2,b3]].<br>
>> >> >> > [{a1,b1},<br>
>> >> >> > {a1,b2},<br>
>> >> >> > {a1,b3},<br>
>> >> >> > {a2,b1},<br>
>> >> >> > {a2,b2},<br>
>> >> >> > {a2,b3},<br>
>> >> >> > {a3,b1},<br>
>> >> >> > {a3,b2},<br>
>> >> >> > {a3,b3}]<br>
>> >> >> ><br>
>> >> >> > So, my questions is how to comprehend list in synchronous way in<br>
>> >> >> > order<br>
>> >> >> > to<br>
>> >> >> > get what I want, rather than to compose the elements from two<br>
>> >> >> > lists<br>
>> >> >> > in<br>
>> >> >> > all<br>
>> >> >> > possible situations.<br>
>> >> >> ><br>
>> >> >> > Thank you,<br>
>> >> >> > Barco<br>
>> >> >> > _______________________________________________<br>
>> >> >> > erlang-questions mailing list<br>
>> >> >> > <a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
>> >> >> > <a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
>> >> >> ><br>
>> >> >> ><br>
>> >> >><br>
>> >> >><br>
>> >> >><br>
>> >> >> --<br>
>> >> >> Best regards,<br>
>> >> >> Dmitry Demeshchuk<br>
>> >> ><br>
>> >> ><br>
>> >><br>
>> >><br>
>> >><br>
>> >> --<br>
>> >> Best regards,<br>
>> >> Dmitry Demeshchuk<br>
>> ><br>
>> ><br>
>><br>
>><br>
>><br>
>> --<br>
>> Best regards,<br>
>> Dmitry Demeshchuk<br>
><br>
><br>
<br>
<br>
<br>
--<br>
Best regards,<br>
Dmitry Demeshchuk<br>
</div></div></blockquote></div><br></div></div>