Mixing
How come retrieving an element from a list is O(1)
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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 4 items ie:
`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 3 times the size of each element to get the memory location of li[3]. So how does the interprettor know where li[3] is without having to traverse the list in search of it?
arrays lists python
asked 3 hours ago
Teererai Marange
1425
add a comment |Â
up vote
2
down vote
favorite
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 4 items ie:
`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 3 times the size of each element to get the memory location of li[3]. So how does the interprettor know where li[3] is without having to traverse the list in search of it?
arrays lists python
asked 3 hours ago
Teererai Marange
1425
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 4 items ie:
`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 3 times the size of each element to get the memory location of li[3]. So how does the interprettor know where li[3] is without having to traverse the list in search of it?
arrays lists python
asked 3 hours ago
Teererai Marange
1425
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 4 items ie:
`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 3 times the size of each element to get the memory location of li[3]. So how does the interprettor know where li[3] is without having to traverse the list in search of it?
arrays lists python
arrays lists python
asked 3 hours ago
Teererai Marange
1425
asked 3 hours ago
Teererai Marange
1425
asked 3 hours ago
Teererai Marange
1425
asked 3 hours ago
Teererai Marange
1425
asked 3 hours ago
Teererai Marange
1425
1425
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
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 terp 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.
answered 1 hour ago
Draconis
2,730413
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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 terp 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.
answered 1 hour ago
Draconis
2,730413
add a comment |Â
up vote
2
down vote
accepted
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 terp 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.
answered 1 hour ago
Draconis
2,730413
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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 terp 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.
answered 1 hour ago
Draconis
2,730413
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 terp 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.
answered 1 hour ago
Draconis
2,730413
answered 1 hour ago
Draconis
2,730413
answered 1 hour ago
Draconis
2,730413
answered 1 hour ago
Draconis
2,730413
2,730413
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f98240%2fhow-come-retrieving-an-element-from-a-list-is-o1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
