Data Structures in Python: set()

Do you remember what a Set is from your school days? A set is a well-defined group of distinct objects.

A set can be a very useful tool for computer programming. Python has a built-in set type. In this article we will learn about the set data type in python, its operations, complexities and where we can use this type.

What Are The Characteristics Of A Set In Python?

Python set has these characteristics:

Set items are unique. A set can not contain duplicate values or objects.
Sets are unordered. Set items do not follow any particular ordering. So we can not access set items with indexes like we can with arrays.
Set items can not be modified, but they can be removed and inserted.

How Do I Create A Set In Python?

We can create a set in python in the following ways:

a = set()
b = {1, 2, 3, 4}
c = set([1, 2, 3, 4])

What are the time complexities of common set operations?

Insertion: O(1) on average. But worst case can cause O(n) due to collision.
Searching: O(1) on average. But worst case can cause O(n) due to collision.

Operation	Average case	Worst Case	notes
x in s	O(1)	O(n)
Union s\	t	O(len(s)+len(t))
Intersection s&t	O(min(len(s), len(t))	O(len(s) * len(t))	replace "min" with "max" if t is not a set
Multiple intersection s1&s2&..&sn		(n-1)*O(l) where l is max(len(s1),..,len(sn))
Difference s-t	O(len(s))
s.difference_update(t)	O(len(t))
Symmetric Difference s^t	O(len(s))	O(len(s) * len(t))
s.symmetric_difference_update(t)	O(len(t))	O(len(t) * len(s))

What Methods Can Be Used With Sets?

A Set supports these methods:

add()

Adds an element to the set. If the element we are trying to add already exists in the set, then nothing will change.

clear()

Removes all the elements from the set.

copy()

Returns a copy of the set.

difference()

Returns a set containing the difference between two or more sets. It means which elements of the first set are not present in the second set.

difference_update()

Removes the items in the first set that are also included in the second set.

discard()

Remove the specified item. If the item is not present in the set, then nothing will happen. No error will be shown.

intersection()

Returns a set, that is the intersection of two or more sets. It means which elements are common to all of the given sets.

intersection_update()

Removes the items in this set that are not present in other, specified set(s). Which means that only the common items will be kept in the first set and other items will be removed.

isdisjoint()

Returns whether two sets have an intersection or not. Are the two sets completely different?

issubset()

Returns if the first set a subset of the second or not.

issuperset()

Returns whether the first set is a superset of the second set or not.

pop()

Removes and returns a random element from the set. If the set is empty, then an error occurs.

remove()

Removes the specified element. An error will be raised if the item to remove does not exist. Use discard() instead of remove() to avoid the error.

symmetric_difference()

Returns a set with the symmetric differences of two sets. Symmetric difference means the set of all items except those that are common in both sets.

symmetric_difference_update()

Update the first set with the symmetric difference if the 2 sets.

union()

Return a set containing the union of sets.

update()

Update the set with another set, or any other iterable.

When is a set useful?

A set allows us to insert and search for elements in O(1) time on average. This is due to the underlying hash table that implements a python set. The uniqueness of the elements can be used to efficiently remove duplicates from a list.

Thank you so much for reading

☺

References:

Blog