* Chris Rebert:
On Mon, Jan 11, 2010 at 1:03 AM, Alf P. Steinbach <al...@start.no> wrote:
* Steven D'Aprano:
On Mon, 11 Jan 2010 08:56:36 +0100, Alf P. Steinbach wrote:
* Paul Rudin:
Sebastian <sebastian.lan...@gmx.de> writes:
I have an array x=[1,2,3]
In python such an object is called a "list".
(In cpython it's implemented as an automatically resizable array.)
I don't think the OP's terminology needs correction.
A Python "list" is an array functionality-wise.
If one isn't observant of that fact then one ends up with O(n^2) time
for the simplest things.
Well that's certainly not true. Some operations may be O(N**2), but others
are not: list.append() is amortized O(N) and for individual appends, may be
can be as fast as O(1).
The second sentence may or may not be true. I don't know of any fundamental
'list' operations that have quadratic time. Is there?
The first sentence is just baffling -- what on Earth is the "that" that
you think is not true?
OK, I can guess (correct me if I'm guessing wrong, please): you think I'm
talking about elementary operations. I'm not. I'm talking about algorithmic
complexity for loops doing e.g. insertions.
Using the term "array" accentuates and clarifies this most important
aspect.
But Python lists are designed to behave as lists.
No, I'm sorry, they're not.
A Python 'list' has de facto constant time indexing, or "random access".
A linked list -- what the informal "list" means in programming
Eh, it's a bit context-dependent. The abstract data type definition is
a superset that includes both linked lists and dynamic arrays.
Assuming you're talking about some abstract type definition that's in some PEP
somewhere (there's no abstract data type in the language specification, it's all
informal) then that's a deficiency of the specification, since the type is
designed around indexing operations. Perhaps the designers thought it would be
"obvious", that no-one could mistake it for other than what it is? Anyway, that
doesn't make it context-dependent: if true, it only makes it poorly specified.
FWIW, Java likewise uses "list" in its ADT sense.
I'm sorry, I'm unfamiliar with that Java terminology (but then, reportedly, many
Java programmers think that Java has "pass by reference", so nothing coming from
that direction will surprise me very much!). The Java language specification has
a section about arrays, none about lists AFAICS. Do you have a reference?
Cheers & hth.,
- Alf
--
http://mail.python.org/mailman/listinfo/python-list
