Menu
Today in class, we learned that retrieving an element from a list is O(1) in Python. Why is this the case? Suppose I have a list of four items, for example:
li = ["perry", 1, 23.5, "s"]
These items have different sizes in memory. And so it is not possible to take the memory location of li[0] and add three times the size of each element to get the memory location of li[3]. So how does the interpreter know where li[3] is without having to traverse the list in order to retrieve the element?
789
accessing a list l at index n l[n] is O(1) because it is not implemented as a Vanilla linked list where one needs to jump between pointers (value, next-->) n times to reach cell index n.
python lists are 0-indexed. So the first element is 0, second is 1, so on. So if the there are n elements in a list, the last element is n-1. Remember this!
The average time complexity of the in operator for lists is O(n) . It becomes slower when there are many elements. The execution time varies greatly depending on the position of the value to look for.
In python, to search an item from a list by using linear search is a straightforward and common term. It simply starts from the left of the list item and starts checking the items with the given item. Finally, returns a Boolean value as If it finds the item, it will return true otherwise false Let’s see an example of it in the below section:
We can use the in-built python List method, count (), to check if the passed element exists in List. If the passed element exists in the List, count () method will show the number of times it occurs in the entire list. If it is a non-zero positive number, it means an element exists in the List.
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.
When given a set of input values, with a lookup operation we can retrieve its corresponding output values from the given table or database. Lookup tables are also known as dictionaries in python. Dictionaries represent the implementation of a hash table in order to perform a lookup.
A list in Python is implemented as an array of pointers1. So, what's really happening when you create the list:
["perry", 1, 23.5, "s"]
is that you are actually creating an array of pointers like so:
[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]
Each pointer "points" to the respective objects in memory, so that the string "perry" will be stored at address 0xa3d25342 and the number 1 will be stored at 0x635423fa, etc.
Since all pointers are the same size, the interpreter can in fact add 3 times the size of an element to the address of li[0] to get to the pointer stored at li[3].
1 Get more details from: the horse's mouth (CPython source code on GitHub).
76
When you say a = [...], a is effectively a pointer to a PyObject containing an array of pointers to PyObjects.
When you ask for a[2], the interpreter first follows the pointer to the list's PyObject, then adds 2 to the address of the array inside it, then returns that pointer. The same happens if you ask for a[0] or a[9999].
Basically, all Python objects are accessed by reference instead of by value, even integer literals like 2. There are just some tricks in the pointer system to keep this all efficient. And pointers have a known size, so they can be stored conveniently in C-style arrays.
17
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
