Averages/Median: Difference between revisions
Content added Content deleted
(added ReScript) |
|||
Line 1,271: | Line 1,271: | ||
-import(lists, [nth/2, sort/1]). |
-import(lists, [nth/2, sort/1]). |
||
-compile(export_all). |
-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) -> |
median(Unsorted) -> |
||
Line 1,277: | Line 1,292: | ||
Mid = Length div 2, |
Mid = Length div 2, |
||
Rem = Length rem 2, |
Rem = Length rem 2, |
||
(nth(Mid+Rem, Sorted) + nth(Mid+1, Sorted)) / 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}}== |
=={{header|ERRE}}== |