Re: binary search trees & binning
Re: binary search trees & binning
- Subject: Re: binary search trees & binning
- From: John Stiles <email@hidden>
- Date: Wed, 16 Apr 2008 10:20:49 -0700
Jean-Daniel Dupas wrote:
Le 16 avr. 08 à 00:07, John Stiles a écrit :
Hmm, set<double> sounds a lot easier than this to me.
Just use insert to put all the doubles into the set (one line), then
use lower_bound to find the delineations between each group (another
one-liner, though of course you'll need to loop over the number of
groups you want). Then the distance between iterators is the size of
each group (std::distance can compute this in another one-liner).
Unfortunately this is another case where Cocoa's collection classes
just aren't very strong, but STL is made for this sort of work...
though Jens is probably right that performance isn't going to be a
big problem if it's <10000 items. The set<> will be a whole lot
faster, but any naive implementation will be "fast enough" unless you
expect your data set will eventually be a lot larger than this.
Do not make assumptions on "CFArray vs STL vectors" performances,
especially for big arrays.
CFArray has some optimizations that made it really fast for some
usages. (http://ridiculousfish.com/blog/archives/2005/12/23/array/).
That's not how I read this article. Rather, when I look at CFArray
versus the STL, it looks like CFArray does better than STL for
worst-case operations (removing the first entry of an array?) but does
much worse for typical- and best-case operations (accessing an item by
index, insertion and removal at the end, etc).
The difference is, in STL, if you want an array where you can remove
from the beginning, you would never use vector<> anyway. You'd use
deque<>, which has different tradeoffs and allows fast removal of
elements from the beginning of the array. CoreFoundation doesn't let you
choose and instead it just changes which algorithms it uses as the size
of the array grows past a certain point, which to me is just weird. It
doesn't seem like a great design to me. If you wanted to say one good
thing about it, though... CFArray may never give you the best
performance, but it will probably also prevent you from getting
worst-case performance if you write really poorly-designed algorithms.
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden