On 15/04/2013 02:14, Steven D'Aprano wrote:
On Sun, 14 Apr 2013 17:44:28 -0700, Mark Janssen wrote:
On Sun, Apr 14, 2013 at 5:29 PM, Steven D'Aprano
<steve+comp.lang.pyt...@pearwood.info> wrote:
On Sun, 14 Apr 2013 12:06:12 -0700, Mark Janssen wrote:
cleaned=''
for c in myStringNumber:
if c != ',':
cleaned+=c
int(cleaned)
....due to being an O(N**2) algorithm.
What on earth makes you think that is an O(n**2) algorithm and not O(n)?
Strings are immutable. Consider building up a single string from four
substrings:
s = ''
s += 'fe'
s += 'fi'
s += 'fo'
s += 'fum'
Python *might* optimize the first concatenation, '' + 'fe', to just reuse
'fe', (but it might not). Let's assume it does, so that no copying is
needed. Then it gets to the second concatenation, and now it has to copy
characters, because strings are immutable and cannot be modified in
place.
Actually, I believe that CPython is optimised to modify strings in place
where possible, so that the above would surprisingly turn out to be
O(n). See the following thread where I asked about this:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/990a695fe2d85c52
(Sorry for linking to Google Groups. Does anyone know of a better c.l.p.
web archive?)
--
http://mail.python.org/mailman/listinfo/python-list
