Anonymous user
Averages/Median: Difference between revisions
→{{header|Erlang}}
(added ReScript) |
|||
Line 1,271:
-import(lists, [nth/2, sort/1]).
-compile(export_all).
test(MaxInt,ListSize,TimesToRun) ->
test(MaxInt,ListSize,TimesToRun,[[],[]]).
test(_,_,0,[GMAcc, OMAcc]) ->
Len = length(GMAcc),
{GMT,GMV} = lists:foldl(fun({T, V}, {AT,AV}) -> {AT + T, AV + V} end, {0,0}, GMAcc),
{OMT,OMV} = lists:foldl(fun({T, V}, {AT,AV}) -> {AT + T, AV + V} end, {0,0}, OMAcc),
io:format("QuickSelect Time: ~p, Val: ~p~nOriginal Time: ~p, Val: ~p~n", [GMT/Len, GMV/Len, OMT/Len, OMV/Len]);
test(M,N,T,[GMAcc, OMAcc]) ->
L = [rand:uniform(M) || _ <- lists:seq(1,N)],
GM = timer:tc(fun() -> qs_median(L) end),
OM = timer:tc(fun() -> median(L) end),
test(M,N,T-1,[[GM|GMAcc], [OM|OMAcc]]).
median(Unsorted) ->
Line 1,277 ⟶ 1,292:
Mid = Length div 2,
Rem = Length rem 2,
(nth(Mid+Rem, Sorted) + nth(Mid+1, Sorted)) / 2.
% ***********************************************************
% median based on quick select with optimizations for repeating numbers
% if it really matters it's a little faster
% by Roman Rabinovich
% ***********************************************************
qs_median([]) -> error;
qs_median([P|List]) ->
TargetPos = length(List)/2 + 0.5,
qs_median(List, TargetPos, P, undefined).
qs_median([X], _, _, _) -> X;
qs_median([X,Y], 1.5, _, _) -> (X+Y)/2;
qs_median([P|Tail], TargetPos, P, up) when TargetPos /= 1 ->
qs_median(Tail, TargetPos - 1, P, up);
qs_median([P|Tail], TargetPos, P, {down, Len}) when Len /= TargetPos ->
qs_median(Tail, TargetPos, P, {down, Len-1});
qs_median([P|Tail], TargetPos, _, _) ->
Smaller = [X || X <- Tail, X < P],
LS = length(Smaller),
case (LS + 1) == TargetPos of
true -> P;
false ->
case (LS + 1.5) == TargetPos of
true ->
Larger = [X || X <- Tail, X >= P],
(P + qs_median(Larger, 1, P, up))/2;
false ->
case (LS + 0.5) == TargetPos of
true -> (P + qs_median(Smaller,TargetPos - 0.5, P,{down, LS}))/2;
false ->
case LS + 1 > TargetPos of
true -> qs_median(Smaller,TargetPos, P, {down, LS});
false ->
Larger = [X || X <- Tail, X >= P],
qs_median(Larger, TargetPos - LS - 1, P, up)
end
end
end
end.
</lang>
=={{header|ERRE}}==
| |||