confused about resizing array in Python

[Ruan]

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.

Therefore, for "memo[n] = fib_memo(n-1) + fib_memo(n-2)", the time it taks
is not at all constant. The larger the n grows, the more time this statement
takes.

Can anybody here familiar with the internal mechanism of python confirm
this?


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: confused about resizing array in Python

[Ruan]

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?



"Roel Schroeven" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> 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.
>
> --
> 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: Why doesn't my heapify work?

[Ruan]

Can't range go from larger to smaller?


"Diez B. Roggisch" <[EMAIL PROTECTED]> wrote in message 
news:[EMAIL PROTECTED]
> Dongsheng Ruan wrote:
>
>> 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]
>
> First of all, there is the module heapq that will just do it.
>
> And then you seem to misunderstand how the range-function works. range(m, 
> 1)
> will always be the empty list. See
>
> pydoc range
>
> for how it operates.
>
> Overall, your code is very unpythonic, to say the least. I suggest you 
> start
> reading the python tutorial first:
>
> http://docs.python.org/tut/
>
> Especially the looping techniques section:
>
> http://docs.python.org/tut/node7.html#SECTION00760
>
> Diez 


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Why doesn't my heapify work?

[Ruan]

I found out what is wrong.

You must give it a negative step, like range(10,1,-1)

But my code is not good enought for heapify.

I will try again.


"Ruan" <[EMAIL PROTECTED]> wrote in message 
news:[EMAIL PROTECTED]
> Can't range go from larger to smaller?
>
>
> "Diez B. Roggisch" <[EMAIL PROTECTED]> wrote in message 
> news:[EMAIL PROTECTED]
>> Dongsheng Ruan wrote:
>>
>>> 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]
>>
>> First of all, there is the module heapq that will just do it.
>>
>> And then you seem to misunderstand how the range-function works. range(m, 
>> 1)
>> will always be the empty list. See
>>
>> pydoc range
>>
>> for how it operates.
>>
>> Overall, your code is very unpythonic, to say the least. I suggest you 
>> start
>> reading the python tutorial first:
>>
>> http://docs.python.org/tut/
>>
>> Especially the looping techniques section:
>>
>> http://docs.python.org/tut/node7.html#SECTION00760
>>
>> Diez
>
> 


-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Ways to make a free variable local to a function?

[Yubin Ruan]

On 2018-04-15 13:31, Kirill Balunov wrote:
> 
> 
> 2018-04-15 10:58 GMT+03:00 Yubin Ruan :
> 
> [this is a bit late...]
> 
> Did you really have any benchmark for it? I know what you are doing but it
> seems to be a pre-mature optimization. If this really is the case, then we
> can
> optimize the Python interpreter.
> 
> 
> I don't know if you intentionally send this message privately to me and not to
> the entire python-list. If it was a mistake, post it there and I will answer
> there too.

Sorry I mistakenly hit the 'Reply' button instead of 'Group-reply'.
 
> Yes I've measured:
> 
> 
> def func(numb):
>     res = []
>     for i in range(numb):
>         res.append(int(i) + float(i))
>     return res
> 
> def func_local(numb, _int = int, _float = float):
>     res = []
>     for i in range(numb):
>         res.append(_int(i) + _float(i))
>     return res

Wouldn't this kind of things better be (implicitly) used in the Python
interpreter instead of in this kind of hand-optimized code? That looks
strange.

Nevertheless, if need be, I would opt for that 'static-declared' approach you
described earlier, which give semantic hint on the optimization used.

Thanks,
Yubin
 
> %timeit func(10)
> 
> 85.8 ms ± 2.47 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
> 
> 
> %timeit func_local(10)
> 
> 72.2 ms ± 892 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
> 
> So in the tight loop it is 16% faster.
-- 
https://mail.python.org/mailman/listinfo/python-list

python regex: variable length of positive lookbehind assertion

[Yubin Ruan]

Hi everyone, 
I am struggling writing a right regex that match what I want:

Problem Description:

Given a string like this:

>>>string = "false_head aaa bbb false_tail \
 true_head some_text_here ccc ddd eee 
true_tail"

I want to match the all the text surrounded by those " ",
but only if those " " locate **in some distance** behind "true_head". 
That is, I expect to result to be like this:

>>>import re
>>>result = re.findall("the_regex",string)
>>>print result
["ccc","ddd","eee"]

