Sets:
Sets are unordered collection of unique values that share many Big-O characteristics & overall functionality with array based data structures. However, there are some key differences that are worth exploring and to better help illustrate differences between the two data structures as it relates to Big-O notation.
Because sets do not allow duplicate values, inserting elements into a set first requires that all elements are searched to determine the inserted element is unique to the set. So unlike an array, even appending a new value into a set still requires N + 1 steps. And inserting a value at the beginning of the set would require 2N + 1 steps. The reason for the 2N + 1 operation is because 1) the set has to search N values to ensure that it’s not a duplicate value, 2) N steps to shift all the values, and finally O(1) step to insert the value.
There’s a lot to sets, but some of the most basic set operations allow you to combine sets together that eleminates the need for using For loops to test / combine values among different arrays. Just a few examples in Swift, there are the ‘intersection’ & ‘union’ methods as just two examples. The ‘intersection’ method creates a new set with values only common in both sets. Conversely, the ’symmetricDifference’ method returns a set of values that is not in both collection data structures.
The Project:
The previous branch of the project returned data from the JSON file in an array, but now using a set we have greatly reduced the memory requirements of the program & improving performance with reduced N elements. Using the count property for both the array & set data structures return vastly different results. It was ‘48526’ for the array, but only ‘2557’ for the set.