[Zope3-dev] N-Tuple Adapters

[Phillip J. Eby]

At 09:42 AM 6/3/03 -0400, Shane Hathaway wrote:
>BTW I got my answer to the original questions from one of Steve's links: 
>to speed up multiple dispatch, you use a decision tree.  Then speed 
>becomes a matter of building efficient trees.  It seems like it could be 
>complex but very fast.

Actually, building efficient trees for such things is either NP-hard or 
NP-complete, I forget which.  If you browse Citeseer for topics related to 
multiple and predicate dispatching, there are some papers that purport to 
prove how hard it is to build a perfect dispatch decision tree.  (I say 
purport because I can't follow the math, myself.)

OTOH, there are a few papers that claim to have good practical performance, 
like the Ernst and Chambers papers on predicate dispatching for the Cecil 
language.  Be warned, however, that the algorithms are *really* complex, 
and they are mostly designed for static typing scenarios.  In other words, 
they assume the compiler has information available about all predicates and 
consequents at tree building time.  To date, I haven't seen any algorithms 
oriented towards incremental tree building.