In article <[EMAIL PROTECTED]>,
John Nagle <[EMAIL PROTECTED]> 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.
--
http://mail.python.org/mailman/listinfo/python-list
