• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag
 

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: Fast NSArray compare
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


  • Follow-Ups:
    • Re: Fast NSArray compare
      • From: Graham Cox <email@hidden>
References: 
 >Fast NSArray compare (From: Varun Chandramohan <email@hidden>)
 >Re: Fast NSArray compare (From: Graham Cox <email@hidden>)

  • Prev by Date: Re: Fast NSArray compare
  • Next by Date: Re: Fast NSArray compare
  • Previous by thread: Re: Fast NSArray compare
  • Next by thread: Re: Fast NSArray compare
  • Index(es):
    • Date
    • Thread