On Tue Apr 15 2014 12:41:50 GMT+1000 (PGT) Graham Cox wrote:
On 15 Apr 2014, at 12:03 pm, John Brownie <john_brow...@sil.org> 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, 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

Reply via email to