[erlang-questions] Erlang shows its slow face!

[Richard O'Keefe]

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.
> py3(Max)->
> 	[{A,B,C} ||
> 		A <-lists:seq(1, Max),
> 		B <-lists:seq(1, Max),
> 		C <-lists:seq(1, Max),
> 		A*A + B*B =:= C*C,
> 		A+B+C =< Max].
> 
> 
> =======================================================================
> 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
> 
>