Re: Better sorting using threads?
Re: Better sorting using threads?
- Subject: Re: Better sorting using threads?
- From: Jeffrey Oleander <email@hidden>
- Date: Sun, 14 Mar 2010 12:34:35 -0700 (PDT)
> 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