469,284 Members | 2,485 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,284 developers. It's quick & easy.

in place-ness of list.append

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!

--
regards,
BBBart

"Someday I'll write my own philosophy book." -Calvin
Feb 5 '07 #1
11 1336
Bart Van Loon wrote:
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
Feb 5 '07 #2

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

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

Bartany 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
Feb 5 '07 #3
Bart Van Loon wrote:
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)......

--
Robin Becker

Feb 5 '07 #4
It was Mon, 05 Feb 2007 11:00:50 GMT, when Kent Johnson wrote:
Bart Van Loon wrote:
>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!

--
regards,
BBBart

"Who can fathom the feminine mind?" -Calvin "I like `em anyway" -Hobbes
Feb 5 '07 #5
It was Mon, 5 Feb 2007 05:01:28 -0600, when sk**@pobox.com wrote:
>
Bart#--------------------------------------------------
Bartdef addnumber(alist, num):
Bart """ work around the inplace-ness of .append """
Bart mylist = alist[:]
Bart mylist.append(num)
Bart return mylist
Bart#--------------------------------------------------

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

Bartany 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]))
#-----------------------------------------------------------

--
regards,
BBBart

"Who can fathom the feminine mind?" -Calvin "I like `em anyway" -Hobbes
Feb 5 '07 #6
>>>>"Bart" == Bart Van Loon <bb****@inGen.bewrites:
>Such an operation will be O(N**2),
Bartwhy is that?

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

BartI am building a binary tree where each node is a list. the two
Bartchildren 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
Feb 5 '07 #7
On 2/5/07, sk**@pobox.com <sk**@pobox.comwrote:
>
Bart#--------------------------------------------------
Bartdef 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?

--
mvh Björn
Feb 5 '07 #8
>>>>"BJörn" == BJörn Lindqvist <bj*****@gmail.comwrites:

BJörnOn 2/5/07, sk**@pobox.com <sk**@pobox.comwrote:
>
Bart#--------------------------------------------------
Bartdef addnumber(alist, num):
Bart""" work around the inplace-ness of .append """
Bartmylist = alist[:]
Bartmylist.append(num)
Bartreturn 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 temptedto
do this.
BJörnHow 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
Feb 5 '07 #9
sk**@pobox.com writes:
>>>"Bart" == Bart Van Loon <bb****@inGen.bewrites:
>Such an operation will be O(N**2),

Bartwhy 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).
BartI am building a binary tree where each node is a list. the two
Bartchildren 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
Feb 5 '07 #10
Alexander Schmolck <a.********@gmail.comwrites:
sk**@pobox.com writes:
>>>>"Bart" == Bart Van Loon <bb****@inGen.bewrites:
>Such an operation will be O(N**2),
Bartwhy 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
Feb 5 '07 #11

asI'm pretty confident append itself (and a+[n]) are linear in
asN=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.

asOr, if you don't need to mutate the tree ``left = (parent,
as1)``. 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
Feb 5 '07 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Andrew Morgan | last post: by
2 posts views Thread by Alessandro Rossi | last post: by
10 posts views Thread by Water Cooler v2 | last post: by
2 posts views Thread by peter.mcclymont | last post: by
7 posts views Thread by peter.mcclymont | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.