how to duplicate array entries

[Alf P. Steinbach]

* Chris Rebert:
> 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
>>>> 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