gzz-dev
[Top][All Lists]

## Re: [Gzz] OrthoCoordsys???, reverting

 From: Benja Fallenstein Subject: Re: [Gzz] OrthoCoordsys???, reverting Date: Sat, 24 Aug 2002 23:07:30 +0200 User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.0.0) Gecko/20020615 Debian/1.0.0-3

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

```