Re: binary search trees & binning
Re: binary search trees & binning
- Subject: Re: binary search trees & binning
- From: Jens Alfke <email@hidden>
- Date: Tue, 15 Apr 2008 14:56:53 -0700
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
Attachment:
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________
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