Re: Fast NSArray compare
Re: Fast NSArray compare
- Subject: Re: Fast NSArray compare
- From: Graham Cox <email@hidden>
- Date: Tue, 15 Apr 2014 12:41:50 +1000
On 15 Apr 2014, at 12:03 pm, John Brownie <email@hidden> wrote:
> think you're an order of magnitude out. Searching an array is linear with the length of the array, O(n), whereas a set or hash should be close to constant, O(1), if there's not a big collision in the hashes. But the principle is correct, that you don't want to be searching arrays. Of course, if it's a sorted array, you can do it in O(log n) by binary searching.
Right, but you're also iterating the first list, which is O(n), so for each item you have to linear search a second list, O(n) again, so it's O(n) x O(n), or O(n^2). If the second "list" is just a hash or set, that's O(1), so overall it's O(n) x O(1) or O(n). That is, I was discussing the overall performance, not just the lookup for membership.
--Graham
_______________________________________________
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