xbe.at

Python / Data structures and algorithms

Exploring Unordered Sets in Python

6 min read, 16 sections

Contents
  1. Introduction to Sets in Python
  2. Creating Sets
  3. Adding and Removing Elements
  4. Set Operations
  5. Set Comprehensions
  6. Frozen Sets
  7. Set Methods
  8. Real-life Example: Unique Visitors
  9. Results for: Real-life Example: Unique Visitors
  10. Real-life Example: Recipe Ingredient Comparison
  11. Results for: Real-life Example: Recipe Ingredient Comparison
  12. Set Performance
  13. Results for: Set Performance
  14. Mathematical Applications of Sets
  15. Results for: Mathematical Applications of Sets
  16. Additional Resources

Introduction to Sets in Python

Sets in Python are unordered collections of unique elements. They are versatile data structures used for storing multiple items without duplicates. Unlike lists or dictionaries, sets do not maintain a specific order of elements and cannot contain duplicate values. This makes them ideal for tasks that require uniqueness and fast membership testing.

# Creating a set
fruits = {"apple", "banana", "cherry"}
print(fruits)  # Output: {'cherry', 'banana', 'apple'} (order may vary)

# Trying to add a duplicate
fruits.add("apple")
print(fruits)  # Output: {'cherry', 'banana', 'apple'} (no change)

# Fast membership testing
print("banana" in fruits)  # Output: True

Creating Sets

Sets can be created using curly braces {} or the set() constructor. When using curly braces, separate elements with commas. The set() constructor can create sets from any iterable object, such as lists or tuples.

# Creating sets using different methods
set1 = {1, 2, 3, 4, 5}
set2 = set([3, 4, 5, 6, 7])
set3 = set("hello")

print(set1)  # Output: {1, 2, 3, 4, 5}
print(set2)  # Output: {3, 4, 5, 6, 7}
print(set3)  # Output: {'h', 'e', 'l', 'o'}

Adding and Removing Elements

Sets are mutable, allowing you to add or remove elements after creation. Use the add() method to insert a single element and update() to add multiple elements. To remove elements, use remove() or discard(). The difference is that remove() raises a KeyError if the element is not found, while discard() doesn't.

colors = {"red", "green", "blue"}

# Adding elements
colors.add("yellow")
colors.update(["purple", "orange"])

# Removing elements
colors.remove("green")
colors.discard("black")  # No error if "black" doesn't exist

print(colors)  # Output: {'red', 'blue', 'yellow', 'purple', 'orange'}

Set Operations

Sets support various mathematical operations like union, intersection, and difference. These operations are useful for comparing and combining sets efficiently.

set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7, 8}

# Union
union_set = set1.union(set2)
print("Union:", union_set)  # Output: {1, 2, 3, 4, 5, 6, 7, 8}

# Intersection
intersection_set = set1.intersection(set2)
print("Intersection:", intersection_set)  # Output: {4, 5}

# Difference
difference_set = set1.difference(set2)
print("Difference:", difference_set)  # Output: {1, 2, 3}

Set Comprehensions

Set comprehensions provide a concise way to create sets based on existing iterables. They follow a syntax similar to list comprehensions but use curly braces instead of square brackets.

# Creating a set of squares of even numbers from 0 to 9
even_squares = {x**2 for x in range(10) if x % 2 == 0}
print(even_squares)  # Output: {0, 64, 4, 36, 16}

# Creating a set of unique characters from a string
unique_chars = {char.upper() for char in "hello world"}
print(unique_chars)  # Output: {'H', 'E', 'L', 'O', 'W', 'R', 'D', ' '}

Frozen Sets

Frozen sets are immutable versions of regular sets. They have the same methods as regular sets, except those that modify the set. Frozen sets can be used as dictionary keys or as elements of other sets.

# Creating a frozen set
frozen_fruits = frozenset(["apple", "banana", "cherry"])

# Attempting to modify the frozen set (will raise an error)
try:
    frozen_fruits.add("orange")
except AttributeError as e:
    print("Error:", e)  # Output: Error: 'frozenset' object has no attribute 'add'

# Using a frozen set as a dictionary key
preferences = {
    frozenset(["apple", "banana"]): "Alice",
    frozenset(["cherry", "date"]): "Bob"
}
print(preferences)  # Output: {frozenset({'apple', 'banana'}): 'Alice', frozenset({'cherry', 'date'}): 'Bob'}

Set Methods

Sets provide various methods for manipulation and comparison. Some commonly used methods include clear(), copy(), issubset(), issuperset(), and symmetric_difference().

set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7, 8}

# Clear all elements from set1
set1.clear()
print("Cleared set1:", set1)  # Output: set()

# Create a copy of set2
set3 = set2.copy()
print("Copy of set2:", set3)  # Output: {8, 4, 5, 6, 7}

# Check if set3 is a subset of set2
print("Is set3 subset of set2?", set3.issubset(set2))  # Output: True

# Symmetric difference (elements in either set, but not in both)
sym_diff = set2.symmetric_difference({4, 5, 9, 10})
print("Symmetric difference:", sym_diff)  # Output: {6, 7, 8, 9, 10}

Real-life Example: Unique Visitors

Imagine you're tracking unique visitors to a website. Sets are perfect for this task as they automatically handle duplicates and provide fast lookup times.

# Simulating website visitors over a week
daily_visitors = [
    ["user1", "user2", "user3"],
    ["user2", "user4", "user5"],
    ["user1", "user3", "user5"],
    ["user6", "user2", "user1"],
    ["user3", "user4", "user6"],
    ["user5", "user2", "user1"],
    ["user4", "user3", "user2"]
]

