[Tutor] Efficiency and speed

[Steven D'Aprano]

On Sat, 20 Mar 2010 03:41:11 am James Reynolds wrote:

> I've still been working towards learning the language, albeit slowly
> and I've been working on a project that is somewhat intense on the
> numerical calculation end of things.
>
> Running 10,000 trials takes about 1.5 seconds and running 100,000
> trials takes 11 seconds. Running a million trials takes about 81
> seconds or so. I don't think 1M trials is needed for accuracy, but
> 100K probably is.

That's 15 microseconds per trial. Why do you think that's necessarily 
slow? How much work are you doing per trial?


> I've made a few other optimizations today that I won't be able to
> test until I get home, but I was wondering if any of you could give
> some general pointers on how to make python run a little more
> quickly.

Read this:
http://www.python.org/doc/essays/list2str.html

Google on "Python optimizations".

And you can watch this talk from the recent Python conference:
http://pycon.blip.tv/file/3322261/

Unfortunately the video is only available as a 1GB file, so I haven't 
watched it myself. But if you have a fast Internet link with lots of 
quota, go ahead.

[snip]
> def mcrange_gen(self, sample):#, lensample):
>     lensample = len(sample) # this section is just for speed. All of
> > these are renames from the globals to bring calc times down at the
> > expense of memory. I haven't tested these yet.
>
>     nx2 = self.nx1
>     nx2_append = nx2.append
>     nx2_sort = nx2.sort
>     nx2_reverse = nx2.reverse
>     nx2_index = nx2.index
>     nx2_remove = nx2.remove

All this becomes white noise. That's the problem with optimizations, 
particularly micro-optimizations: so often they make the code less 
readable.

Unless you have profiled your code and determined that these 
micro-optimizations make a significant difference, I'd say drop them, 
they're not worth it. This sort of micro-optimization is the last thing 
you should be adding.


>     for s in range(lensample):
>         q = sample[s] #takes the next randomly generated number from
> > the sample list
>         nx2_append(q) # and appends it to nx list.
>         nx2_sort() # and sorts it in place
>         nx2_reverse() # reverses the list, because this was the
> > original order
>         i = nx2_index(q) #get the index of that element
>         nx2_remove(q) # and remove the element.
>         yield i # send the position of that element back to the main
> > program.

Your naming conventions are ... weird. "s" for an integer index, "q" for 
a sample -- what's with that? And what's nx1 and nx2?

Writing comments is a good thing, but only when the comments actually 
add something to the code. Nearly every one of the above comments is 
useless. For instance, you write:

nx2_append(q) # and appends it to nx list.

Really? Calling "append" appends? Who would have guessed!

nx2_sort() # and sorts it in place

Sort sorts. Wow.

I trust I've made my point. There's no need to repeat the code in plain 
English as a comment. It just becomes noise.

Since s is never used except to get the sample, I'd do this:

nx = self.nx1  # This is more a typing optimization than for speed.
for q in sample:
    nx.append(q)
    nx.sort(reverse=True)
    i = nx.index(q)
    nx.remove(q)
    yield i

Now, let's look at what happens in the first four lines of the loop.

Appending to a list is fast. You almost certainly don't need to care 
about that.

Sorting is fast-ish. Python's sort is amazingly fast, as far as sorts 
go, but sorting is a naturally expensive operation, and you don't sort 
the data once, you sort it every time through the loop. Tick this as 
something that *maybe* you want to get rid of.

index() is an O(N) operation -- slow but not painfully slow. Unless your 
list is short, this is another "maybe" to remove.

remove() is another expensive operation. Unless your list is very short, 
this is something else you want to avoid when possible.



-- 
Steven D'Aprano