How naive is Python?

[Roy Smith]

In article <huCqh.1309$O02.170 at newssvr11.news.prodigy.net>,
 John Nagle <nagle at animats.com> wrote:

>     How naive (in the sense that compiler people use the term)
> is the current Python system?  For example:
> 
> 	def foo() :
> 	    s = "This is a test"
> 	    return(s)
> 
>  s2 = foo()
> 
> How many times does the string get copied?

All of those just move around pointers to the same (interned) string.

> How about this?
> 
> 	kcount = 1000
> 	s = ''
> 	for i in range(kcount) :
> 	    s += str(i) + ' '
> 
> Is this O(N) or O(N^2) because of recopying of "s"?

This is a well-known (indeed, the canonical) example of quadratic behavior 
in Python.  The standard solution is to store all the strings (again, 
really just pointers to the strings) in a list, then join all the elements:

  temp = []
  for i in range (1000):
    temp.append (str(i))
  s = "".join (temp)

That ends up copying each string once (during the join operation), and is 
O(N) overall.