[Tutor] A fun puzzle

[Dick Moores]

At 11:49 AM 8/23/2007, Kent Johnson wrote:
>Dick Moores wrote:
>>>Two reasons. First, looking up a name that is local to a function 
>>>is faster than looking up a global name. To find the value of 
>>>'str', the interpreter has to look at the module namespace, then 
>>>the built-in namespace. These are each dictionary lookups. Local 
>>>values are stored in an array and accessed by offset so it is much faster.
>>Wow, what DON'T you understand?
>
>Lots, actually :-) There is a whole 'nother tier or two of Python 
>expert above me that I can't touch. I just parrot back what I hear 
>them saying. :-)
>
>>Please explain "accessed by offset".
>
>IIUC an array is allocated on the call stack to hold references to 
>the local variables. (Anticipating you next question: 
>http://en.wikipedia.org/wiki/Stack_frame) To get the value of the 
>local variable the runtime just has to look up the correct entry in 
>the array. The bytecode has the offset into the array. This is very 
>quick - an indexed lookup.
>
>Normal attribute access such as a module or builtin has to read the 
>value out of a dict which is much more expensive, even with Python's 
>optimized dicts.

Thank you. Nice parroting. :-)


>>This time I added "xrange(10, end, 10)" and did the timing using 
>>the template in the timeit module:
>>template = """
>>def inner(_it, _timer):
>>      _t0 = _timer()
>>      from itertools import chain
>>      end = 1000000
>>      for _i in _it:
>>          for x in chain(xrange(1, end, 10), xrange(2, end, 10),
>>          xrange(3, end, 10), xrange(4, end, 10), xrange(5, end, 10),
>>          xrange(6, end, 10), xrange(7, end, 10), xrange(8, end, 10),
>>          xrange(9, end, 10), xrange(10, end, 10)):
>>              pass
>>      _t1 = _timer()
>>      return _t1 - _t0
>>"""
>>This gets always close to 71 msec per loop.
>>
>>template = """
>>def inner(_it, _timer):
>>      _t0 = _timer()
>>      end = 1000000
>>      for _i in _it:
>>          for x in xrange(end):
>>              pass
>>      _t1 = _timer()
>>      return _t1 - _t0
>>"""
>>This gets always close to 84 msec per loop.
>>So they're not the same! And yours is the faster one! Because 
>>itertools.chain() is written in C, I suppose.
>
>That is very strange. I did a simple timer with time.time() and 
>found that my original (1-9) version was consistently a little 
>slower than the simple xrange(). And xrange is written in C too, and 
>the chain version adds a layer over xrange. You should check your 
>code carefully, that is a very surprising result.

Yes, surprising. But the templates pasted above are exactly what I 
used in 2 copies of timeit.py. I don't know what to check. Can you 
see what's wrong?  I just ran both of those again, with very similar results.

Following your lead I've now done some timing using time.time():

==============================================================
from __future__ import division
from itertools import chain
import time

end = 1000000
timeTotal = 0
for c in range(100):
     timeStart = time.time()
     for x in chain(xrange(1, end, 10), xrange(2, end, 10),
     xrange(3, end, 10), xrange(4, end, 10), xrange(5, end, 10),
     xrange(6, end, 10), xrange(7, end, 10), xrange(8, end, 10),
     xrange(9, end, 10), xrange(10, end, 10)):
         pass

     timeEnd = time.time()
     timeElapsed = timeEnd - timeStart
     timeTotal += timeElapsed
avgTime = timeTotal/c
print "with chain avgTime was %.4g seconds" % avgTime

"""
results of 5 runs:
with chain avgTime was 0.2072 seconds
with chain avgTime was 0.1916 seconds
with chain avgTime was 0.1913 seconds
with chain avgTime was 0.1921 seconds
with chain avgTime was 0.1915 seconds
(avg is 0.1947 seconds)
"""
=================================================

=================================================
from __future__ import division
import time
end = 1000000
timeTotal = 0
for c in range(100):
     timeStart = time.time()
     for x in xrange(end):
         pass
     timeEnd = time.time()
     timeElapsed = timeEnd - timeStart
     timeTotal += timeElapsed
avgTime = timeTotal/c
print "no chain avgTime was %.4g seconds" % avgTime

"""
results of 5 runs:
no chain avgTime was 0.2104 seconds
no chain avgTime was 0.2109 seconds
no chain avgTime was 0.1946 seconds
no chain avgTime was 0.1948 seconds
no chain avgTime was 0.1946 seconds
(avg is 0.2011 seconds)
"""
=====================================================
When I ran the above 2 scripts, I alternated between them. Don't 
really see that one is decisively faster than the other.

Dick



======================================
                       Bagdad Weather
<http://weather.yahoo.com/forecast/IZXX0008_f.html>