Python Lists

I don't understand how a list works in Python.

I always assumed that it was just a linked list with the "link" part hidden to make it mutable. If I wanted to delete a value or a slice I assumed it would just mark the deleted parts for the GC and route the "links" around them.

x = [1,2,3,4,5]

x[0] = (1, 0x1111)
x[1] = (2, 0x2222)
x[2] = (3, 0x3333)

del x[1]

x[0] = (1, 0x1111)
x[1] = (3, 0x3333)

Is this how it works?

Wait, that doesn't convey what I mean, or make sense.


x = [1,2,3,4,5]

x[0] = (1, 0x1111)
x[1] = (2, 0x2222)
x[2] = (3, 0x3333)

del x[1]

x[0] = (1, 0x2222) /*Changed this*/
x[1] = (3, 0x3333)

Is this how it works?

stack overflow

I always assumed that it was just a linked list with the "link" part hidden to make it mutable. If I wanted to delete a value or a slice I assumed it would just mark the deleted parts for the GC and route the "links" around them.
That's implementation dependent but in CPython it's just a dynamic array.

They're resizable arrays (think Java's ArrayList) in the common implementations. Deleting/popping an element will shift the rest of the array elements back.

>>5
That sounds expensive.

>>6
In practice, it won't be noticeable in most cases, since it's implemented (in CPython) in quite fast C code, which's VROOM VROOM compared to the pure-Python libraries you're also likely to be using.

>>7
Languages can't escape time complexity.

>>8
The fixed 50-fold speed factor associated with going from CPython to C in CPU-bottlenecked code (i wrote a raytracer) compensates for time complexity until a very, very distant point.

In reality you can't ignore those constants that landau O() notation hides. That's why we don't all use the O(n^2.3...) method for matrix multiplication, because it's so much slower than the O(n^3) way.

>>5
Deleting/popping an element will shift the rest of the array elements back.
Nope.

Slice ops in python return new lists (semi-copies) of the original. They are mutable because ops that change the contents of a list (without changing the size of the list) do so in-place. Your del operation is syntactic sugar for an underlying slice:
x = x[:(del_index)] + x[(del_index + 1):]
which creates new lists for each operation.

>>8
yeah, but small input sizes can, and often do.

>>12
That's what i'm saying, you mental midget go scrub a toilet

>>11
That can't be right though. Lists aren't just syntactic sugar for tuples. If they were what would be the point of making them different?

>>14
You are correct. They are not tuples. They are mutable, you can change the contents without creating a new list. But to create or remove additional elements, a new list must be created. So therefore you can say that lists have mutable elements but immutable structure, while tuples have immutable elements and immutable structure.

>>15
Actually new list creation only seems to apply to slicing, seeing how variables containing lists are references, and the del operation seems to take place in-place. You know what, why not just ask the people who implement python?

>>8
Languages can do whatever they want, it's easy to define a language where every operation is O(1), it would just be impossible to implement.

>>17
That is incorrect you mental midget.

>>17
I suppose you could limit the language or library to things that can have known O(1) time implementations.

>>19
How would you do anything?

>>20
you could write your own functions that use loops and stuff, building the more expensive operations yourself. Oh, I thought you meant all the built in operations would be order 1. Do you mean that every operation that the user could possibly define would be order 1? That would be possible, but it would be hard to do things. You wouldn't be able to write a loop that prints "hello world" n times, for example. But who knows, maybe such a language would fill a niche. Like servers responding to clients, as quickly as possible.

>>18
No it's completely correct you stupid piece of shit, please state where you believe my post is false and I'll tell you why your inferior brain fails.

MENTAL MIDGET DRAFT (MM1X)

Mental Midget is a language that requires no specific syntax from its user, it is capable of understanding (to any conceivable extent) any human language and will execute the statement exactly as the programmer intended it to be executed as part of its mind reading capabilities. Mental Midget can and will do anything the programmer asks, including but not limited to cleaning their toilets, fucking off back to the imageboards and violate Guido van Rossums asshole together with the laws of Physics. Mental Midget programs might be interpreted or compiled or just executed by concentrated effort of the mind.

The purpose of this language is to supersede the "Compute" programming language (as defined in http://esolangs.org/wiki/Compute) as the "Compute" programming language lacks any form of output to the user.

Implementation is left as an exercise to the reader.

>>23
I ran this through a MM1X interpreter and it created the interpreter itself.

>>24
dickstrapping

>>24
That is possible only on a quantum machine.

>>26

is a quantum machine even possible? because (from the little i've read) they kind of make it sound like snake-oil...

>>27
My brain is a quantum machine, so is yours, unless you opened it up and looked inside causing all the wave functions to collapse, in which case you're single minded.

>>7
CPython is the standard Python implementation. It's just called CPython sometimes to distinguish it from Jython and other implementations. Also, PyPy, the Python-based implementation of Python, is actually FASTER than CPython, I shit you not.

http://stackoverflow.com/questions/2591879/pypy-how-can-it-possibly-beat-cpython

>>28
if you open it, it mutates
Sounds like another bullshit story made up by jews.

>>30
It's not mutation, see the basics of quantum theory.

>>28
in which case you're single minded.
I see what you did there.

>>28
Hey Penrose, there's still no evidence of that.