Re: Fast NSArray compare
Re: Fast NSArray compare
- Subject: Re: Fast NSArray compare
- From: John Brownie <email@hidden>
- Date: Tue, 15 Apr 2014 20:25:48 +1000
On Tue Apr 15 2014 12:41:50 GMT+1000 (PGT) Graham Cox wrote:
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.
OK, I see your point. With two different lists, assuming the fixed list
(n entries) is much smaller than the total list (m entries), you end up
with O(mn), O(m), or O(m log n), which probably ends up as O(m) in the
end, but the size of the multiplier will still bite.
John
--
John Brownie, email@hidden or email@hidden
Summer Institute of Linguistics | Mussau-Emira language, Mussau Is.
Ukarumpa, Eastern Highlands Province | New Ireland Province
Papua New Guinea | Papua New Guinea
_______________________________________________
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