Figure: A Multiway Radix Search Tree
Úlfar Erlingsson, Mukkai Krishnamoorthy and T.V. Raman.
Lucid and Efficient Case Analysis. Technical Report 95-14,
Department of Computer Science, Rensselaer Polytechnic Institute,
Troy, NY, 1995.
(compressed
PostScript)
This paper describes a new scheme for building static search trees, using multiway radix search trees. We present this method for code generation of switch statements in imperative languages. We show that, for sparse case sets, the method produces faster code on average than existing methods, requiring O(1) time with a small constant for the average search. We then apply this method to the problem of code generation for generic functions in object-oriented languages, and find that its use improves clarity as well as efficiency.