Let's look at this issue a little more formally. A nested if-then-else
construct of the form
if test1 then . . .
else if test2 then . . .
else if test3 then . . .
. . .
else if testn then . . .
else ;
has a binary decision tree (BDT) of the form
1--->s[uccess]
|
2--->s
|
3--->s
|
.
.
.
|
n--->s
|
f[ailure]
The external path length of this BDT, the number of tests performed under
the usual Bayesian assumptions, i.e., when each of the paths through it is
traversed once, is just
E(n) = (1 + 2 + 3 + . . . + n) + n = n(n + 1)/2 + n = n(n + 3)/2.
This polynomial-time scheme thus has disagreeable performance for even
moderately large n: for, for example, n = 10 we already have E(10) = 65.
Branch-table schemes are not so well standardized, but the select (PL/I) or
switch (C) programming figures are tractable in a standard way. Consider
the PL/I variant
declare c1 character(1) ;
. . .
select(c1) ;
when('a') . . . ;
when('b', 'c', 'd') . . . ;
when('x') . . . ;
when('n') . . . ;
otherwise . . . ;
end ;
It is sometimes implemented [very] badly, but it can be implemented using a
TR instruction and 256-byte table in such a way that
'a' ==> 00000001b = 1
'b', 'c', 'd' ==> 00000010b = 2
'x' ==> 00000011b = 3
'n' ==> 00000100b = 4
and all other single-character/byte values are translated to 00000000b = 0.
Translated values can then be multiplied/shifted appropriately to yield
multiples of 4 [or 8] for use in a classical branch table. Moreover, the
same code can be reused [with different TR and branch tables] in all such
situations.
This second scheme has excellent, flat performance which is independent of n
and any oirdering of tests for n < 2^8 + 1 = 257 (or for n < 2^16 + 1 =
65537 if a TROO instructrion and a larger table are used).
There is thus little excuse for the use of thickets of nested if-then-elses.
Here, as elsewhere, an explicit, reusable table-driven scheme is better
than an ad hoc procedural one.
John Gilmore
Ashland, MA 01721-1817
USA
_________________________________________________________________
Fixing up the home? Live Search can help
http://imagine-windowslive.com/search/kits/default.aspx?kit=improve&locale=en-US&source=hmemailtaglinenov06&FORM=WLMTAG
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to [EMAIL PROTECTED] with the message: GET IBM-MAIN INFO
Search the archives at http://bama.ua.edu/archives/ibm-main.html
