Re: binary search trees & binning

FROM : John Stiles
DATE : Wed Apr 16 19:20:49 2008

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.