WWDC22 SALE: Save 50% on all my Swift books and bundles! >>

Why is contains() so much faster with sets than it is with arrays?

Forums > Swift

I know that contains() is faster with a set, and in Day 3 of 100 Days of SwiftUI, this is stated:

In comparison, calling contains() on a set runs so fast you’d struggle to measure it meaningfully. Heck, even if you had a million items in the set, or even 10 million items, it would still run instantly, whereas an array might take minutes or longer to do the same work.

I've tried looking it up, but results are typically just comparisons in speed or listing differences between them.

   

As far as I can gather (but maybe someone can correct me) is when in a Array it loops over every item in the array so the bigger then array the longer it will take. Where a set cannot have the same item in it and it has to be hashable (which is unique for each item) so it does not have to loop over all items.

2      

@NigelGee, you're correct. In the best case, looking up an item in an Array means it's the first element. In the worst case, you have to look at all of them and it's the very last one. So, on average, the time to find a particular element in an Array is on the order of the number of items in the array, or O(n).

Set is usually implemented as a hashmap where the key and the value are the same thing, or where the key is the thing being looked up and the value is some constant, so that the Set is just a view of the map's key set. Looking up the key usually just involves computing the key's hashcode and then some other constant time thing (such as computing an offset in a lookup table, again, depending on the implementation). So, it doesn't matter how many items there are in the set, looking up a particular item takes constant time, or O(1).

In practical terms, there's not a detectable difference given modern hardware until you get into multiple thousands of elements.

1      

Hacking with Swift is sponsored by Emerge

SPONSORED Optimize your app’s startup time, binary size, and overall performance using Emerge’s advanced app optimization and monitoring tools. Reliably measure app size, speed up your app's startup time with Emerge's Launch Booster, and much more. Emerge is actively used by many of the top mobile development teams in the world.

Find out more

Sponsor Hacking with Swift and reach the world's largest Swift community!

Reply to this topic…

You need to create an account or log in to reply.

All interactions here are governed by our code of conduct.

 
Unknown user

You are not logged in

Log in or create account
 

Link copied to your pasteboard.