How can I write a regex to match that?
I have try to use the **positive lookbehind assertion** in python regex,
but it does not allowed variable length of lookbehind.

Thanks in advance,
Ruan
-- 
https://mail.python.org/mailman/listinfo/python-list

Re: python regex: variable length of positive lookbehind assertion

[Yubin Ruan]

On Wednesday, June 15, 2016 at 12:18:31 PM UTC+8, Lawrence D’Oliveiro wrote:
> On Wednesday, June 15, 2016 at 3:28:37 PM UTC+12, Yubin Ruan wrote:
> 
> > I want to match the all the text surrounded by those " ",
> 
> You are trying to use regex (type 3 grammar) to parse HTML (type 2 grammar) 
> <https://en.wikipedia.org/wiki/Formal_grammar#The_Chomsky_hierarchy>?
> 
> No can do 
> <http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454>.


Yes. I think you are correct. Thanks.
-- 
https://mail.python.org/mailman/listinfo/python-list

Multiline parsing of python compiler demistification needed

[Yubin Ruan]

Hi, everyone, I have some problem understand the rule which the python compiler 
use to parsing the multiline string.

Consider this snippet:

str_1 = "foo"
str_2 = "bar"

print "A test case" + \
   "str_1[%s] " + \
   "str_2[%s] " % (str_1, str_2)

Why would the snippet above give me an "TypeError: not all arguments converted 
during string formatting" while the one below not ?

print "A test case" + \
   "str_1[%s] " % str1

Obviously the first snippet have just one more line and one more argument to 
format than the second one. Isn't that unreasonable ? I couldn't find any clue 
about that. Anyone help ?

I am using python 2.7.6

Also, I know the **Pythonic** way to play with multiline, which would be using 
triple quote or a pair of parenthesis to surround the multiline string to make 
it a **online** string. You don't have to show code in that respect.

Thanks in advance!

Ruan.
-- 
https://mail.python.org/mailman/listinfo/python-list

python3: why writing to socket require bytes type while writing to a file require str ?

[Yubin Ruan]

Hi,
I'm migrating my code to python3 now and find it hard to deal with python's 
'str' and 'bytes' type. It's kind of painful.
One thing I find really confusing is that, writing to a socket requires 
argument to be of type 'bytes'(otherwise python throw 'str does not support 
buffer interface...' exception), while writing to a file requires argument to 
be of type 'str'. Why is that? In standard UNIX interface, everything is file, 
which mean that writing to a socket is the same as writing to a normal file. 
This is true is python2. But thing doesn't seem to work in python 3.
Does anyone have idea why is this in python3 ?
In my understanding, writing to a file would requires that everything be 
written byte by byte. So writing objects of type 'bytes' to socket makes sense. 
But, how could python write to file using unicode(type 'str')? Does python 
encode 'str'(Unicode) automatically before writing things to file? If it's 
true, then why can't it do that automatic encoding when I trying to write a 
'str' to socket ?

Regards,
Ruan
-- 
https://mail.python.org/mailman/listinfo/python-list

How can I create a linked list in Python?

[Dongsheng Ruan]

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

Re: How can I create a linked list in Python?

[Dongsheng Ruan]

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 to pass arguments to the function embedded in the timeit.Timer()

[Dongsheng Ruan]

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

What is the dummy statement that do nothing in Python?

[Dongsheng Ruan]

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

Re: What is the dummy statement that do nothing in Python?

[Dongsheng Ruan]

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

need help on a data structure problem

[Dongsheng Ruan]

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: confused about resizing array in Python

[Dongsheng Ruan]

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

Re: confused about resizing array in Python

[Dongsheng Ruan]

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

what is wrong with my python code?

[Dongsheng Ruan]

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

Why doesn't my heapify work?

[Dongsheng Ruan]

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

Re: Download

[Yubin Ruan]

On Mon, Jun 05, 2017 at 05:16:55PM +0200, Maria Alonso-Martirena wrote:
> Good morning,
> 
> 
> 
> You asked me to subscribe before writing to you and i've already done so. I
> need your help: I’ve just downloaded Python for Windows (versión 3.6.1.).
> However, when I try to open it, it just says “modify”, “repair” or
> “uninstall”.
> 
> How can I solve this problem? Why is it not working correctly?

A quick search of "Python Tutorial" in Youtube will be helpful.


--
Yubin
-- 
https://mail.python.org/mailman/listinfo/python-list