[REBOL] Re: Switch with refinements/hmmm!
From: joel:neely:fedex at: 2-Nov-2001 15:58
Hi, all, ...
Joel Neely wrote:
> Incidentally, I'm working up a set of benchmarks on all of the
> variations discussed in this thread; I'll publish results later
> today.
>
As promised, here are some comparisons. I took a bunch of
different variations as discussed in this thread, made a sub-
version of each one for 2, 3, and 4 refinements, and did some
timings. The text table below gives some key tradeoff points
and reports times. The test harness called each version of
each variation with all possible combinations of refinements,
and did so enough times to get vaguely stable net times.
Since I didn't have time to run the overall test multiple
times and average the results, all numbers should be viewed as
accurate +/- two seconds (or worse).
times vs.
refinements
------------
0? >1? code run mod flex 2 3 4
rs-either y n lin lin m hi m hi 12 26 54
rs-ifelse y n lin lin m hi m hi 13 27 55
rs-anyall1 y n lin lin m hi med 13 27 55
rs-if1 n n lin lin m hi m hi 17 38 80
rs-true n n lin lin v hi v hi 19 41 92
rs-pif n n lin lin v hi v hi 51 109 226
rs-ifelsetree y y exp lin m lo v hi 14 29 63
rs-eithertree y y exp lin m lo v hi 13 29 61
rs-alln n y lin lin v hi med 13 30 72
rs-anyalln y y exp exp m lo med 13 30 72
rs-anyparn y y exp exp med med 14 31 74
rs-anyifn y y exp exp med med 15 35 92
rs-ifn y y lin lin m hi v hi 22 49 109
rs-selwds y y exp exp m lo v lo 24 51 118
rs-combin y y lin lin med m lo 33 75 167
rs-selstr y y exp exp m lo v lo 35 79 178
rs-macro y y lin lin v hi m hi 35 80 180
rs-combo y y lin lin med v lo 66 152 337
rs-selblk y y exp exp m lo v lo 37 134 494
The "0?" column tells whether an approach explicitly handles the
case where no refinements are set.
The ">1?" column tells whether an approach handles more than one
refinement set per call.
The "code" column tells whether the source code for an approach
increases linearly or exponentially with the number of refinements.
The "run" column tells whether the execution time for an approach
increases linearly or exponentially with the number of refinements.
The "mod" column is my subjective impression of how easy the code
was to modify as the number of refinements increased.
The "flex" column is my subjective impression of how flexible the
code would be if different actions needed to be taken for the
various tested cases/combinations.
The timings are in seconds. Note however that increasing the number
of refinements doubles the number of combinations possible. The
benchmark put every routine through all possible combinations; the
following table shows timings normalized to remove that factor.
2 3 4
rs-either 3.00 3.25 3.38
rs-ifelse 3.25 3.38 3.44
rs-anyall1 3.25 3.38 3.44
rs-if1 4.25 4.75 5.00
rs-true 4.75 5.13 5.75
rs-pif 12.75 13.63 14.13
rs-eithertree 3.25 3.63 3.81
rs-ifelsetree 3.50 3.63 3.94
rs-alln 3.25 3.75 4.50
rs-anyalln 3.25 3.75 4.50
rs-anyparn 3.50 3.88 4.63
rs-anyifn 3.75 4.38 5.75
rs-ifn 5.50 6.13 6.81
rs-selwds 6.00 6.38 7.38
rs-combin 8.25 9.38 10.44
rs-selstr 8.75 9.88 11.13
rs-macro 8.75 10.00 11.25
rs-combo 16.50 19.00 21.06
rs-selblk 9.25 16.75 30.88
Descriptions/code for each of the tested alternatives appears below.
The functions were all written to append a string to a global variable
instead of printing (to avoid making the whole benchmark I/O bound).
Only the version with three refinements is shown for each algorithm.
RE-EITHER and RS-IFELSE are conventional if-elseif-elsif-... "ladders"
that take the first successful test, and have an else clause for no
matches. They only differ in the use of EITHER versus IF/ELSE.
rs-either-3: func [/refa /refb /refc][
either refa [
append rs-result "ref A"
][either refb [
append rs-result "ref B"
][either refc [
append rs-result "ref C"
][
append rs-result "NO ref"
]]]
]
rs-ifelse-3: func [/refa /refb /refc][
if/else refa [
append rs-result "ref A"
][if/else refb [
append rs-result "ref B"
][if/else refc [
append rs-result "ref C"
][
append rs-result "NO ref"
]]]
]
RS-ANYALL1 uses the ANY/ALL combination, bailing out after the first
true branch is found, with a default for no true option.
rs-anyall1-3: func [/refa /refb /refc] [
any[
all [refa append rs-result "ref A"]
all [refb append rs-result "ref B"]
all [refc append rs-result "ref C"]
append rs-result "NO ref"
]
]
RS-IF1 uses successive IF tests, exiting as soon as one is selected.
This version doesn't have a default case, but it would be easy to add.
rs-if1-3: func [/refa /refb /refc][
if refa [append rs-result "ref A" exit]
if refb [append rs-result "ref B" exit]
if refc [append rs-result "ref C" exit]
]
RS-TRUE uses the "inside-out-SWITCH" trick to select the first branch
where the associated word has a specified constant value.
rs-true-3: func[/refa /refb /refc][
switch true reduce [ ; needs a value
refa [append rs-result "ref A"]
refb [append rs-result "ref B"]
refc [append rs-result "ref C"]
]
]
RS-PIF uses Ladislav's polymorphic IF construction, with no default.
rs-pif-3: func[/refa /refb /refc][
pif [
refa [append rs-result "ref A"]
refb [append rs-result "ref B"]
refc [append rs-result "ref C"]
]
]
RS-EITHERTREE and RS-IFELSETREE use the most obvious structure -- a
fully-populated binary decision tree.
rs-eithertree-3: func [/refa /refb /refc] [
either refa
[either refb
[either refc
[append rs-result "all refs are set!"]
[append rs-result "ref A & B"]]
[either refc
[append rs-result "ref A & C"]
[append rs-result "ref A"]]]
[either refb
[either refc
[append rs-result "ref B & C"]
[append rs-result "ref B"]]
[either refc
[append rs-result "ref C"]
[append rs-result "NO refs"]]]
]
rs-ifelsetree-3: func [/refa /refb /refc] [
if/else refa
[if/else refb
[if/else refc
[append rs-result "all refs are set!"]
[append rs-result "ref A & B"]]
[if/else refc
[append rs-result "ref A & C"]
[append rs-result "ref A"]]]
[if/else refb
[if/else refc
[append rs-result "ref B & C"]
[append rs-result "ref B"]]
[if/else refc
[append rs-result "ref C"]
[append rs-result "NO refs"]]]
]
RS-ALLN uses a series of ALL clauses to test each refinement in
order, thus handling multiple true branches (but no default).
rs-alln-3: func [/refa /refb /refc][
all [refa append rs-result "ref A"]
all [refb append rs-result "ref B"]
all [refc append rs-result "ref C"]
]
RS-ANYALLN yses the full-blown ANY/ALL to test every possible
combination of refinement values. Note that it is order-sensitive.
rs-anyalln-3: func [/refa /refb /refc] [
any[
all [refa refb refc append rs-result "all refs are set !"]
all [refa refb append rs-result "ref A & B"]
all [refa refc append rs-result "ref A & C"]
all [refb refc append rs-result "ref B & C"]
all [refa append rs-result "ref A"]
all [refb append rs-result "ref B"]
all [refc append rs-result "ref C"]
append rs-result "NO ref"
]
]
RS-ANYPARN uses the "parens-in-an-all" trick to avoid short-circuit
exit of a selected branch.
rs-anyparn-3: func [/refa /refb /refc] [
any[
all [refa refb refc (append rs-result "all refs are set !")]
all [refa refb (append rs-result "ref A & B")]
all [refa refc (append rs-result "ref A & C")]
all [refb refc (append rs-result "ref B & C")]
all [refa (append rs-result "ref A")]
all [refb (append rs-result "ref B")]
all [refc (append rs-result "ref C")]
append rs-result "NO ref"
]
]
RS-ANYIFN uses an ANY to bail out after a branch has been chosen, but
uses IF for the individual branches to avoid the short-circuit exit
issue with ALL. This is a more generic version of RS-ANYPARN.
rs-anyifn-3: func [/refa /refb /refc] [
any[
if all [refa refb refc] [append rs-result "all refs are set !"]
if all [refa refb] [append rs-result "ref A & B"]
if all [refa refc] [append rs-result "ref A & C"]
if all [refb refc] [append rs-result "ref B & C"]
if all [refa] [append rs-result "ref A"]
if all [refb] [append rs-result "ref B"]
if all [refc] [append rs-result "ref C"]
append rs-result "NO ref"
]
]
RS-IFN uses a sequence of IF tests, wrapped in an overall test to
check for no true branches.
rs-ifn-3: func [/refa /refb /refc][
either any [refa refb refc] [
if refa [append rs-result "ref A"]
if refb [append rs-result "ref B"]
if refc [append rs-result "ref C"]
][
append rs-result "NO ref"
]
exit
]
RS-SELWDS creates a "key" block with the values of all refinements,
and uses that to SELECT/ONLY a value to be printed. The last non-
trivial line uses LOAD MOLD/ONLY REDUCE to get words instead of
NONE! or LOGIC! values in the key block.
rs-selwds-3: func [/refa /refb /refc] [
append rs-result select/only [
[none none none] "no refs"
[true none none] "ref A"
[none true none] "ref B"
[true true none] "ref A & B"
[none none true] "ref C"
[true none true] "ref A & C"
[none true true] "ref B & C"
[true true true] "all refs"
] load mold/only reduce [refa refb refc]
]
RS-COMBIN is a hand-optimized version of RS-COMBO. See that version
for a description.
rs-combin-3: func [/refa /refb /refc /local r n limit] [
r: make string! 6 n: 0 limit: 3
if refa [append r " A" n: n + 1]
if refb [append r " B" n: n + 1]
if refc [append r " C" n: n + 1]
append rs-result switch/default n reduce [
0 ["NO refs"]
limit ["all refs are set !"]
][join "ref" r]
]
RS-SELSTR creates a key value (as with RS-SELWDS) but the key is a
string instead of a block.
rs-selstr-3: func [/refa /refb /refc] [
append rs-result select [
"" "no refs"
"a" "ref A"
"b" "ref B"
"ab" "ref A & B"
"c" "ref C"
"ac" "ref A & C"
"bc" "ref B & C"
"abc" "all refs"
] to-string replace/all reduce [
all [refa "a"]
all [refb "b"]
all [refc "c"]
] none ""
]
RS-MACRO uses a special-purpose version of SWITCH to locate and
evaluate the appropriate block of expressions.
.rsmacro: func [block /default if-nothing /local todo] [
todo: clear []
foreach [word then-do] block [
if get word [append todo then-do]
]
if empty? todo [append todo if-nothing]
copy todo
]
rs-macro-3: func [/refa /refb /refc /local todo] [
todo: .rsmacro/default [
refa [append rs-result "is A"]
refb [append rs-result "is B"]
refc [append rs-result "is C"]
] [append rs-result "nothing to do"]
do todo
]
RS-COMBO uses a special-case function to test each refinement in
order, constructing a string with labels for all true cases. It
prints the result, but with special handling for all and none true.
rs-combo-3: func [/refa /refb /refc /local r n limit check] [
r: copy [] n: 0 limit: 3
check: func [opt label] [
if opt [repend r [pick ["&" ""] (n: n + 1) > 1 label]]
]
check refa "A"
check refb "B"
check refc "C"
append rs-result switch/default n reduce [
0 ["NO refs"]
limit ["all refs are set !"]
][join "ref " form r]
]
RS-SELBLK uses multi-layer REDUCEtion to ensure that the key block
and the selector blocks are all constructed with NONE! or LOGIC!
values.
rs-selblk-3: func [/refa /refb /refc] [
append rs-result select/only reduce [
reduce [none none none] "no refs"
reduce [true none none] "ref A"
reduce [none true none] "ref B"
reduce [true true none] "ref A & B"
reduce [none none true] "ref C"
reduce [true none true] "ref A & C"
reduce [none true true] "ref B & C"
reduce [true true true] "all refs"
] reduce [refa refb refc]
]
My thanks to all who contributed ideas. My apologies for not having
enough time to fully credit each idea to the appropriate contributors,
and for any errors I may have made in rendering your ideas.
-jn-
--
This sentence contradicts itself -- no actually it doesn't.
-- Doug Hofstadter
joel<dot>neely<at>fedex<dot>com
