An Introduction to the Art of Computer Programming Using Python in the Age of Generative AI

VI. Dictionaries and Sets

Introduction to Dictionaries and Sets

Dictionaries and sets are versatile collections in Python that are used to store and manage data efficiently. Dictionaries allow you to store key-value pairs, providing a fast way to retrieve values based on their keys. Sets, on the other hand, are collections of unique elements and are excellent for performing set operations.

Python Dictionaries are Hashed Tables

Python dictionaries are efficient because they use hash functions to map unique, immutable keys to values stored in a hash table. This means that values can be accessed directly by computing the index from the key, rather than searching through the elements one by one as you would in a list. While lists have linear time complexity, meaning that search times increase with list size, dictionary operations can often be performed in constant time, making them much faster for lookup operations regardless of dictionary size. This efficiency in accessing items makes dictionaries ideal for situations where fast data retrieval is essential.

Python dictionaries are implemented as hashed tables, where each key is passed through a hash function that assigns that key a unique index in an underlying array-like structure. When you access or insert an entry into a dictionary, Python uses this hash function to quickly compute the index. Because this computation and the subsequent memory access are done in constant time, the average complexity for these operations is O(1), making it very efficient for lookups, insertions, and deletions.

Now let's look at the visualization of the hash table below. This visualization represents a simplified model of a Python dictionary. Each key entered is processed by a hash function to determine its index in a table, and the value is stored at that index. When a value is retrieved, the same hash function computes the index, and the value is accessed directly. This demonstrates why dictionary operations in Python are generally O(1) under the hood—because the hash function allows direct access to the value by its key, without having to search through all the elements.

In this simplified example, a hash function adds the numeric values encoding the characters entered and uses the modulo operation (%) to calculate the index to which the value is assigned from the sum. Unfortunately, this simple hash function is not suitable for all cases, because inputs whose characters result in the same sum are assigned to the same index, i.e., the assignment is not unique.

# Creating a dictionary
my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
print(my_dict)

# Accessing elements
print(my_dict['apple'])

# Adding elements
my_dict['date'] = 4
print(my_dict)

# Deleting elements
del my_dict['banana']
print(my_dict)
        

Run

Working with Sets

Sets are an unordered collection datatype that is iterable, mutable, and has no duplicate elements. Sets are also implemented as hashed tables behind the scenes, so that, for example, data retrieval is more efficient than with a list.

# Creating a set
my_set = {1, 2, 3, 4, 5}
print(my_set)

# Adding elements
my_set.add(6)
print(my_set)

# Removing elements
my_set.remove(3)
print(my_set)

# Set operations
another_set = {4, 5, 6, 7, 8}
print(my_set.union(another_set))
print(my_set.intersection(another_set))
        

Run

Advanced Set Operations

Sets support a variety of operations similar to mathematical set operations, such as union, intersection, difference, and symmetric difference. These operations allow you to efficiently combine and compare sets.

# Set difference
set1 = {1, 2, 3, 4, 5}
set2 = {4, 5, 6, 7, 8}
print(set1.difference(set2))  # Elements in set1 but not in set2

# Symmetric difference
print(set1.symmetric_difference(set2))  # Elements in either set1 or set2, but not in both
        

Run

Prompting Generative AI for Efficient Use of Dictionaries and Sets

Leveraging Generative AI to implement dictionaries and sets effectively requires crafting precise and application-oriented prompts. By providing clear objectives, context, and specific requirements, you can obtain AI-generated code that meets your programming needs efficiently. Below are some strategies to enhance your interactions with AI:

• Define Your Objective: Clearly state what you aim to achieve with your program. For example, instead of asking "How do I create a dictionary in Python?", ask "How can I create a Python program that manages a shopping list where users can add and remove items along with their quantities?"
• Provide Context: Explain the scenario or problem you're addressing. For instance, "I need a Python script to handle a shopping list that allows users to add new items with quantities, remove existing items, and view the current list with total quantities."
• Specify Requirements: Outline any specific functionalities or constraints. For example, "The shopping list should be stored in a dictionary with item names as keys and quantities as values, and it should prevent duplicate items."
• Ask for Examples: Request sample code to see practical implementations. For example, "Can you provide a Python example of using a dictionary to manage a shopping list with add, remove, and display functionalities?"
• Specify the Outcome: Clearly state what you aim to achieve. Instead of asking "How can I manipulate a dictionary?", ask "How can I add, remove, and update items in a Python dictionary to manage a shopping list system effectively?"

Example Prompt:

Resulting AI-generated code:

# Shopping List Management Program
shopping_list = {}

def add_item(item, quantity):
    if item in shopping_list:
        shopping_list[item] += quantity
        print(f'Updated "{item}" quantity to {shopping_list[item]}.')
    else:
        shopping_list[item] = quantity
        print(f'"{item}" has been added to your shopping list with quantity {quantity}.')

def remove_item(item):
    if item in shopping_list:
        del shopping_list[item]
        print(f'"{item}" has been removed from your shopping list.')
    else:
        print(f'"{item}" not found in your shopping list.')

def display_list():
    if shopping_list:
        print("Your Shopping List:")
        total_items = 0
        for item, quantity in shopping_list.items():
            print(f"- {item}: {quantity}")
            total_items += quantity
        print(f"Total items: {total_items}")
    else:
        print("Your shopping list is currently empty.")

# Example Usage
add_item("Milk", 2)
add_item("Bread", 1)
display_list()
add_item("Eggs", 12)
display_list()
remove_item("Bread")
display_list()
        

Run