Asymptotic Analysis of Data Structures (Optional)
So far in this course, you learned about different data structures such as lists, sets, tuples, and dictionaries but you never learned WHY it is better to use which in which scenarios. The answer to this question depends on mainly three things: ease of implementation, memory, and running time of operations. Sometimes programmers are lazy and will prioritize how quickly they can finish up the code over how good the code is (dependent on memory taken up and running time). We will cover mainly the running time of operations and a bit about memory. This is by no means comprehensive.
Tuple vs List
Essentially, a list is everything a tuple wants to be but more. However, the restrictions of a tuple (immutability) make it faster and more memory efficient. So use tuples when you really don’t need the mutability of a list. If you do need the mutability, use a list.
Set/Dictionary vs List
All three are mutable. Set/dictionary being unordered means checking membership takes O(1) whereas it takes O(n) to check for membership in lists because they are ordered. Also, removing and inserting into a set/dictionary usually takes O(1), whereas inserting in the back and removing from the back is O(1) (inserting/removing from the front, however, is O(n)). You would want to use a list over a set/dictionary when you want an ordered structure. Also, iterating over a list is faster than a set/dictionary (although both O(n)).
Set vs Dictionary
A set is used when you don’t need the key-value pair, as it takes less memory than the dictionary. Think about it. The values of a set are essentially the keys in the dictionary, so dictionaries have what sets have but with something attached to it.
You can use the python
timeit module to test for yourself which operations are faster. You can do a bit of google searching to figure out more about the running time of data structures.Copyright © 2021 Code 4 Tomorrow. All rights reserved.
The code in this course is licensed under the MIT License.
If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.