Are Dictionaries Faster than Lists in Python?
In this tutorial, you’ll learn about the aspects in which dictionaries are faster than lists in Python .
The table of content is structured as follows:
Let’s dive into it!
Accessing the Elements
In general, accessing an element in a dictionary is faster than accessing an element in a list in Python, especially when the collection size is large.
The reason for this is that dictionaries use a hash table to store their data, which allows for constant-time access to elements. When a value is looked up in a dictionary by its key, Python computes a hash value for the key and uses it to find the corresponding value in the hash table quickly. On the other hand, in a list, Python must traverse the list sequentially to find the desired element, which takes time proportional to the size of the list.
To understand the difference better, let’s imagine an example problem. Consider a group of cities, and their populations are given, and our program requires accessing the populations whenever the user requires them. The problem can be solved by utilizing dictionaries or lists; however, there would be a clear computation speed difference in favor of dictionary implementation.
- In the dictionary implementation, the desired city name would be entered as the key, the hash value for this city would be computed, and the memory slot allocated would be accessed after constant time operations.
- In the case of lists, there would be two lists: List 1, which includes all the city names in the dataset, while List 2 has the respective populations of the cities in the same indices, for example, if “Karlsruhe” is at index 7 in List 1, then it’s population is stored at index 7 in List 2. Now to access the population of Karlsruhe, the program needs to iterate through all the cities until the index is found and the population is retrieved from List 2.
The problem exemplifies that accessing elements in lists has O(n) complexity compared to O(1), i.e. constant, complexity of the access time of dictionaries. Now let’s take a look at their speed comparison when we are iterating through the data structures.
Iterating Through the Elements
Even though dictionaries’ speed is higher when accessing an element, it’s worth noting that there are cases where lists can be faster in comparison with dictionaries, especially when you need to iterate over the elements in a specific order or perform operations that modify the order of the elements.
Consider the same example we mentioned above, but assume we need to sort the cities based on their population. We need to access every element of the data sets and switch their positions. The sorting algorithms work with the same essentials for both data structures, but now dictionaries lose the advantage of accessing only the target element since, in both cases, the total count of access operations is going to be the same. Furthermore, dictionaries need to compute a hash value for every operation, while lists need a simple integer. On top of this, a hash-map requires excessive memory to operate, which might also be problematic if the data size is too large.
Ultimately, the choice between using a dictionary or a list depends on the specific requirements of your program, the operations you need to perform on the data, and the size of your data set. Hope the tutorial helped, see you in the next tutorial!
Video, Further Resources & Summary
Do you need more explanations on the properties of Dictionaries and Lists? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.
The YouTube video will be added soon.
Furthermore, you could have a look at some of the other tutorials on Statistics Globe:
- Lists in Python (13 Examples)
- Difference Between List & Tuple in Python
- Difference Between List & Series in Python
- Difference Between List & Dictionary in Python
- Convert Dictionary to List in Python
- All Python Programming Examples
This post has shown the advantages and disadvantages of using dictionaries instead of lists. In case you have further questions, you may leave a comment below.
This page was created in collaboration with Ömer Ekiz. You may have a look at Ömer’s author page to read more about his academic background and the other articles he has written for Statistics Globe.
Statistics Globe Newsletter