Re: Fast NSArray compare
Re: Fast NSArray compare
- Subject: Re: Fast NSArray compare
- From: John Brownie <email@hidden>
- Date: Tue, 15 Apr 2014 12:03:07 +1000
Graham Cox wrote:
As a general principle, if you have to check whether one of a list of things is part of another list of things, an array is the wrong container for the job, because it amounts to a worst-case O(n^2) search. Instead, use a set or hash table for the set of things that must be detected among the first list, and it reduces to a worst-case O(n) operation. That said, if the number of items in the second list is small, the performance may be acceptable, and using a hash table might not speed it up noticeably - the time will be dominated by the iteration through the larger list.
I 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.
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