[Tutor] Efficiency?

[Blake Winton]

Hee-Seng Kye wrote:
> Hi, I was reading you e-mail again the other day, and I realized that I 
> wanted to ask you about efficiency of function.

Sure.  (I've renamed the functions so that I can talk about them a 
little easier.)  (And I think I'm going to Cc: the tutor list, since 
re-reading my email, I'm touching on some points that other people might 
find useful...  And hey, maybe the other tutors will time some of these 
functions, and let us know which actually is faster, and why one might 
be faster than another.)

> You said the function below is much less efficient though shorter, and I 
> discovered that the one below is significantly slower, as you said.  Why 
> is that?  I thought list comprehension is usually faster than 'for' 
> loops.  Is it because the one below uses 'reduce' function?  The 
> function above is even appending to an empty list, which I thought slow 
> things down, and yet much faster.

Well, we can always rewrite the list comprehension as a for loop, which
will show us where the inefficiency lies.

So this:
 >> >>> def findSmallestNumber1(r):
 >> ...   return [i for i in range(len(r)) if r[i] == reduce( min, r ) ]

turns into:
 >>> def findSmallestNumber2(r):
...   retval = []
...   for i in range( len( r ) ):
...     if r[i] == reduce( min, r ):
...       retval.append(i)
...   return retval

The for-loop version of this will be a little slower than the 
list-comprehension version, but they're both doing much more work than 
the first version I sent you.  How are they doing more work, you ask? 
Well, the reduce function has to go through every element of the list 
every time it's called to find the minimum.  ("reduce(min,r)" basically 
finds the smallest element in the list "r".)

So the code in findSmallestNumber1 and 2 goes through the whole list 
once (the "for i in range( len( r ) ):" loop), and then "n" more times 
(the "reduce( min, r )" call), where "n" is the number of elements in 
the loop.  If we think of going through the loop once as "n", then this 
code will go through it "n + n*n" (or "n + n^2", or "n^2 + n") times, 
which I'll write as O(n^2 + n).  (Do you know Big-O Notation?  Maybe you 
call it "The Order of a function".  It's a way of describing how fast 
your code will run, given large inputs.  I'll show you another example 
below.  If you're impatient, googling for "Big-O Notation" gives you a 
lot of hits, all of which seem to be on-topic.)

Now, calling reduce runs through the list at the speed of C, which is 
faster than doing it at the speed of Python, but it's still going to be 
quite slow if your loop is large.  And even worse, the minimum number 
isn't going to change between one run and the next, so we should really 
only calculate it once, and store it in a variable, which we can call, 
say "s".

And that's essentially what this code does:
 >> >>> def findSmallestNumber3(r):
 >> ...   s = reduce( min, r )
 >> ...   return [i for i in range(len(r)) if r[i] == s ]

or its for-loop version:
 >>> def findSmallestNumber3(r):
...   retval = ""
...   s = reduce( min, r )
...   for i in range(len(r)):
...     if r[i] == s:
...       retval.append(i)
...   return retval

This will run through the loop once (the "reduce( min, r )" call), and 
then once more (the "for i in range(len(r)):" loop), for a total of 2 
times, which I'm going to write as O(2n).

> When you say the one below is a little more efficient than the above, do 
> you mean that the one below is more clear to read?  Or do you mean the 
> one below runs a little faster?  I don't understand how the one above is 
> different from the one below, except for a matter of notation.

It should run a little faster.  Perhaps not a lot faster, perhaps a lot 
faster.  Intuitively, I think it would depend on the length of the list. 
  If you time it, let me know.

And do you understand why it should run faster?

And let's go back to the first example:
 >> >>> def findSmallestNumber0( r ):
 >> ...   indices = []
 >> ...   for index in range(len(r)):
 >> ...     if len(indices) == 0 or r[index] < r[ indices[0] ]:
 >> ...       indices = [index]
 >> ...     elif r[index] == r[ indices[0] ]:
 >> ...       indices.append( index )
 >> ...   return indices

So, this runs through the loop once (the "for index in range(len(r)):" 
loop), and...  That's all.  So it will be O(n), and therefore should be 
the fastest of all.  (It might not be, but that depends on some other 
factors, which I could list out for you if you want.)

> Thanks again.  As I'm new to programming, I thought that shorter codes 
> run faster than longer ones (though could be less easier to read), but 
> the two versions of your function alerted me that it's not necessarily 
> true.

I hope I didn't confuse you too much, with all this theoretical stuff ;)
Figuring out how quickly a program will run is a very tricky business, 
which is why you have to time stuff before and after any change if 
you're trying to improve performance.  (I've spent 12 years writing 
programs professionally, (and probably another 5 before that writing 
them in school,) so I've developed a sense of what will run fast, and 
what won't.  You will too, over time.  And in the meantime, using Big-O 
notation can give you a hint as to what might run faster.

O(n^2 + n) is slower than O(2n) is slower than O(n).

Later,
Blake.