(Really) Tight bounds for dispatching binary methods

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

submitted

Scientific paper

We consider binary dispatching problem originating from object oriented programming. We want to preprocess a hierarchy of classes and collection of methods so that given a function call in the run-time we are able to retrieve the most specialized implementation which can be invoked with the actual types of the arguments. For the binary dispatching, where the methods take exactly two arguments, logarithmic query time is possible, even if the structure is allowed to take linear space. Unfortunately, known solutions achieving such complexity require superlinear time for constructing the structure. Using a different idea we are able to construct in (deterministic) linear time and space a structure allowing dispatching binary methods in the same logarithmic time. Then we show how to improve the query time to slightly sublogarithmic, which is easily seen to be optimal as a consequence of some already known lower bounds if we want to keep the size of the resulting structure close to linear.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

(Really) Tight bounds for dispatching binary methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with (Really) Tight bounds for dispatching binary methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (Really) Tight bounds for dispatching binary methods will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-291468

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.