Time and Space Efficient Multi-Method Dispatching

Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Gerth Brodal

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

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¨ uller 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.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2001-8
Antal sider13
ISBN (Elektronisk)87-7949-010-7
StatusUdgivet - okt. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2001-8
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Time and Space Efficient Multi-Method Dispatching'. Sammen danner de et unikt fingeraftryk.

Citationsformater