Re: binary search trees & binning
Re: binary search trees & binning
- Subject: Re: binary search trees & binning
- From: John Stiles <email@hidden>
- Date: Tue, 15 Apr 2008 15:07:48 -0700
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.
Jens Alfke wrote:
I need to place many thousands of doubles into size-class groups
whose boundaries can be explicitly specified (much like one would do
in constructing a histogram, though that's not what I'm doing). The
number of size-classes won't be great, usually fewer than 100, say.
It occurred to me that using a binary search tree would be a
reasonably simple approach
If you had millions of doubles, or even hundreds of thousands, I'd
agree. But the time required to toss a few thousand numbers into
buckets is likely to be unnoticeably short on today's hardware. Why
not implement it in the simplest possible way first, minimizing
implementation time instead of runtime, and then benchmark it and see
how it does?
In other words, I'd probably first try using a C array of 100
NSMutableArrays, and wrap the doubles in NSNumbers. On every insert
you can do a simple binary search to figure out which of the 100
buckets it should go in.
If that's too slow because of the overhead of allocating all those
NSNumber objects, I'd switch to using C arrays of double[ ] instead,
growing them in chunks using realloc.
—Jens
------------------------------------------------------------------------
_______________________________________________
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
_______________________________________________
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