Why doesn't my heapify work?
I want to turn an Array into a heap, but my code just doesn't work: no change after execution. A=[3,5,4,9,6,7] m=len(A)-1 for i in range(m,1): t=(i-1)/2 if A[i]>A[t]: A[i],A[t]=A[t],A[i] -- http://mail.python.org/mailman/listinfo/python-list
what is wrong with my python code?
I got feed back saying" list object is not callable". But I can't figure out what is wrong with my code. A=[3,5,4,9,6,7] l=len(A)-1 for i in range(l): print A(i) -- http://mail.python.org/mailman/listinfo/python-list
Re: confused about resizing array in Python
This seems to be clever to use reference for list. Is it unique to Python? How about the traditional programming languages like C, Pascal or C++? "Roel Schroeven" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Dongsheng Ruan schreef: >> "Roel Schroeven" <[EMAIL PROTECTED]> wrote in message >> news:[EMAIL PROTECTED] >>> Ruan schreef: >>>> Then how about Python's list? >>>> >>>> What is done exactly when list.append is executed? >>>> >>>> For list, is there another larger list initialized and the contents >>>> from the old list is copied to it together with the new appended list? > >>> I'm not sure, but I think each time the list needs to grow, it doubles >>> in size. That leaves room to add a number of elements before the >>> allocated space needs to grow again. It's a frequently used approach, >>> since it is quite efficient and the memory needed is never double the >>> amount of memory strictly needed for the elements of the list. > > > You mentioned "it doubles in size". > > > > Are you saying that a new double sized array is allocated and the > > contents of the old list is copied there? > > > > Then the old list is freed from memory? > > > > It seems to be what is called amortized constant. > > > > Say the list size is 100, before it is fully used, the append takes > > O(1) time. But for the 101th element, the time will be O(100+1), and > > then from then on, it is O(1) again. Like John Machin said in the > > previous post? > > > > But on average, it is O(1). I guess this is the amortized constant. > > Isn't it? > > I think so, more or less, but as I said I'm not entirely sure about how > Python handles lists. > > One thing to keep in mind is that the list (like any other Python data > structure) doesn't store the objects themselves; it only stores references > to the objects. If the list needs to be copied, only the references are > copied; the objects themselves can stay where they are. For small objects > this doesn't make much difference, but if the objects grow larger it gets > much more efficient if you only have to move the references around. > > -- > If I have been able to see further, it was only because I stood > on the shoulders of giants. -- Isaac Newton > > Roel Schroeven -- http://mail.python.org/mailman/listinfo/python-list
Re: confused about resizing array in Python
You mentioned "it doubles in size".
Are you saying that a new double sized array is allocated and the contents
of the old list is copied there?
Then the old list is freed from memory?
It seems to be what is called amortized constant.
Say the list size is 100, before it is fully used, the append takes O(1)
time. But for the 101th element, the time will be O(100+1), and then from
then on, it is O(1) again. Like John Machin said in the previous post?
But on average, it is O(1). I guess this is the amortized constant. Isn't
it?
"Roel Schroeven" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> Ruan schreef:
>> "Roel Schroeven" <[EMAIL PROTECTED]> wrote:
>>> Ruan schreef:
My confusion comes from the following piece of code:
memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
I used to think that the time complexity for this code is O(n) due to
its use of memoization.
However, I was told recently that in Python, dictionary is a special
kind of array and to append new element to it or to resize it, it is in
fact
internally inplemented by creating another array and copying the old
one to
it and append a new one.
>
>>> That's not correct. Python dictionaries are highly optimized and I
>>> believe the time complexity is amortized constant (i.e. O(1)) for both
>>> insertions and lookups.
>
>> Then how about Python's list?
>>
>> What is done exactly when list.append is executed?
>>
>> For list, is there another larger list initialized and the contents from
>> the
>> old list is copied to it together with the new appended list?
>
> I'm not sure, but I think each time the list needs to grow, it doubles in
> size. That leaves room to add a number of elements before the allocated
> space needs to grow again. It's a frequently used approach, since it is
> quite efficient and the memory needed is never double the amount of memory
> strictly needed for the elements of the list.
>
> You can always study the source code for all gory details of course.
>
> --
> If I have been able to see further, it was only because I stood
> on the shoulders of giants. -- Isaac Newton
>
> Roel Schroeven
--
http://mail.python.org/mailman/listinfo/python-list
need help on a data structure problem
Not quite related with Python. But my Data Structure course is experiemented on python and there is no data structure group, So I have to post here: Write a procedure (in pseudocode!) to increase the number of buckets in a (closed) hash table. Analyze its time and space complexity. -- http://mail.python.org/mailman/listinfo/python-list
Re: What is the dummy statement that do nothing in Python?
Yes, that's just what I want. Thanks! - Original Message - From: Analog Kid To: Dongsheng Ruan Cc: python-list@python.org Sent: Wednesday, January 31, 2007 12:04 PM Subject: Re: What is the dummy statement that do nothing in Python? hey dongsheng: not too sure what you are looking for ... but i guess a simple "pass" statement should do it ... if a > b: pass hth, -ajay On 1/31/07, Dongsheng Ruan <[EMAIL PROTECTED]> wrote: I remember that in python there is some kind of dummy statement that just holds space and does nothing. I want it to hold the place after a something like if a>b: do nothing I can't just leave the space blank after if statement because there will be error message. Does anybody know what to insert there? Thanks! -- http://mail.python.org/mailman/listinfo/python-list -- BBQ - "Spare (My) Ribs" being contemplated -- http://mail.python.org/mailman/listinfo/python-list
What is the dummy statement that do nothing in Python?
I remember that in python there is some kind of dummy statement that just holds space and does nothing. I want it to hold the place after a something like if a>b: do nothing I can't just leave the space blank after if statement because there will be error message. Does anybody know what to insert there? Thanks! -- http://mail.python.org/mailman/listinfo/python-list
How to pass arguments to the function embedded in the timeit.Timer()
Hi Does anybody know how to pass multiple arguments to the function tested in timeit.timer() in python? I googled and found how to pass one argument: x=1 mytime = timeit.Timer( setup="from Createlst import createlst", stmt= "createlst(%s)"%(x) ) But how can I extend it to two or more arguments? Like this: p1=createlst.createlst(1) p2=createlst.createlst(1) mytime = timeit.Timer(setup="from list_concat_copy import list_concat_copy", stmt="list_concat_copy.list_concat_copy(%x,%y)"%p1,p2 ) I don't know how to end the timeit.Timer. Should it be (%x,%y)"%p1,p2 or (%x,%y)"%p1,%p2 or (%x,%y)"(%p1%p2) . I tried and none worked. I just got error message like global variable "A' not defined. Can anybody help? Thanks! -- http://mail.python.org/mailman/listinfo/python-list
Re: How can I create a linked list in Python?
Thanks for your kindly help. I am new CS student taking datat structure and algorithms with AHO's book with the same title. The book is done in Pascal, which might be an outdated language. However, my instructor probably wants us to understand the list ADT better by not using the built in list in Python. "Gary Herron" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > Dongsheng Ruan wrote: >> with a cell class like this: >> >> #!/usr/bin/python >> >> import sys >> >> class Cell: >> >> def __init__( self, data, next=None ): >> self.data = data >> self.next = next >> >> def __str__( self ): >> return str( self.data ) >> >> def echo( self ): >> print self.__str__() > If you really want a list (as Python defines a list - with all the > methods) then you should use Python's lists. They are quite efficient and > convenient: > > l = [Cell(1), Cell(2), Cell(3)] > > However, if what you want is each cell to refer to a next cell (which > after all is what a linked list does), then you already have it with the > next attribute. (In other languages you might implement 'next' as a > pointer, while in Python we call it a reference -- but it amounts to the > same thing.) Create it this way: > > c = Cell(3) > b = Cell(2, c) a = Cell(1, b) > > or > > a = Cell(1, Cell(2, Cell(3))) > > However, I'll repeat this: The concept of a linked list if a figment of > languages with pointer data types. Python abstracts that by allowing > attributes to contain references to other objects. However, you're much > better off if you can use Python's list data structure rather than try to > emulate an outdated concept in a modern language. > > Gary Herron > > > -- http://mail.python.org/mailman/listinfo/python-list
How can I create a linked list in Python?
with a cell class like this: #!/usr/bin/python import sys class Cell: def __init__( self, data, next=None ): self.data = data self.next = next def __str__( self ): return str( self.data ) def echo( self ): print self.__str__() -- http://mail.python.org/mailman/listinfo/python-list
