DEV Community

Cover image for Data Structures in Python: set()
Abu Hurayra
Abu Hurayra

Posted on

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.

Set Example Image

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:

  1. Set items are unique. A set can not contain duplicate values or objects.
  2. 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.
  3. 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])
Enter fullscreen mode Exit fullscreen mode

Create a Set

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.

add element to set

clear()

Removes all the elements from the set.

clear a set

copy()

Returns a copy of the set.

copying a 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.

return the difference of 2 sets

difference_update()

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

update the first set with the difference

discard()

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

discard an element from set

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.

set intersection

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.

intersection update

isdisjoint()

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

is disjoint

issubset()

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

is subset

issuperset()

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

Is superset

pop()

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

Set pop

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.

remove from set

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

symmetric_difference_update()

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

symmetric difference update

union()

Return a set containing the union of sets.

union of sets

update()

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

update set

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:

  1. https://www.w3schools.com/python/python_sets_methods.asp
  2. https://wiki.python.org/moin/TimeComplexity

Top comments (0)