Re: [Gzz] OrthoCoordsys???, reverting

[Benja Fallenstein]

Tuomas Lukka wrote:

> > But I'm still not entirely clear about why you think it would be more 
> > efficient that way-- can you explain?
> >    
>
> Quite simple: the asymptotic complexity goes from O(N log N) to O(N).
> Because in the current, recursive model you go through all parents,
> i.e. the whole tree, for each vob you're interpolating. Here the effort
> is constant.

I don't buy into that for two reasons. Firstly, this is not an internal 
tree, but one representing an external structure, so the assumption that 
the tree depth scales as log n is bogus: if I set VanishingView to show 
100 times as many cells, n skyrockets, but the tree depth very likely 
stays precisely the same. So anything between O(N) best case (quite 
usual, actually) and O(N*N) worst case (really unususal: a single 
coordsys containing a single coordsys containing a single...) is 
possible using the recursive approach.

Secondly, and more inportantly, you really only need to decide once what 
coordsys you interpolate another coordsys to. So when you want to 
interpolate s, and you know that p = parent[s] is interpolated to q 
(i.e., interpTo[p] == q), you can simply do a lookup, "which coordsys 
inside q has the same key as s?" Then you get O(N) too, without any 
compromises.

> > > > And b), I don't buy into it being more efficient: it 
> > > > creates one object per coordsys, which is precisely what I'm trying to 
> > > > avoid in AWT. This is a place where I would like to see some serious 
> > > > benchmarks first before changing anything ;-)
> > > >        
> > > Yes, actually I was thinking of storing ints instead of keys for 
> > > efficiency.
> > >      
> > Ok. -- Of course, then you'd have to use a custom hashtable, again.
> >    
>
> Yes, but OTOH the interpolation wouldn't need to use hashCode() but just
> integer comparison.

You mean equals() I guess-- hashtables don't usually use the hashCode() 
of the keys stored in them during lookups, AFAIK (except if you do 
linear hashtables; OrthoCoordsys uses linked list hashtables, with the 
linked lists stored in arrays). Hm, we can expect equals() to be the 
cost of one virtual method call plus a classcast inside that call, I think.

Of course you could generalize your approach here: if this virtual 
method call is too slow, and you don't need perfect results, use a 
hashtable implementation that remembers the hash codes of its keys and 
simply compares those. If both this and normal equals() comparison are 
possible (by using different hashtable implementations), that would be 
fine with me. -- Note that while hashCode()s *should* not clash, in 
practice there will probably be cases where they do (due to bad 
implementations); in your implementation this would lead to drawing 
errors, while in the more usual implementations, it will lead to 
degraded performance... ok, that's something you should be able to 
choose between, too.

I do doubt that using int comparison instead of equals() will make a 
great difference (until I see benchmarks), but I'm not opposed to giving 
the choice.

- Benja