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, john_brow...@sil.org or j.brow...@sil.org.pg 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 (Cocoa-dev@lists.apple.com) 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: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
