Looking for ways to optimize python lists? We will cover a few data structures and algorithms that will help you optimize your code when working with lists. At the end of this post you will have a general understanding of the bisect module, deques, and heaps. All of which can be helpful when using lists.
Bisect Module
When working with a sorted list in python, you don’t have to use a for loop to iterate through it. Especially, when looking for an insertion point or categorizing numeric data. Searching a list using a for loop could potentially require us to iterate over the entire list before finding or not finding the value we are looking for. In terms of time complexity this is equivalent to O(n) because our execution time is dependent upon the size of the list. However, when using the bisect module a binary search is conducted improving the time complexity to O(log(n)).
Deque
In python, lists are optimized to be Last In First Out (LIFO) stacks. This optimization enables items to be added and removed from the right side of the list. When items are added to the left side of the list, the entire list is reallocated in memory. To prevent from reallocating memory when adding items to the left side of the list, you can use a deque from the collections module. Deque is a double ended queue that is optimized for adding items to both sides of a list. When using deque, item access time may be slower.
Heapq
In need of a priority queue? Then use the heapq module in your solution. Instead of sorting a list every time an item is added to the stack, you can leverage the heap data structure. Heapq will always pop the smallest element off of the stack and the heap will always store the smallest element at the first index of the heap. With the help of heaps and heapq, you are able to simplify your priority queue solution and increase efficiency.
Recap
Have questions? Contact us today, we would love to hear from you.
