Python list index method time complexity

Imagine that you are organizing a data science conference. You are making a list of attendees. Later you want to look up a name in this attendee list. How much time does it take to find a name if you store the data as a list, and as a dictionary? If 100 people are attending your conference, you don’t have to think about lookup speed. You can keep your data in lists or dictionaries. You can even build an Excel table and use INDEX and MATCH keys to find the names you want.

What if you are storing billions of names? Do you think it is a good idea to store too many elements in a list? Can dictionaries do a better job in finding a certain item in a collection of too many elements?

In this blog, I am going to answer time-related questions about lists and dictionaries.

Let me give brief definitions of lists and dictionaries.

Lists

Lists are one of the most commonly used data types in Python. A list is a sequence of items in an order.

Lists are mutable, they can be changed after they are created.

Accessing elements of a list:

We can access the elements of a list by their indexes.

Dictionaries

Dictionaries are unordered collections of key-value pairs, or items.

Dictionaries are also mutable, we can add, remove, and/or change items as needed.

Accessing elements of a dictionary:

We can access the elements of a dictionary by their keys.

Test Run

Time to run tests and compare the lookup speeds of both dictionaries and lists!

Below are the hardware and software configurations of my device. The test results may vary depending on your computer’s configuration.

Lists Test Run

Define a function to find a number in a list.

Create a long list and a short list to compare the lookup speed.

Call the function and measure time with timeit.

As we can see in the test run, the larger the list, the longer it takes.

Dictionaries test run

Define a function to find a number in a dictionary.

Create a long dictionary and a short dictionary to compare the lookup speed.

Call the function and measure time using timeit.

As we can see in the test run, the length of the dictionary doesn’t affect the lookup time.

Analysis Of The Test Run Result

In this simple example, with my laptop’s configurations,

For 100 items

0.0000014 seconds /0.00000021 seconds= 6.66

A dictionary is 6.6 times faster than a list when we lookup in 100 items.

For 10,000,000 items

0.123 seconds /0.00000021seconds = 585714.28

When it comes to 10,000,000 items a dictionary lookup can be 585714 times faster than a list lookup.

6.6 or 585714 are just the results of a simple test run with my computer. These may change in other cases.

Why is looking up entries in a dictionary so much faster?

• You have to go through the entire list to get what you want. However, a dictionary will return the value you ask for without going through all keys.
• The two times above for 100 and 10000000 are almost the same for a dictionary, which is because a dictionary can almost instantly jump to the key it is asked for thanks to the lookups.
• Lookups are faster in dictionaries because Python implements them using hash tables.
• If we explain the difference by Big O concepts, dictionaries have constant time complexity, O[1] while lists have linear time complexity, O[n].

The fastest way to repeatedly lookup data with millions of entries in Python is using dictionaries. Because dictionaries are the built-in mapping type in Python thereby they are highly optimized. However, we have a typical space-time tradeoff in dictionaries and lists. It means we can decrease the time necessary for our algorithm but we need to use more space in memory.

Although dictionaries are optimized a lot more in Python 3.6, they still use more memory than lists, since you need to use space for the keys and the lookup as well, while lists use space only for the values.

Useful Links

1. Time complexity comparisons of other operations like append, delete, reverse in lists and dictionaries from Geeks for geeks.
2. An excellent explanation about time complexity and big O notation by CS Dojo.

3. A 6-minute neat explanation to hash tables and lookups by Gayle Laakmann, the author of the book Cracking The Coding Interview.

Thanks for reading.

If you want to get into contact, you can email me at , or you can find me at //www.linkedin.com/in/seyma-tas/