Mixing
How come list element lookup is O(1) in Python?
Clash Royale CLAN TAG#URR8PPP
up vote
9
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 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?
python arrays list
edited 9 mins ago
Peter Mortensen
13k1983111
asked 6 hours ago
Teererai Marange
64121331
add a comment |Â
up vote
9
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 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?
python arrays list
edited 9 mins ago
Peter Mortensen
13k1983111
asked 6 hours ago
Teererai Marange
64121331
9
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
13
Don't confuse item access, which isO(1), with item lookup / search, which isO(n).
– Mike Scotty
6 hours ago
1
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Pythonlistobjects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
– juanpa.arrivillaga
5 hours ago
add a comment |Â
up vote
9
down vote
favorite
up vote
9
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 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?
python arrays list
edited 9 mins ago
Peter Mortensen
13k1983111
asked 6 hours ago
Teererai Marange
64121331
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?
python arrays list
python arrays list
edited 9 mins ago
Peter Mortensen
13k1983111
asked 6 hours ago
Teererai Marange
64121331
edited 9 mins ago
Peter Mortensen
13k1983111
asked 6 hours ago
Teererai Marange
64121331
edited 9 mins ago
Peter Mortensen
13k1983111
edited 9 mins ago
Peter Mortensen
13k1983111
edited 9 mins ago
Peter Mortensen
13k1983111
13k1983111
asked 6 hours ago
Teererai Marange
64121331
asked 6 hours ago
Teererai Marange
64121331
asked 6 hours ago
Teererai Marange
64121331
64121331
9
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
13
Don't confuse item access, which isO(1), with item lookup / search, which isO(n).
– Mike Scotty
6 hours ago
1
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Pythonlistobjects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
– juanpa.arrivillaga
5 hours ago
add a comment |Â
9
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
13
Don't confuse item access, which isO(1), with item lookup / search, which isO(n).
– Mike Scotty
6 hours ago
1
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Pythonlistobjects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.
– juanpa.arrivillaga
5 hours ago
9
9
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
13
13
Don't confuse item access, which is
O(1), with item lookup / search, which is O(n).– Mike Scotty
6 hours ago
Don't confuse item access, which is
O(1), with item lookup / search, which is O(n).– Mike Scotty
6 hours ago
1
1
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
4
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Python
list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.– juanpa.arrivillaga
5 hours ago
Python
list objects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.– juanpa.arrivillaga
5 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
21
down vote
accepted
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).
answered 6 hours ago
DJG
3,95232142
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
21
down vote
accepted
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).
answered 6 hours ago
DJG
3,95232142
add a comment |Â
up vote
21
down vote
accepted
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).
answered 6 hours ago
DJG
3,95232142
add a comment |Â
up vote
21
down vote
accepted
up vote
21
down vote
accepted
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).
answered 6 hours ago
DJG
3,95232142
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).
answered 6 hours ago
DJG
3,95232142
edited 6 hours ago
answered 6 hours ago
DJG
3,95232142
answered 6 hours ago
DJG
3,95232142
answered 6 hours ago
DJG
3,95232142
3,95232142
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%2fstackoverflow.com%2fquestions%2f52684993%2fhow-come-list-element-lookup-is-o1-in-python%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
9
What makes you think that arrays are linearly allocated rather than a list of pointers. - [me confused by your profile description]
– Morrison Chang
6 hours ago
13
Don't confuse item access, which is
O(1), with item lookup / search, which isO(n).– Mike Scotty
6 hours ago
1
Lists don't physically contain other objects. It's almost impossible to have one object physically contain another object in Python.
– user2357112
6 hours ago
4
Some relevant reading material: Python list implementation, How is Python's List Implemented?, What is the underlying data structure for Python lists?.
– Warren Weckesser
6 hours ago
Python
listobjects are implemented as array-lists, not a linked-list structure. They are essentially arrays of PyObject pointers, in CPython.– juanpa.arrivillaga
5 hours ago