[erlang-questions] Erlang shows its slow face!

[Joe Armstrong]

I think you can do a wee bit better ...

py3a(Max) ->
    N = Max div 2,
    [{A,B,C} ||
	A <- lists:seq(1,N+1),
	B <- lists:seq(1,Max-A),
	C <- lists:seq(1,Max-A-B),
	A*A + B*B =:= C*C].

Since the largest side of the triangle (A) cannot be bigger than Max/2

/Joe



On Mon, Nov 15, 2010 at 2:06 AM, Richard O'Keefe <ok@REDACTED> wrote:
>
> On 13/11/2010, at 8:37 PM, Gilberto Carmenate García wrote:
>
>> Hi all!
>> I have been doing tests to Erlang I found this funny stuff that makes
>> Pythagorean Triplets
>>
>> pythag(N) ->
>>    [ {A,B,C} ||
>>        A <- lists:seq(1,N),
>>        B <- lists:seq(1,N),
>>        C <- lists:seq(1,N),
>>        A+B+C =< N,
>>        A*A+B*B =:= C*C].
>
> That's not as efficient as it could be.
>
>        C <- lists:seq(1, N),
>        A <- lists:seq(1, N-C-1),
>        B <- lists:seq(1, N-C-A),
>
> does a factor of 6 or better fewer iterations (tested up to N = 500).
>
> We can do better still.  Since A^2 + B^2 = C^2, C >= max(A,B),
> so it follows that A, B are both <= (N-1) div 2, and
> given A and B there is only one possible C.
> So there are only about (N*N)/4 cases to check instead of N*N*N,
>
> Here's a table.
>
> Fun   N      Iters   Filtered    Answers
> old  10       1000        120          0
> new  10        120        120          0
> sqt  10         16         13          0
> old  20       8000       1140          2
> new  20       1140       1140          2
> sqt  20         81         58          2
> old  50     125000      19600         12
> new  50      19600      19600         12
> sqt  50        576        372         12
> old 100    1000000     161700         34
> new 100     161700     161700         34
> sqt 100       2401       1513         34
> old 200    8000000    1313400         86
> new 200    1313400    1313400         86
> sqt 200       9801       6094         86
> old 500  125000000   20708500        274
> new 500   20708500   20708500        274
> sqt 500      62001      38258        274
>
> Fun is old (your loop nest), new (my CAB loop nest above), or
> sqt (AB loop nest with C = hypot(A,B) truncated to integer);
> N is N; Iters is the number of iterations of the loop nest;
> Filtered is the number of cases that pass the A+B+C =< N
> filter, and Answers is the number of triples found this way.
>
> !!!! Looking at the last line, we see a reduction in iterations
> !!!! by a factor of 2016.1, which dwarfs any difference between
> !!!! Erlang and C#.  (And it's possible to do even better.)
>
> One issue of course is that C# is presumably not building
> and iterating over any lists at all here, so if you want
> a *fair* comparison between C# and Erlang, your iterations
> should not iterate over any lists either.
>
>        p
>
>
>
>
>
>>
>> I tested it agains an implementation I made in C# so, and takes 14
>> secounds in my pc to do with 300 numbers in Erlang however in c# is just
>> a secound, even when C# runs under VM too.
>> So I did all possible ways for me to implement differents manners in
>> Erlang looking for speed and all is the same, listed as  follows:
>>
>> So my question is, there are any way to do that even more fast, why 3
>> nestes fors structs in C# are more effients that lists:foldr or
>> lists:foreach in Erlang.
>>
>> %% FORMA 1
>> py1(Max)->
>>    L = lists:seq(1, Max),
>>    lists:foldr(
>>        fun(A, Acc3)->
>>            lists:foldr(
>>                fun(B, Acc2)->
>>                    lists:foldr(
>>                        fun(C, Acc)->
>>                            case ((A*A + B*B =:= C*C) andalso (A+B+C =<
>> Max)) of
>>                                                               true->
>>                                    [{A,B,C}|Acc];
>>                                false->
>>                                    Acc
>>                            end
>>                        end
>>                    , Acc2, L)
>>                end
>>            , Acc3, L)
>>        end
>>    , [], L).
>>
>>
>>
>> %% FORMA 2
>> py2(Max)->
>>       fora(1, [], Max).
>>
>> fora(A, Acc, Max)->
>>       Acc1 = forb(A,1, Acc, Max),
>>       case A < Max of
>>        true->
>>            fora(A+1, Acc1, Max);
>>        false->
>>            Acc1
>>    end.
>>
>> forb(A,B, Acc, Max)->
>>    Acc1 = forc(A,B,1, Acc, Max),
>>    case B < Max of
>>        true->
>>            forb(A,B+1, Acc1, Max);
>>        false->
>>            Acc1
>>    end.
>>
>> forc(A,B,C, Acc, Max)->
>>    Acc1 = case (A*A + B*B =:= C*C) andalso (A+B+C =< Max) of
>>        true->
>>            [{A,B,C}|Acc];
>>        _->
>>            Acc
>>    end,
>>    case C < Max of
>>        true->
>>            forc(A,B,C+1, Acc1, Max);
>>        false->
>>            Acc1
>>    end.
>>
>> %% FORMA 3.
>>
>>
>> =======================================================================
>> Este mensaje ha sido enviado mediante el servicio de correo electronico que ofrece la Federacion de Radioaficionados de Cuba a sus miembros para respaldar el cumplimiento de los objetivos de la organizacion y su politica informativa. La persona que envia este correo asume el compromiso de  usar el servicio a tales fines y cumplir con las regulaciones establecidas.
>>
>>
>>
>> ________________________________________________________________
>> erlang-questions (at) erlang.org mailing list.
>> See http://www.erlang.org/faq.html
>> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>>
>>
>
>
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>
>