[erlang-questions] Hi all here the RESUME for Pytagorians Numbers Algorithm!!!
Edmond Begumisa
ebegumisa@REDACTED
Mon Nov 15 17:30:27 CET 2010
It's interesting to see that parallelising on a single core comes at 0
cost. Why did I think parallel versions would be slightly slower on a
single core machine? I was even tempted to put in a test and only go
parallel if there's more than one core.
BTW, are you sure your py2 algo is wrong or does it just return the list
in a different order? Try sorting the lists before the =:= test.
- Edmond -
On Mon, 15 Nov 2010 15:25:24 +1100, Gilberio Carmenates García
<co7eb@REDACTED> wrote:
>
> Made on a pc with Petium 4 CPU 1.6 Ghz one core, 512 Ram.
>
> *** Pytagoriam's Numbers REPORT! ***
>
> Using N = 300
>
> *** THE ORIGINAL IMPLEMENTATIONS (ME!)****
> -py1: 15547000 mcs = 15.547 s
> -py2: 14514999 mcs = 14.514999 s
> -py3: 14468999 mcs = 14.468999 s
>
> *** Tony's implementations ****
> -pythag1: 13218999 mcs = 13.218999 s
> -pythag2: 2296999 mcs = 2.296999 s
>
> *** Hynek's implementation ****
> Simpler and about 5% faster version
> -pythag3: 2202999 mcs = 2.202999 s
>
> *** Edmond's implementation, using parallelism****
> -py2E: 14624999 mcs = 14.624999 s
>
> *** Willem's implementation****
> -wpythag2: 2202999 mcs = 2.202999 s
>
> *** Hynek's new implementation****
> -pythag4: 1530999 mcs = 1.530999 s
>
> *** Willem's new implementation in parallel by Hynek****
> -wpythag2P: 2202999 mcs = 2.202999 s
>
> *** Morten's implementation****
> -pythag5: 62999 mcs = 0.062999 s
>
> *** Richard's improvement****
> -py3R: 2452999 mcs = 2.452999 s
>
> Comparisons in results agains 'pythag1' Tony's function
> py1 returns the same than 'pythag1'
> py2 NO returns the same than 'pythag1' %% since my secound
> implementation 'py2' is wrong!!!
> py3 returns the same than 'pythag1'
> pythag1 returns the same than 'pythag1'
> pythag2 returns the same than 'pythag1'
> pythag3 returns the same than 'pythag1'
> py2E NO returns the same than 'pythag1' %% since Edmond use my
> wrong implementation.
> wpythag2 returns the same than 'pythag1'
> pythag4 returns the same than 'pythag1'
> wpythag2P returns the same than 'pythag1'
> pythag5 returns the same than 'pythag1'
> py3R NO returns the same than 'pythag1' %% I just tries to put the
> Richard explanation in a
> algorithm but, seems to
> me I was wrong here too.
>
> NOTE: Time was took using timer:tc/3 function.
>
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Here the source code of all algorithm
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>
>
> -module(py).
> -compile([export_all]).
>
>
> start(N)->
> %% My implementations.
> {T1,R1} = timer:tc(py,py1, [N]),
> {T2,R2} = timer:tc(py,py2,[N]),
> {T3,R3} = timer:tc(py,py3,[N]),
>
> %% Tony's improvement of the original form 3.
> {T4,R4} = timer:tc(py,pythag1,[N]),
> %% Tony's implementation.
> {T5,R5} = timer:tc(py,pythag2,[N]),
>
> %% Hynek's implementation.
> %% Simpler and about 5% faster version:
> {T6,R6} = timer:tc(py,pythag3,[N]),
>
> %% Edmond's implementation using parallelism.
> {T7,R7} = timer:tc(py,py2E,[N]),
>
> %% Willem's implementation.
> {T8,R8} = timer:tc(py,wpythag2,[N]),
>
> %% Hynek's new version
> {T9,R9} = timer:tc(py,pythag4,[N]),
>
> %% Willem's implementation in parallel by Hynek
> {T10,R10} = timer:tc(py,wpythag2P,[N]),
>
> %% Morten's implementation.
> {T11,R11} = timer:tc(py,pythag5,[N]),
>
> %% Richard's improvement.
> {T12,R12} = timer:tc(py,py3R,[N]),
>
> io:format("~n *** Pytagoriam's Numbers REPORT! ***~n~n"),
> io:format("Using N = ~p~n", [N]),
>
> io:format("~n*** THE ORIGINAL IMPLEMENTATIONS (ME!)****~n"),
> io:format("-py1: ~p mcs = ~p s~n", [T1,T1/1000000]),
> io:format("-py2: ~p mcs = ~p s~n", [T2,T2/1000000]),
> io:format("-py3: ~p mcs = ~p s~n", [T3,T3/1000000]),
>
> io:format("~n*** Tony's implementations ****~n"),
> io:format("-pythag1: ~p mcs = ~p s~n", [T4,T4/1000000]),
> io:format("-pythag2: ~p mcs = ~p s~n", [T5,T5/1000000]),
>
> io:format("~n*** Hynek's implementation ****~n"),
> io:format("Simpler and about 5% faster version~n"),
> io:format("-pythag3: ~p mcs = ~p s~n", [T6,T6/1000000]),
>
> io:format("~n*** Edmond's implementation, using parallelism****~n"),
> io:format("-py2E: ~p mcs = ~p s~n", [T7,T7/1000000]),
>
> io:format("~n*** Willem's implementation****~n"),
> io:format("-wpythag2: ~p mcs = ~p s~n", [T8,T8/1000000]),
>
> io:format("~n*** Hynek's new implementation****~n"),
> io:format("-pythag4: ~p mcs = ~p s~n", [T9,T9/1000000]),
>
> io:format("~n*** Willem's new implementation in parallel by
> Hynek****~n"),
> io:format("-wpythag2P: ~p mcs = ~p s~n", [T10,T10/1000000]),
>
> io:format("~n*** Morten's implementation****~n"),
> io:format("-pythag5: ~p mcs = ~p s~n", [T11,T11/1000000]),
>
> io:format("~n*** Richard's improvement****~n"),
> io:format("-py3R: ~p mcs = ~p s~n", [T12,T12/1000000]),
>
> io:format("~nComparisons in results agains 'pythag1' Tony's
> function~n"),
> Rs = [{py1,R1}, {py2,R2}, {py3,R3}, {pythag1,R4}, {pythag2,R5},
> {pythag3,R6},
> {py2E,R7}, {wpythag2,R8}, {pythag4,R9}, {wpythag2P,R10},
> {pythag5,R11}, {py3R,R12}],
> lists:foreach(fun({Name, R})->
> if
> (R=:=R4)->
> io:format("~p returns the same than 'pythag1'~n",
> [Name]);
> true->
> io:format("~p NO returns the same than 'pythag1'~n",
> [Name])
> end
> end, Rs),
> io:format("~nNOTE: Time took using timer:tc/3 function.~n").
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% The original form 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).
>
>
>
> %% The original form 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.
>
> %% The original form 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].
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Tony's improvement of the original form 3.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> pythag1(N) ->
> L = lists:seq(1,N),
> [ {A,B,C} ||
> A<- L,
> B<- L,
> C<- L,
> A+B+C =< N,
> A*A+B*B =:= C*C].
>
> %% Tony's implementation.
> pythag2(N) ->
> lists:reverse(pythan2_A(1, N, [])).
>
> pythan2_A(A, N, Acc) when A> N -> Acc;
> pythan2_A(A, N, Acc) -> pythan2_A(A+1,N,pythan2_B(A, 1, N, Acc)).
>
> pythan2_B(A, B, N, Acc) when A+B> N -> Acc;
> pythan2_B(A, B, N, Acc) -> pythan2_B(A,B+1,N,pythan2_C(A, B, 1, N,
> Acc)).
>
> pythan2_C(A, B, C, N, Acc) when A+B+C> N -> Acc;
> pythan2_C(A, B, C, N, Acc) ->
> if A*A+B*B =:= C*C ->
> pythan2_C(A, B, C+1, N, [{A,B,C}|Acc]);
> true ->
> pythan2_C(A, B, C+1, N, Acc)
> end.
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Hynek's implementation.
> %% Simpler and about 5% faster version:
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> pythag3(N) when is_integer(N) -> pythag3(N,1).
>
> pythag3(N, A) when A+2> N -> [];
> pythag3(N, A) -> pythag3(N, A, 1).
>
> pythag3(N, A, B) when A+B+1> N -> pythag3(N, A+1);
> pythag3(N, A, B) -> pythag3(N, A, B, 1).
>
> pythag3(N, A, B, C) when A+B+C> N -> pythag3(N, A, B+1);
> pythag3(N, A, B, C) when A*A + B*B =:= C*C -> [{A, B, C}|pythag3(N, A,
> B, C+1)];
> pythag3(N, A, B, C) -> pythag3(N, A, B, C+1).
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Edmond's implementation using parallelism.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> %%---- START CODE ----
>
> py2E(Max)->
> lists:flatten(lpmap(fun(A) ->
> forbE(A, 1, [], Max)
> end, lists:seq(1, Max), ordered)).
>
> forbE(A, B, Acc, Max) ->
> Acc1 = forcE(A, B, 1, Acc, Max),
> case B< Max of
> true -> forbE(A, B+1, Acc1, Max);
> false -> Acc1
> end.
>
> forcE(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-> forcE(A, B, C+1, Acc1, Max);
> false-> Acc1
> end.
>
>
> pythag2E(N)->
> lists:flatten(lpmap(fun(A) ->
> pythan2_BE(A, 1, N, [])
> end, lists:seq(1, N), ordered)).
>
> pythan2_AE(A, N, Acc) when A> N -> Acc;
> pythan2_AE(A, N, Acc) -> pythan2_AE(A+1,N,pythan2_BE(A, 1, N, Acc)).
>
> pythan2_BE(A, B, N, Acc) when A+B> N -> Acc;
> pythan2_BE(A, B, N, Acc) -> pythan2_BE(A,B+1,N,pythan2_CE(A, B, 1, N,
> Acc)).
>
> pythan2_CE(A, B, C, N, Acc) when A+B+C> N -> Acc;
> pythan2_CE(A, B, C, N, Acc) ->
> if A*A+B*B =:= C*C ->
> pythan2_CE(A, B, C+1, N, [{A,B,C}|Acc]);
> true ->
> pythan2_CE(A, B, C+1, N, Acc)
> end.
>
> %% @spec lpmap(fun(), list(), (atom() = ordered|unordered)) -> list()
> %% @doc Spawns a process for each element in list L, performs
> specified
> %% function F against each in parallel and then returns results
> either
> %% same order as L (ordered) or in any order (unordered).
> %% NB: See also lpmap/4.
>
> lpmap(F, L, ordered) ->
> Ref = erlang:make_ref(),
> Pids = [lpmap_spawn_link(self(), Ref, F, I) || I<- L],
> lpmap_gather_ordered(Pids, Ref, [], 0, void);
> lpmap(F, L, unordered) ->
> Ref = erlang:make_ref(),
> lists:foreach(fun(I) ->
> lpmap_spawn_link(self(), Ref, F, I)
> end, L),
> lpmap_gather_unordered(length(L), Ref, [], 0, void).
>
> %% @spec lpmap(fun(), integer(), list(), (atom() =
> ordered|unordered)) -> list()
> %% @doc Same as lpmap/3 except ensures only a maximum of MaxPs
> parallel
> %% processes execute function F at any one time (i.e. first
> takes MaxPs
> %% items from list, executes F in parallel against each, then
> as each
> %% process returns, spawns another process on next item in L as
> long as
> %% active processes are less than MaxPs).
> %% NB: See also lpmap/4.
>
> lpmap(F, L, MaxPs, ordered) when MaxPs>0 ->
> Ref = erlang:make_ref(),
> {HPids, TPids} = if
> length(L)> MaxPs -> lists:split(MaxPs, L);
> true -> {L, []}
> end,
> Pids = [lpmap_spawn_link(self(), Ref, F, I) || I<- HPids],
> lpmap_gather_ordered(Pids, Ref, TPids, MaxPs, F);
> lpmap(F, L, MaxPs, unordered) when MaxPs>0 ->
> Ref = erlang:make_ref(),
> {HPids, TPids} = if
> length(L)> MaxPs -> lists:split(MaxPs, L);
> true -> {L, []}
> end,
> lists:foreach(fun(I) ->
> lpmap_spawn_link(self(), Ref, F, I)
> end, HPids),
> lpmap_gather_unordered(length(HPids), Ref, TPids, MaxPs, F).
>
> %% lpmap internal functions
>
> lpmap_spawn_link(Parent, Ref, F, I) ->
> spawn_link(fun() ->
> Parent ! {self(), Ref, F(I)}
> end).
>
> lpmap_gather_ordered([], _Ref, [], _MaxPs, _F) ->
> [];
> lpmap_gather_ordered([HPid|TPids], Ref, L, MaxPs, F) ->
> receive
> {HPid, Ref, Ret} when length(TPids)<MaxPs, L=/=[] ->
> [H | T] = L,
> [Ret | lpmap_gather_ordered(
> lists:append(TPids, [lpmap_spawn_link(self(), Ref, F,
> H)]),
> Ref, T, MaxPs, F)];
> {HPid, Ref, Ret} ->
> [Ret | lpmap_gather_ordered(TPids, Ref, L, MaxPs, F)]
> end.
>
> lpmap_gather_unordered(0, _Ref, [], _MaxPs, _F) ->
> [];
> lpmap_gather_unordered(NPs, Ref, L, MaxPs, F) ->
> receive
> {_Pid, Ref, Ret} when NPs-1<MaxPs, L=/=[] ->
> [H | T] = L,
> lpmap_spawn_link(self(), Ref, F, H),
> [Ret | lpmap_gather_unordered(NPs, Ref, T, MaxPs, F)];
> {_Pid, Ref, Ret} ->
> [Ret | lpmap_gather_unordered(NPs-1, Ref, L, MaxPs, F)]
> end.
>
>
> %%---- END CODE -----
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Willem's implementation.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> wpythag2(N) ->
> L = [{A, A*A} || A<- lists:seq(1,N)],
> lists:flatten([forAllBs(A, A2, L, N) || {A, A2}<- L]).
>
> forAllBs(A, A2, L, N) ->
> [forAllCs(A, B, A + B, A2 + B2, L, N) || {B, B2}<- L, A + B< N].
>
> forAllCs(A, B, AB, A2B2, L, N) ->
> [{A, B, C} || {C, C2}<- L, A2B2 =:= C2, AB + C =< N].
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Hynek's new version
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> pythag4(N) when is_integer(N) -> pythag4(N,1).
>
> pythag4(N, A) when A+2> N -> [];
> pythag4(N, A) -> pythag4(N, A, A*A, 1).
>
> pythag4(N, A, _A2, B) when A+B+1> N -> pythag4(N, A+1);
> pythag4(N, A, A2, B) -> pythag4(N, A, A2, B, B*B, 1).
>
> pythag4(N, A, A2, B, _B2, C) when A+B+C> N -> pythag4(N, A, A2, B+1);
> pythag4(N, A, A2, B, B2, C) when A2 + B2 =:= C*C ->
> [{A, B, C}|pythag4(N, A, A2, B, B2, C+1)];
> pythag4(N, A, A2, B, B2, C) -> pythag4(N, A, A2, B, B2, C+1).
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Willem's implementation in parallel by Hynek
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> wpythag2P(N) ->
> L = [{A, A*A} || A<- lists:seq(1,N)], % For all A's
> lists:flatten(lpmap(fun({A, A2}) -> % For all B's in parallel
> [forAllCsWH(A, B, A + B, A2 + B2, L, N)
> || {B, B2}<- L, A + B< N]
> end, L, 2000, ordered)).
>
> forAllCsWH(A, B, AB, A2B2, L, N) ->
> [{A, B, C} || {C, C2}<- L, A2B2 =:= C2, AB + C =< N].
>
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Morten's implementation.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> pythag5(N) when is_integer(N) ->
> Primes = sieve(N div 2),
> M1M2s = incorporate_primes([{1,1}], N, Primes),
> lists:usort(lists:flatten([ [{A,B,C}, {B,A,C}] || {M1, M2}<- M1M2s,
> M1> M2, A<- [M1-M2], B<- [2*round(math:sqrt(M1*M2))], C<- [M1+M2],
> A+B+C =< N])).
>
> sieve(N) when is_integer(N) ->
> erase(),
> sieve(N,2).
>
> sieve(N, K) when K>= N ->
> [X || X<- lists:seq(2, N), erase(X) == undefined];
> sieve(N, K) ->
> cross_off(K, K, N div K - 1),
> sieve(N, find_next_in_sieve(K + 1)).
>
> cross_off(_K, _Current, 0) ->
> ok;
> cross_off(K, Current, Left) ->
> Next = Current + K,
> put(Next, out),
> cross_off(K, Next, Left - 1).
>
> find_next_in_sieve(K) ->
> case get(K) of
> undefined ->
> K;
> _ ->
> find_next_in_sieve(K+1)
> end.
>
> incorporate_prime(M1M2s, N, P) ->
> lists:flatten([incorporate_prime_single({M1,M2}, N, P)|| {M1, M2}<-
> M1M2s]).
>
> incorporate_prime_single({M1,M2}, N, P) ->
> Evens = [{X, Y} || X<- incorporate_prime_even(M1, N, P), Y<-
> incorporate_prime_even(M2, N, P)],
> Odds = [{X, Y} || X<- incorporate_prime_odd(M1, N, P), Y<-
> incorporate_prime_odd(M2, N, P)],
> Evens ++ Odds.
>
> incorporate_prime_even(M, N, P) ->
> incorporate_prime(M, N, P, []).
>
> incorporate_prime_odd(M, N, P) ->
> incorporate_prime(M * P, N, P, []).
>
> incorporate_prime(M, N, _P, Acc) when M> N/2 ->
> Acc;
> incorporate_prime(M, N, P, Acc) ->
> incorporate_prime(M * P * P, N, P, [M|Acc]).
>
> incorporate_primes(M1M2s, _N, []) ->
> M1M2s;
> incorporate_primes(M1M2s, N, [P|Rest]) ->
> M1M2s_new = incorporate_prime(M1M2s, N, P),
> incorporate_primes(M1M2s_new, N, Rest).
>
>
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %% Richard's improvement.
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
> py3R(N)->
> [{A,B,C} ||
> C<- lists:seq(1, N),
> A<- lists:seq(1, N-C-1),
> B<- lists:seq(1, N-C-A),
> A*A + B*B =:= C*C,
> A+B+C =< N].
>
>
> %%%%%%%%%%%%%%%%%%%%% END
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
>
>
> Cheers,
>
> Ivan.
>
> ----------------------------------------------------------------------
> Do you want to get EVO (ExtendedVisualOtp) to develops client-server
> applicacions using C# / Erlang? Just say it!!!.
>
>
>
> =======================================================================
> Este mensaje ha sido enviado mediante el servicio de correo electrónico
> que ofrece la Federación de Radioaficionados de Cuba a sus miembros para
> respaldar el cumplimiento de los objetivos de la organización y su
> política informativa. La persona que envía este correo asume el
> compromiso de usar el servicio a tales fines y cumplir con las
> regulaciones establecidas.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
More information about the erlang-questions
mailing list