List, set, and dictionary complexity in Python

Let’s dive into the exciting world of Python data structures! 🐍

Imagine you’re at a party, and you’ve got a list of guests. Now, you want to find your friend Bob in the crowd. You could go through each person one by one (like a list), or you could ask everyone to form groups based on their first name (like a set). Which do you think would be faster? Let’s find out!

# We have a party with 100,000 guests
guest_list = list(range(100000))
guest_set = set(guest_list)

%timeit 50000 in a_list_range
%timeit 50000 in a_set_range
%timeit 500000 in a_list_range
%timeit 500000 in a_set_range

So now we have a range of 0 to 99,999 that is implemented as both a list and a set. We search both data structures for 50,000 and 500,000. Here are the timings:

455 µs ± 2.68 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
40.1 ns ± 0.115 ns per loop (mean ± std. dev. of 7 runs,
➥ 10,000,000 loops each)
936 µs ± 9.37 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
28.1 ns ± 0.107 ns per loop (mean ± std. dev. of 7 runs,
➥ 10,000,000 loops each)

Even when the party is huge (0 to 99,999 guests), finding Bob is much quicker in the set. That’s because in Python, a set uses something called a hash, which is like a super-efficient guest list organizer. It doesn’t matter if your party has 10 or 10 million guests, a set will find Bob in no time!

But wait, there’s more! If you’re looking for a specific guest (like Bob), a dictionary can be super fast. But if you’re looking for a group of guests (like everyone between Alice and Charlie), then an ordered list is your best bet.

# If you're looking for a group of guests
# An ordered list with a bisection algorithm would perform much better

So, while lists are great and easy to use in Python, remember that sometimes a set or a dictionary might be a better option. And be careful when using in to search inside large lists - it can slow things down!

By the way, for most searching operations, there’s an even better data structure than lists, sets, or dictionaries: trees. But that’s a story for another day.

Remember, choosing the right data structure is like choosing the right tool for a job. It can make your code faster, smarter, and even more fun to write! Happy coding! 🚀