CMU 15-110: Principles of Computing
Sets

1. Motivating Example
2. Creating Sets
3. Properties of Sets
   1. Sets are Unordered
   2. Elements are Unique
   3. Elements Must Be Immutable
   4. Sets are Very Efficient
4. Set Operations
5. Example: Comparing Two Large Lists

1. Motivating Example
   A key idea behind sets is that the in operator is very, very fast for sets compared to lists. For example:
   import time def timeToFindEachValue(L, n): # Return the time it takes to check for each value from 0 to n # whether that value is in L. # The 'in' operator is much, much faster for sets than lists. startTime = time.time() for value in range(n): if (value in L): pass endTime = time.time() return endTime - startTime n = 10**4 L = list(range(0, n, 2)) # evens up to n print(timeToFindEachValue(L, n)) S = set(L) print(timeToFindEachValue(S, n))


2. Creating Sets
   
   • Create an empty set
     s = set() print(s) # prints set()
   
   
   • Create a set from a list
     L = ['cat', 'cow', 'dog'] s = set(L) print(s) # prints {'cow', 'dog', 'cat'}


3. Properties of Sets
   1. Sets are Unordered
      
      s = set([2, 4, 8]) print(s) # prints {8, 2, 4} in standard Python (though not in brython) for value in s: # prints 8, 2, 4 print(value)
   
   
   2. Elements are Unique
      
      s = set([2,2,2]) print(s) # prints {2} print(len(s)) # prints 1
   
   
   3. Elements Must Be Immutable
      
      s = set() s.add(12345) # fine, since numbers are immutable s.add('wow') # fine, since strings are immutable s.add([1,2]) # fails: unhashable type: 'list' (since lists are mutable)
   
   
   4. Sets are Very Efficient
      We saw this in the example above.


4. Set Operations
   
   
   
   1. Operations on a set
      
      

      Operation	Result
      len(s)	the number of elements in s
      x in s	True if x is in s, and False otherwise
      x not in s	opposite of in: True if x is not in s, and False otherwise
      s.add(x)	add element x to set s, where x is immutable
      s.discard(x)	removes x from set s if present (no error if not present)
      for value in s:	loop over each value in set s

   
   
   2. Operations on two sets
      
      

      Operation	Equivalent	Result
      s.issubset(t)	s <= t	test whether every element in s is in t
      s.issuperset(t)	s >= t	test whether every element in t is in s
      s.union(t)	s | t	new set with elements from both s and t
      s.intersection(t)	s & t	new set with elements common to s and t
      s.difference(t)	s - t	new set with elements in s but not in t



5. Example: Comparing Two Large Lists
   
   # This is a perfect case for using set differences (s - t) # We start with two large lists: list1 = ['Lemon', 'Mauve', 'Lilac', 'Taupe', 'Slate', 'Pear', 'Copper', 'Amaranth', 'Lavender', 'Amethyst', 'Champagne', 'Harlequin', 'Periwinkle', 'Teal', 'Carmine', 'Red', 'Baby', 'Magenta', 'White', 'Silver', 'Byzantium', 'Brown', 'Cerulean', 'Blush', 'Ruby', 'Raspberry', 'Gold', 'Tan', 'Cyan', 'Scarlet', 'Desert', 'Viridian', 'Jungle', 'Spring', 'Orchid', 'Beige', 'Emerald', 'Prussian', 'Olive', 'Chartreuse', 'Indigo', 'Pink', 'Salmon', 'Puce', 'Blue', 'Electric', 'Persian', 'Violet', 'Bronze', 'Ivory', 'Cobalt', 'Navy', 'Maroon', 'Azure', 'Turquoise', 'Jade', 'Orange-red', 'Spring', 'Coral', 'Plum', 'Green', 'Aquamarine', 'Peach', 'Apricot', 'Blue-violet', 'Black', 'Ocher', 'Coffee', 'Sangria', 'Magenta', 'Crimson', 'Cerise', 'Sapphire', 'Purple', 'Orange', 'Amber', 'Gray', 'Erin', 'Chocolate', 'Red-violet', 'Rose', 'Lime', 'Yellow'] list2 = ['Coffee', 'Navy', 'Lilac', 'Mauve', 'Plum', 'Ocher', 'Bronze', 'Baby', 'Slate', 'Pink', 'Copper', 'Silver', 'Olive', 'White', 'Sapphire', 'Spring', 'Jungle', 'Apricot', 'Raspberry', 'Lime', 'Magenta', 'Periwinkle', 'Maroon', 'Carmine', 'Gold', 'Pear', 'Cyan', 'Red', 'Amethyst', 'Turquoise', 'Harlequin', 'Chartreuse', 'Emerald', 'Blue', 'Blue-green', 'Chocolate', 'Crimson', 'Indigo', 'Orchid', 'Ivory', 'Azure', 'Blue-violet', 'Burgundy', 'Violet', 'Salmon', 'Spring', 'Lavender', 'Tan', 'Taupe', 'Erin', 'Beige', 'Cobalt', 'Red-violet', 'Rose', 'Amber', 'Amaranth', 'Teal', 'Yellow', 'Purple', 'Byzantium', 'Blush', 'Desert', 'Lemon', 'Electric', 'Sangria', 'Prussian', 'Aquamarine', 'Orange-red', 'Cerulean', 'Brown', 'Puce', 'Coral', 'Gray', 'Viridian', 'Jade', 'Scarlet', 'Champagne', 'Peach', 'Green', 'Magenta', 'Orange', 'Black'] # And we ask: which colors are only in one of the two lists? colors1 = set(list1) colors2 = set(list2) print('Colors in list1 but not in list2:', colors1 - colors2) print('Colors in list2 but not in list1:', colors2 - colors1)