[Tutor] Logical error?

[Steven D'Aprano]

On Sat, May 03, 2014 at 11:53:27AM +1000, Steven D'Aprano wrote:

> [...]
> > fullPath = []   # declare (initially empty) lists
> > truncPath = []
> > 
> > with codecs.open('/var/log/rsyncd.log', 'r') as rsyncd_log:
> >     for line in rsyncd_log.readlines():
> >         fullPath += [line.decode('utf-8', 'ignore').strip()]
> 
> A small note about performance here. If your log files are very large 
> (say, hundreds of thousands or millions of lines) you will find that 
> this part is *horribly horrible slow*. There's two problems, a minor and 
> a major one.

Ah, actually I was mistaken about that. I forgot that for built-in 
lists, += augmented assignment is equivalent to calling list.extend(), 
so it actually does make the modifications in place. So I was wrong to 
say:

> The big problem is this:
> 
>     fullPath += [line.decode('utf-8', 'ignore').strip()]
> 
> which is an O(N**2) algorithm.

This would be true, if += were implemented in terms of list addition. 
But it isn't, it is implemented as list.extend.



-- 
Steven