Python Tip #8 – reducing looping by using dicts

In situations where you have a list of objects and have to retrieve then in random order, dictionaries can act as lookup tables.

users = list of class User 

# Get users one by one by looking up ids
user_1 = next((u for u in users if u.id == user_1_id), None)
user_2 = next((u for u in users if u.id == user_2_id), None)
...

# Simpler solution using lookup table
lookup = dict((u.id, user) for u in users)
user_1 = lookup[user_1_id]
user_2 = lookup[user_2_id]
...

This tip is not very obvious, hence this explanation:

user_1 = next((u for u in users if u.id == user_1_id), None)

This method employs a iterator looping through the list of users every time we have to find a user, which means we have to run this loop a hundred times. This poses a complexity of O(N2).

lookup = dict((u.id, user) for u in users)
user_1 = lookup[user_1_id]

This method on the other hand iterates through the users list one time and create a lookup table that we can again and again without having to iterate through the list every time. This reduces the complexity to O(N) which could theoretically lead up to 10 times faster execution of the program.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.