Array vs Dictionary search performance in Swift

Question

I think it's probably a simple answer but I thought I'd quickly check...

Let's say I'm adding Ints to an array at various points in my code, and then I want to find if an array contains a certain Int in the future..

var array = [Int]()

array.append(2)
array.append(4)
array.append(5)
array.append(7)

if array.contains(7) { print("There's a 7 alright") } 

Is this heavier performance wise than if I created a dictionary?

var dictionary = [Int:Int]()

dictionary[7] = 7

if dictionary[7] != nil { print("There's a value for key 7")}

Obviously there's reasons like, you might want to eliminate the possibility of having duplicate entries of the same number... but I could also do that with a Set.. I'm mainly just wondering about the performance of dictionary[key] vs array.contains(value)

Thanks for your time

Answer 1

Generally speaking, Dictionaries provide constant, i.e. O(1), access, which means searching if a value exists and updating it are faster than with an Array, which, depending on implementation can be O(n). If those are things that you need to optimize for, then a Dictionary is a good choice. However, since dictionaries enforce uniqueness of keys, you cannot insert multiple values under the same key.

Based on the question, I would recommend for you to read Ray Wenderlich's Collection Data Structures to get a more holistic understanding of data structures than I can provide here.

Answer 2

I did some sampling!

I edited your code so that the print statements are empty.

I ran the code 1.000.000 times. Every time I measured how long it takes to access the dictionary and array separately. Then I subtracted the dictTime for arrTime (arrTime - dictTime) and saved this number each time.

Once it finished I took the average of the results.

The result is: 23150. Meaning that over 1.000.000 tries the array was faster to access by 23150 nanoSec. The max difference was 2426737 and the min was -5711121.

Here are the results on a graph: