in place-ness of list.append

[Bart Van Loon]

Hi all,

I would like to find out of a good way to append an element to a list
without chaing that list in place, like the builtin list.append() does.

currently, I am using the following (for a list of integers, but it
could be anything, really)

#--------------------------------------------------
def addnumber(alist, num):
""" work around the inplace-ness of .append """
mylist = alist[:]
mylist.append(num)
return mylist
#--------------------------------------------------

and I am wondering if this is good practice or not.

any advice on this matter?

thanks!

 

[Kent Johnson]

Hi all,

I would like to find out of a good way to append an element to a list
without chaing that list in place, like the builtin list.append() does.

currently, I am using the following (for a list of integers, but it
could be anything, really)

#--------------------------------------------------
def addnumber(alist, num):
""" work around the inplace-ness of .append """
mylist = alist[:]
mylist.append(num)
return mylist
#--------------------------------------------------

Use + :

In [1]: a=[1,2]

In [2]: b=a+[3]

In [3]: a
Out[3]: [1, 2]

In [4]: b
Out[4]: [1, 2, 3]

Kent

 

[skip]

Bart> #--------------------------------------------------
Bart> def addnumber(alist, num):
Bart> """ work around the inplace-ness of .append """
Bart> mylist = alist[:]
Bart> mylist.append(num)
Bart> return mylist
Bart> #--------------------------------------------------

Bart> and I am wondering if this is good practice or not.

Bart> any advice on this matter?

Such an operation will be O(N**2), and thus expensive if performed
frequently on lists of moderate length. I've never been tempted to do this.
Can you say a little about why you'd want to do this? Knowing that, perhaps
someone here can point you in a more Pythonic direction.

Skip

 

[Robin Becker]

Hi all,
........

#--------------------------------------------------
def addnumber(alist, num):
""" work around the inplace-ness of .append """
mylist = alist[:]
mylist.append(num)
return mylist
#--------------------------------------------------

and I am wondering if this is good practice or not.

any advice on this matter?

........

would it not be simpler to just use

..... alist+[num].....

where you need it? Seems more natural than

def addnumber(alist,num):
return alist+[num]

and then

......addnumber(alist,num)......

 

[Bart Van Loon]

Hi all,

I would like to find out of a good way to append an element to a list
without chaing that list in place, like the builtin list.append() does.

currently, I am using the following (for a list of integers, but it
could be anything, really)

#--------------------------------------------------
def addnumber(alist, num):
""" work around the inplace-ness of .append """
mylist = alist[:]
mylist.append(num)
return mylist
#--------------------------------------------------

Use + :

In [1]: a=[1,2]

In [2]: b=a+[3]

In [3]: a
Out[3]: [1, 2]

In [4]: b
Out[4]: [1, 2, 3]

should have known that...

thanks for you fast response!

 

[Bart Van Loon]

Bart> #--------------------------------------------------
Bart> def addnumber(alist, num):
Bart> """ work around the inplace-ness of .append """
Bart> mylist = alist[:]
Bart> mylist.append(num)
Bart> return mylist
Bart> #--------------------------------------------------

Bart> and I am wondering if this is good practice or not.

Bart> any advice on this matter?

Such an operation will be O(N**2),

why is that?

and thus expensive if performed frequently on lists of moderate
length. I've never been tempted to do this. Can you say a little
about why you'd want to do this? Knowing that, perhaps someone here
can point you in a more Pythonic direction.

I am building a binary tree where each node is a list. the two children
are the parent list + 1 and the parent list + 2.

I am using it recursively as such:

#-----------------------------------------------------------
def makescoretree(scorelist):
""" generates the Tree of possible scores """
if waves(scorelist) >= MAXWAVES:
return []
return Scoretree(scorelist,
makescoretree(addnumber(scorelist, 1)),
makescoretree(addnumber(scorelist, 6)))
#-----------------------------------------------------------

but now I found out that I can do this easily like

#-----------------------------------------------------------
def makescoretree(scorelist):
""" generates the Tree of possible scores """
if waves(scorelist) >= MAXWAVES:
return []
return Scoretree(scorelist,
makescoretree(scorelist + [1]),
makescoretree(scorelist + [6]))
#-----------------------------------------------------------

 

[skip]

Bart> why is that?

The a[:] operation makes a copy of a (as will the x = a + [n] idiom).

Bart> I am building a binary tree where each node is a list. the two
Bart> children are the parent list + 1 and the parent list + 2.

You might consider creating each node as

left = [parent, 1]
right = [parent, 2]

You thus wind up with a nested set of two-element nodes, e.g.:

[]
[[], 1] [[], 2]
[[[], 1], 1] [[[], 1], 2] [[[], 2], 1] [[[], 2], 2]

where the left-hand side of each node is just a reference to the parent
node. Once the tree is built if you can flatten the resulting node lists to
generate lists which are more efficient for direct element access.

Again, this all depends on how big your trees are, what you do with them
once they are built, if you need to search the tree while building the tree,
etc.

Skip

 

[=?ISO-8859-1?Q?BJ=F6rn_Lindqvist?=]

Bart> #--------------------------------------------------
Bart> def addnumber(alist, num):
Bart> """ work around the inplace-ness of .append """
Bart> mylist = alist[:]
Bart> mylist.append(num)
Bart> return mylist
Bart> #--------------------------------------------------

Such an operation will be O(N**2), and thus expensive if performed
frequently on lists of moderate length. I've never been tempted to do this.

How can that be? Making a copy of a list is O(N), isn't it?

 

[skip]

Bart> #--------------------------------------------------
Bart> def addnumber(alist, num):
Bart> """ work around the inplace-ness of .append """
Bart> mylist = alist[:]
Bart> mylist.append(num)
Bart> return mylist
Bart> #--------------------------------------------------
BJörn> How can that be? Making a copy of a list is O(N), isn't it?

Yes, not enough sleep under my belt or caffeine in my system (*) when I
wrote those replies. addnumber is O(N). If you are building a binary tree
of M elements you're going to wind up with an O(N*M) or O(N**2) cost to
build the tree though. Actually, I think in the case of building the binary
tree you wind up with an O(N*log N) algorithm since you don't have to
traverse the entire set of nodes you've already built to find where to
insert the next one.

Skip

(*) It really sucks when someone's car alarm goes off at 4AM with no visual
indication when it's about -5F outside and you have to actually go outside
to check and make sure it's not your car (only to find out it's the car
directly behind yours)...

S

 

[Alexander Schmolck]

Bart> why is that?

The a[:] operation makes a copy of a (as will the x = a + [n] idiom).

I'm pretty confident append itself (and a+[n]) are linear in N=len(a) since
the copying is linear and appending a single item in-place is constant time
(OTOH calling append N times to construct a list or tree of length N from
scratch is quadratic; I assume that is what you meant and also what the OP
seems to want to use it for, so not doing it this way is sound advice).

Bart> I am building a binary tree where each node is a list. the two
Bart> children are the parent list + 1 and the parent list + 2.

You might consider creating each node as

left = [parent, 1]
right = [parent, 2]

Or, if you don't need to mutate the tree ``left = (parent, 1)``. Tuples ought
to have a little less memory overhead.

'as

 

[Alexander Schmolck]

"Bart" == Bart Van Loon <[email protected]> writes:

Such an operation will be O(N**2),

Bart> why is that?

The a[:] operation makes a copy of a (as will the x = a + [n] idiom).

I'm pretty confident append itself (and a+[n]) are linear in N=len(a) since

Sorry -- I just see that I missed your other post.

'as

 

[skip]

as> I'm pretty confident append itself (and a+[n]) are linear in
as> N=len(a) ...

Yes, as I indicated in an earlier reply. The overall construction of his
data structure would be O(N**2) or O(N*log N). The latter is for binary
tree construction, but I didn't know what the OP was going to do with his
lists at the time I originally replied.

as> Or, if you don't need to mutate the tree ``left = (parent,
as> 1)``. Tuples ought to have a little less memory overhead.

Since at least 2.4, lists overallocate space for new entries proportional to
the current size of the list, so yes, tuples will be a bit friendlier,
certainly if your tree is very deep.

Skip