how to duplicate array entries
clp2 at rebertia.com
Mon Jan 11 10:21:40 CET 2010
On Mon, Jan 11, 2010 at 1:03 AM, Alf P. Steinbach <alfps at start.no> wrote:
> * Steven D'Aprano:
>> On Mon, 11 Jan 2010 08:56:36 +0100, Alf P. Steinbach wrote:
>>> * Paul Rudin:
>>>> Sebastian <sebastian.langer at 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
>> 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. FWIW,
Java likewise uses "list" in its ADT sense.
More information about the Python-list