Re: Better sorting using threads?
Re: Better sorting using threads?
- Subject: Re: Better sorting using threads?
- From: Ken Ferry <email@hidden>
- Date: Mon, 15 Mar 2010 13:20:40 -0700
On Mon, Mar 15, 2010 at 1:11 PM, Andrew James <email@hidden>wrote:
> Thanks for everyone's feedback. I'm always very happy to have ignorance
> on my part removed!
>
> As far as interface is concerned yes I completely respect the fact that
> it's there to hide details and help us focus on behavior not
> implementation. And yes I'm sort of kicking myself for not realizing an
> array is really just some thing that lets you index into it with a number.
> Doh!
>
> That being said, once containers get large, understanding the Big O
> notation for operations can become important factors in choosing one
> implementation over another. One of the things I do like about STL ( don't
> want to digress too far in this direction ) is that documentation provides
> gaurantees about Big O notation.
>
> Do this type of gaurantee exist anywhere in Cocoa's containers?
>
Yes, but you probably won't like the guarantees, since they're pretty
conservative. See CFArray.h, CFDictionary.h.
There are no guarantees for "NSArray" or "NSDictionary" because they can
have arbitrary subclasses. However, in standard cases you'll be getting the
same behavior as with the un-subclassable CFArray and CFDictionary.
-Ken
>
> --aj
>
> ------------------------------
> *From:* Jeffrey Oleander <email@hidden>
> *To:* Gwynne Raskind <email@hidden>; Ken Ferry <
> email@hidden>; Andrew James <email@hidden>
>
> *Cc:* Cocoa-Dev List <email@hidden>
> *Sent:* Sun, March 14, 2010 12:34:35 PM
>
> *Subject:* Re: Better sorting using threads?
>
> > On Fri, 2010/03/12, Andrew James <email@hidden> wrote:
> > From: Andrew James <email@hidden>
> > Subject: Re: Better sorting using threads?
> > To: "Gwynne Raskind" <email@hidden>, "Ken Ferry" <
> email@hidden>
> > Cc: "Cocoa-Dev List" <email@hidden>
> > 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 <email@hidden>
> >> To: Ken Ferry <email@hidden>
> >> Cc: Cocoa-Dev List <email@hidden>
> >> 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 (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