
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.
list1 = [4, 0.22, "Hello", [1, 2, 3], -2.5, 0.22]
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.
print ( list1[0] )
4
Dictionaries
Dictionaries are unordered collections of key-value pairs, or items.
dict1 = {key1: value1, key2: value2, key3: value3}
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.
print( dict1[key1] )
value1
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.
def find_number_in_list(lst, number):
if number in lst:
return True
else:
return False
Create a long list and a short list to compare the lookup speed.
short_list = list(range(100))
long_list = list(range(10000000))
Call the function and measure time with timeit.
%timeit find_number_in_list(short_list, 99)
1.4 µicrosecond = 0.0000014 second
%timeit find_number_in_list(long_list, 9999999)
123 millisecond = 0.123 second
As we can see in the test run, the larger the list, the longer it takes.
List length comparison: 10000000 / 100 = 100000
Lookup time comparison: 0.123 / 0.0000014 = 87857
Dictionaries test run
Define a function to find a number in a dictionary.
def find_number_in_dict(dct, number):
if number in dct.keys():
return True
else:
return False
Create a long dictionary and a short dictionary to compare the lookup speed.
short_dict = {x:x*5 for x in range(1,100)}
long_dict = {x:x*5 for x in range(1,10000000)}
Call the function and measure time using timeit.
%timeit find_number_in_dict(short_dict, 99)
210 nanosecond = 0.00000021 second
%timeit find_number_in_dict(short_dict, 9999999)
220 nanosecond = 0.00000022 second
As we can see in the test run, the length of the dictionary doesn’t affect the lookup time.
Dict length comparison: 10000000 / 100 = 100000
Lookup time comparison: 0.00000021 / 0.00000022 = 0.9545
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).
Space-time tradeoff
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
- Time complexity comparisons of other operations like append, delete, reverse in lists and dictionaries from Geeks for geeks.
- An excellent explanation about time complexity and Big O Notation by CS Dojo.
- 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 [email protected], or you can find me at https://www.linkedin.com/in/seyma-tas/