unique_visitors = set()
for day in daily_visitors:
    unique_visitors.update(day)

print("Total unique visitors:", len(unique_visitors))
print("Unique visitors:", unique_visitors)

Results for: Real-life Example: Unique Visitors

Total unique visitors: 6
Unique visitors: {'user1', 'user2', 'user3', 'user4', 'user5', 'user6'}

Real-life Example: Recipe Ingredient Comparison

Sets can be useful in comparing ingredients across different recipes. This example demonstrates how to find common and unique ingredients between two recipes.

recipe1 = {"flour", "sugar", "eggs", "milk", "butter"}
recipe2 = {"flour", "sugar", "eggs", "vanilla", "baking powder"}

common_ingredients = recipe1.intersection(recipe2)
unique_to_recipe1 = recipe1.difference(recipe2)
unique_to_recipe2 = recipe2.difference(recipe1)

print("Common ingredients:", common_ingredients)
print("Unique to recipe 1:", unique_to_recipe1)
print("Unique to recipe 2:", unique_to_recipe2)

all_ingredients = recipe1.union(recipe2)
print("All ingredients needed:", all_ingredients)

Results for: Real-life Example: Recipe Ingredient Comparison

Common ingredients: {'sugar', 'flour', 'eggs'}
Unique to recipe 1: {'milk', 'butter'}
Unique to recipe 2: {'baking powder', 'vanilla'}
All ingredients needed: {'sugar', 'flour', 'eggs', 'milk', 'butter', 'baking powder', 'vanilla'}

Set Performance

Sets in Python are implemented using hash tables, which provide constant-time average case complexity for add, remove, and lookup operations. This makes sets extremely efficient for large collections of unique elements.

import time

# Comparing performance of sets vs lists for membership testing
def performance_test(n):
    # Create a set and a list with n elements
    set_data = set(range(n))
    list_data = list(range(n))
    
    # Test set membership
    start_time = time.time()
    for i in range(n):
        i in set_data
    set_time = time.time() - start_time
    
    # Test list membership
    start_time = time.time()
    for i in range(n):
        i in list_data
    list_time = time.time() - start_time
    
    return set_time, list_time

n = 100000
set_time, list_time = performance_test(n)
print(f"Time for {n} lookups:")
print(f"Set: {set_time:.6f} seconds")
print(f"List: {list_time:.6f} seconds")
print(f"Set is {list_time / set_time:.2f}x faster")

Results for: Set Performance

Time for 100000 lookups:
Set: 0.010255 seconds
List: 4.757950 seconds
Set is 463.95x faster

Mathematical Applications of Sets

Sets in Python can be used to represent mathematical sets and perform set operations. Here's an example demonstrating the use of sets for solving a simple set theory problem.

# Define the universal set U and sets A, B, C
U = set(range(1, 21))  # Universal set: integers from 1 to 20
A = {x for x in U if x % 2 == 0}  # Even numbers
B = {x for x in U if x % 3 == 0}  # Multiples of 3
C = {x for x in U if x % 5 == 0}  # Multiples of 5

# Calculate (A ∪ B) ∩ C'
result = (A.union(B)).intersection(U.difference(C))

print("U =", U)
print("A =", A)
print("B =", B)
print("C =", C)
print("(A ∪ B) ∩ C' =", result)

# Verify the result using set comprehension
verified_result = {x for x in U if (x in A or x in B) and x not in C}
print("Verified result:", verified_result)
print("Results match:", result == verified_result)

Results for: Mathematical Applications of Sets

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
B = {3, 6, 9, 12, 15, 18}
C = {5, 10, 15, 20}
(A ∪ B) ∩ C' = {2, 3, 4, 6, 8, 9, 12, 14, 16, 18}
Verified result: {2, 3, 4, 6, 8, 9, 12, 14, 16, 18}
Results match: True

Additional Resources

For those interested in delving deeper into sets and their applications in Python, here are some recommended resources:

  1. Python's official documentation on sets: https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
  2. "Effective Python: 90 Specific Ways to Write Better Python" by Brett Slatkin - This book includes advanced techniques for working with sets and other Python data structures.
  3. "Python Cookbook" by David Beazley and Brian K. Jones - Offers practical recipes for solving problems using sets and other Python features.
  4. ArXiv paper on set theory and its applications: "Set Theory and Its Applications" by Akihiro Kanamori (https://arxiv.org/abs/math/0703356)

These resources provide a mix of practical Python programming techniques and theoretical foundations of set theory, which can enhance your understanding and usage of sets in Python.

More in Data structures and algorithms

  1. Implementing a Queue Data Structure in Python16 min

    A Queue data structure implemented using Python lists, demonstrating the fundamental FIFO (First-In-First-Out) principle. This implementation showcases the...

  2. Exploring Linked Lists in Python9 min

    A linked list fundamentally begins with the Node class, representing individual elements in the list. Each node contains two essential components: the data...

  3. Implementing Efficient Graph Structures in Python9 min

    The adjacency list representation of graphs offers an efficient way to store sparse graphs where the number of edges is much less than the maximum possible...

  4. Depth-First and Breadth-First Search Algorithms in Python7 min

    Graph traversal is a fundamental technique in computer science for exploring and analyzing graph structures. Two primary methods are Depth-First Search (DFS)...

  5. Implementing Graph Data Structures in Python9 min

    A graph is a non-linear data structure consisting of vertices (nodes) and edges connecting these vertices. In Python, we can implement a graph using...

  6. Counting Sort Algorithm in Python9 min

    Counting Sort is a non-comparative sorting algorithm that operates in O(n+k) time complexity, where n is the number of elements and k is the range of input....