[prev in list] [next in list] [prev in thread] [next in thread] 

List:       koffice-devel
Subject:    Re: KSpread: Style Storage
From:       Stefan Nikolaus <stefan.nikolaus () kdemail ! net>
Date:       2006-06-23 8:35:06
Message-ID: 200606231035.08922.stefan.nikolaus () kdemail ! net
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


On Thursday 22 June 2006 20:32, Robert Knight wrote:
> But what benefits does this have over a Quad-Tree?  Unless there are
> notable performance or memory usage benefits then it would seem
> sensible to pick the simpler solution (the Quad-Tree) which requires
> less code and will be easier for other devs to understand and tweak.

Agreed, even if I consider this 'quad-tree here, hash there, binary tree 
(still?) there' not as easily understandable. The solution with the best 
performance should be chosen and this is your quad-tree - at least at the 
moment. ;-) 

Using an integer tree massif charts (I don't know, where the exact numbers 
are) tell me:
Quad-Tree: ~9 MB
(Ko)R-Tree: ~ 10 MB
R+-Tree: ~20 MB (*cough* smells like leakage)

The R+-Tree _should_ (if you implement it correctly ;-) ) perform better as 
R-Trees for the case of lookups, because you have non-overlapping 'super 
rects'. Those are equivalent to some extend to your fixed quadrants. In 
R-Trees. You have to iterate over all 'super rects' to find a 'data rect', 
while in R+-Trees you can stop, if you've found one that contains the 
searched position.

AFAICS, R-Trees, in general, should be more flexible: They have no problems 
with large regions, while quadrant overlaps seem to be an issue in 
Quad-Trees. And they should occupy less memomy with widely scattered regions, 
i.e. rects on the upper left and on the bottom right of the whole sheet. But 
the latter would be quite uncommon.

Bye,
Stefan

[Attachment #5 (application/pgp-signature)]

_______________________________________________
koffice-devel mailing list
koffice-devel@kde.org
https://mail.kde.org/mailman/listinfo/koffice-devel


[prev in list] [next in list] [prev in thread] [next in thread]