Re: red black trees
Re: red black trees
- Subject: Re: red black trees
- From: John Stiles <email@hidden>
- Date: Wed, 18 Feb 2004 20:56:49 -0800
On Feb 18, 2004, at 8:22 PM, Brian Reardon wrote:
So what is driving your desire to have a tree vs an ordered array?
I am trying to implement Preparata and Shamos's convex hull point set
search algorithm (Computational Geometry, Springer-Verlag, 1985,
section 4.1.3, pages 157-166) which is O(NlogN) for 2 dimensional data
sets and O(N(logN)^(d-2)) for d >=3. However, this result is
dependent on the implementation of a red-black tree and my
understanding of the algorithm (perhaps I am wrong) is that if you
only use a sorted array then the algorithm is O(N^2). I am making
this assumption based on p. 160 which goes into detail as to the
importance of using an ordered, balanced tree in this algorithm.
If you are really worried about performance, maybe you should implement
your own red-black tree (certainly you'll be able to find freebie
source on the web) or use the STL, which has an additional benefit--you
won't be required to bundle up each entry inside an NSObject.
I use NS collections when I need to interface with Cocoa, but I
wouldn't use them to implement heavyweight algorithms. Certainly
there's nothing wrong with it, but Objective-C message passing and
NSObjects in general add extra baggage that you don't necessarily need
if you're just dealing with huge sets of floating point numbers or
something. Yes, the overhead is not huge, and for general-purpose code,
you can usually find bigger and better things to optimize, but your the
whole algorithm is relying on objc_msgSend for every set insertion,
deletion and lookup, certainly that's going to take a non-zero toll on
overall performance.
The blessing with Cocoa is that Objective-C++ lets you use STL so
seamlessly; just write STL code like always, and rename your file from
".m" to ".mm".
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.