Re: [Gzz] OrthoCoordsys???, reverting

[Tuomas Lukka]

On Sat, Aug 24, 2002 at 11:07:30PM +0200, Benja Fallenstein wrote:
> 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.

Yes, true. However, I actually expect that we'll in reality see
the tree depths of log N, since currently they are flattened by the fact
that the tree functionality is new.

> 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.

Oh, if this being done by the current code?

However, looking at a single integer still causes less memory references ;)

> >>>>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.

but it uses the hashCode() of the key. Now all keys would just be integers.

> 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.

ApproximateHashTable... sounds fun ;)

But that doesn't work: you need to use the ints because instead of putting
the key, you put a combination of the key's hashcode and its parent's integer.

> 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.

That could well be.

Oh, but one efficiency thing is that you don't actually need to *store* the
parentage anywhere...

        Tuomas