UPGRADE YOUR SKILLS: Learn advanced Swift and SwiftUI on Hacking with Swift+! >>

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.

2      

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.

4      

@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.

4      

TAKE YOUR SKILLS TO THE NEXT LEVEL If you like Hacking with Swift, you'll love Hacking with Swift+ – it's my premium service where you can learn advanced Swift and SwiftUI, functional programming, algorithms, and more. Plus it comes with stacks of benefits, including monthly live streams, downloadable projects, a 20% discount on all books, and free gifts!

Find out more

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

Archived topic

This topic has been closed due to inactivity, so you can't reply. Please create a new topic if you need to.

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.