how to duplicate array entries

Alf P. Steinbach alfps at start.no
Mon Jan 11 12:12:56 CET 2010


* Chris Rebert:
> On Mon, Jan 11, 2010 at 2:20 AM, Alf P. Steinbach <alfps at start.no> wrote:
>> * 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:
> <snip>
>>>>>> 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
> 
> No, I mean the computer science definition/term:
> http://en.wikipedia.org/wiki/List_(computer_science)

Note that the default meaning is a list with the characteristics of a linked list.

The abstract data type specified in that article is a bit more restricted than 
the usual meaning of list -- as the article notes, the ADT it presents is 
equivalent to an abstract stack, and it's essentially the Lisp view of lists, 
not only just linked list but a restricted view of linked lists. To understand 
it you have to keep in mind that such an ADT is a simplification, for the 
purpose of specifying logical functionality and nothing else. The algorithmic 
efficiency is simply not specified, but is implied.

Unfortunately, as noted there, the article doesn't cite any references or sources...

Here's one:

http://www.itl.nist.gov/div897/sqg/dads/HTML/list.html


>>> 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?
> 
> http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html

Thanks. I didn't know that. It's a very dirty hodgepodge interface with 
*optional* methods that throw exceptions if not implemented and apparently no 
constraints on algorithmic complexity for various methods. As such, it's a very 
good example why 'list' should not be conflated with 'array'. It leads to such 
monstrosities where neither correctness nor any kind of efficiency is guaranteed 
  :-)

Cheers, & thanks,


- Alf

PS: Please do not mail me copies of your replies to the group. A mail copy means 
that I may have to answer your article twice, as in this case.



More information about the Python-list mailing list