Abstract | ||
---|---|---|
The dispatching problem for object oriented languages is the problem of determining the most specialized method to invoke for calls at run-time. This can be a critical component of execution performance. A number of recent results, including [Muthukrishnan and M眉ller SODA'96, Ferragina and Muthukrishnan ESA'96, Alstrup et al. FOCS'98], have studied this problem and in particular provided various efficient data structures for the mono-method dispatching problem. A recent paper of Ferragina, Muthukrishnan and de Berg [STOC'99] addresses the multi-method dispatching problem.Our main result is a linear space data structure for binary dispatching that supports dispatching in logarithmic time. Using the same query time as Ferragina et al., this result improves the space bound with a logarithmic factor. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/3-540-45471-3_3 | SWAT |
Keywords | Field | DocType |
main result,logarithmic time,critical component,various efficient data structure,logarithmic factor,muthukrishnan esa,recent paper,linear space data structure,query time,recent result,space efficient multi-method dispatching,data structure,object oriented language,linear space | Space time,Data structure,Sparse array,Object-oriented programming,Computer science,Linear space,Algorithm,Binary data,Logarithm,Binary number | Conference |
Volume | ISSN | ISBN |
2368 | 0302-9743 | 3-540-43866-1 |
Citations | PageRank | References |
3 | 0.39 | 19 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stephen Alstrup | 1 | 657 | 42.60 |
Gerth Stølting Brodal | 2 | 1399 | 86.30 |
Inge Li Gørtz | 3 | 128 | 20.94 |
Theis Rauhe | 4 | 661 | 35.11 |