how to duplicate array entries

Chris Rebert 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
>>> 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. FWIW,
Java likewise uses "list" in its ADT sense.

Cheers,
Chris
--
http://blog.rebertia.com



More information about the Python-list mailing list