Re: in place-ness of list.append
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
Alexander Schmolck <[EMAIL PROTECTED]> writes: > [EMAIL PROTECTED] writes: > > > > "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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
[EMAIL PROTECTED] writes: > > "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 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
> "BJörn" == BJörn Lindqvist <[EMAIL PROTECTED]> writes: BJörn> On 2/5/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: >> 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. 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
On 2/5/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: > > 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? -- mvh Björn -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
> "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). 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
It was Mon, 5 Feb 2007 05:01:28 -0600, when [EMAIL PROTECTED] wrote: > > 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])) #--- -- regards, BBBart "Who can fathom the feminine mind?" -Calvin "I like `em anyway" -Hobbes -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: in place-ness of list.append
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 -- http://mail.python.org/mailman/listinfo/python-list
