[REBOL] Re: More on expressions
From: joel:neely:fedex at: 7-Feb-2003 17:24
Hi, Carl,
Here are the benchmark results:
Carl Read wrote:
> Well, yours will be the quicker, since it has a min or max
> less in it, but I'd be interested to know what kind of speed
> differences the parens make, so could you do a test of yours
> with them in as well?
>
First a bit of preamble; I took all of the submitted solutions
(with a bit of cleanup, such as fixing the infix/prefix typo and
replacing </> with <=/>= to allow equal values among the args)
and built a testing and benchmarking harness. The benchmarking
is built on the infrastructure I'm building (in my spare time with
my left foot) for the "shootout" effort, so I won't take the time
to explain that here -- documentation will be forthcoming Real Soon
Now -- but the test cases appear below.
Each case has a string label, a "setup" block to do any preliminary
evaluations, and a "final" block that gives the expression whose
value should be the median of the three arguments A B and C .
test-specs: [
"benchmark baseline" [] [0]
"second sort" [] [second sort reduce [a b c]]
"pick max remove max" [] [
pick maximum-of head remove maximum-of reduce [a b c] 1
]
"any all (explicit)" [] [
any [
all [a <= b b <= c b] all [b <= c c <= a c]
all [c <= a a <= b a] all [c <= b b <= a b]
all [b <= a a <= c a] all [a <= c c <= b c]
]
]
"any all (w/ default)" [] [
any [
all [a >= b a <= c a] all [a >= c a <= b a]
all [b >= a b <= c b] all [b >= c b <= a b]
c
]
]
"sum less extremes" [] [
a + b + c - (min a min b c) - max a max b c
]
"max of remove max" [
dummy: head remove maximum-of reduce [a b c]
][
max dummy/1 dummy/2
]
"int form remove extremes" [] [
to integer! form head remove minimum-of
head remove maximum-of reduce [a b c]
]
"any xor with default" [] [
any [
all [(a > b) xor (a > c) a]
all [(a > c) xor (b > c) c]
b
]
]
"unwrapped sort with sets" [
set [a b] reduce [min a b max a b]
set [b c] reduce [min b c max b c]
set [a b] reduce [min a b max a b]
][
b
]
"sums less twice max" [] [
(max a b) + (max b c) + (max a c) - (2 * (max a max b c))
]
"max of mins" [] [max max min a b min b c min a c]
"sort network (parens)" [] [max (min a b) (min (max a b) c)]
"sort network" [] [max min a b min max a b c]
]
The only one missing is the "bogosort" approach, which is way slow
compared to everything else (about 13 times the time needed for
the fastest solution).
The above block was first submitted to a testing harness to verify
that all expressions yielded the correct results for a comprehensive
set of test data; here's that output:
[1 1 1] [1 1 1] 1
[1 1 2] [1 1 2] 1
[1 1 3] [1 1 3] 1
[1 2 1] [1 1 2] 1
[1 2 2] [1 2 2] 2
[1 2 3] [1 2 3] 2
[1 3 1] [1 1 3] 1
[1 3 2] [1 2 3] 2
[1 3 3] [1 3 3] 3
[2 1 1] [1 1 2] 1
[2 1 2] [1 2 2] 2
[2 1 3] [1 2 3] 2
[2 2 1] [1 2 2] 2
[2 2 2] [2 2 2] 2
[2 2 3] [2 2 3] 2
[2 3 1] [1 2 3] 2
[2 3 2] [2 2 3] 2
[2 3 3] [2 3 3] 3
[3 1 1] [1 1 3] 1
[3 1 2] [1 2 3] 2
[3 1 3] [1 3 3] 3
[3 2 1] [1 2 3] 2
[3 2 2] [2 2 3] 2
[3 2 3] [2 3 3] 3
[3 3 1] [1 3 3] 3
[3 3 2] [2 3 3] 3
[3 3 3] [3 3 3] 3
0 errors in second sort
0 errors in pick max remove max
0 errors in any all (explicit)
0 errors in any all (w/ default)
0 errors in sum less extremes
0 errors in max of remove max
0 errors in int form remove extremes
0 errors in any xor with default
0 errors in unwrapped sort with sets
0 errors in sums less twice max
0 errors in max of mins
0 errors in sort network (parens)
0 errors in sort network
Then the various cases were benchmarked competitively. I used a
baseline of evaluating a literal zero as a result; the benchmark
engine subtracts out the timings for the baseline, and then gives
ratios between all the "real" cases relative to the smallest one.
With a bit of formatting (percentages and labels), we get these
comparative results, fastest to slowest:
100 sort network
122.4 max of mins
122.4 sort network (parens)
167.7 any xor with default
175.5 sum less extremes
191.6 any all (w/ default)
219 sums less twice max
219.5 pick max remove max
245.3 any all (explicit)
250.8 second sort
264.2 max of remove max
338.1 int form remove extremes
549.6 unwrapped sort with sets
Interestingly enough, adding the parens to the "sort network"
expression adds 20%-25% to the running time, which is essentially
the same cost as the extra min or max of the next alternative.
Thanks to all who participated!
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
