> On Fri, 2010/03/12, Andrew James <andrew_a_ja...@yahoo.com> wrote: > From: Andrew James <andrew_a_ja...@yahoo.com> > Subject: Re: Better sorting using threads? > To: "Gwynne Raskind" <gwy...@darkrainfall.org>, "Ken Ferry" > <kenfe...@gmail.com> > Cc: "Cocoa-Dev List" <cocoa-dev@lists.apple.com> > Date: Friday, 2010 March 12, 13:55 > My concern is that keeping traditional C-arrays > in sorted order means > > 1) finding the location for insert ( O(n) ) > 2) copying a range of contiguous memory to make the > location available > 3) copying in new value > > I've made the assumption that NSArray wraps an > old school contiguous C-style array > ( ala C++ std:::vector ) > > With many sorted container insertion inserting > in sorted order means > 1) finding the location for inserter ( O(nlogn) ) > or the like > 2) create node with new value > 3) swizzle some pointers to include new values > > .. ( ala C++ std::set ) > > I have a hard time seeing how this is more expensive > for very large container than sorting an array when > needed. The initial poster was indicating he has > a container with thousands of members. > > Please educate me where my post illustrates ignorance. > > Cheers, > --aj
Well, encapsulation requires a certain amount of enforced ignorance. We're not supposed to know exactly how it does it. We're only supposed to know the public interface and let it do its thing as it wishes to do it, even changing when the maintainers of the class decide to make changes. I may be implemented as a Fibonacci heap, or a binary tree for all we know, using a contiguous block of memory or nodes allocated one at a time. There are hints in the interface provided, but no promises beyond it regarding implementation. >> ________________________________ >> From: Gwynne Raskind <gwy...@darkrainfall.org> >> To: Ken Ferry <kenfe...@gmail.com> >> Cc: Cocoa-Dev List <cocoa-dev@lists.apple.com> >> Sent: Fri, March 12, 2010 9:14:35 AM >> Subject: Re: Better sorting using threads? >>> On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: >>> Does Cocoa have sorted containers so that an >>> object can be inserted in >>> sorted order? If so it seems like this would be far >>> less expensive. >> >> Probably the best thing to do if you want this is to >> maintain the sort >> yourself by inserting new objects in the correct >> position. You can find the >> position using >> -[NSArray >> indexOfObject:inSortedRange:options:usingComparator:] >> ... _______________________________________________ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
