Re: Better sorting using threads?
Re: Better sorting using threads?
- Subject: Re: Better sorting using threads?
- From: Andrew James <email@hidden>
- Date: Fri, 12 Mar 2010 11:55:03 -0800 (PST)
All,
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
________________________________
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:]. That's two
> lines instead of one to add an object to an array, which is not bad.
>
> That method is new in 10.6, but something similar has been in CoreFoundation
> for a while. CFArrayBSearchValues is usable on NSArray since CFArray is
> bridged.
>
> You can also look at -[NSArray sortedArrayHint]. The deal there is that you
> extract an opaque "hint" from a sorted array, change the array, and resort
> passing in the hint. This is optimized for the case when the array is still
> mostly sorted, but with some things out of place.
I maintain a simple sorted array by rerunning -sortUsingFunction:context: for every insert (or set of inserts, since the vast majority of inserts into the array are groups of objects together). So far I haven't had any speed issues with it at all. But my case is pretty simple; it's a small array of around 100 objects, and the sort function is trivial (object.integerProperty comparison).
-- Gwynne
_______________________________________________
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
_______________________________________________
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