How to use timeit module
If you want to use
timeit in an interactive Python session, there are two convenient options:
Use the IPython shell. It features the convenient
In : def f(x): ...: return x*x ...: In : %timeit for x in range(100): f(x)100000 loops, best of 3: 20.3 us per loop
In a standard Python interpreter, you can access functions and other names you defined earlier during the interactive session by importing them from
__main__in the setup statement:
def f(x): return x * x import timeit timeit.repeat("for x in range(100): f(x)", "from __main__ import f", number=100000)[2.0640320777893066, 2.0876040458679199, 2.0520210266113281]
The way timeit works is to run setup code once and then make repeated calls to a series of statements. So, if you want to test sorting, some care is required so that one pass at an in-place sort doesn't affect the next pass with already sorted data (that, of course, would make the Timsort really shine because it performs best when the data already partially ordered).
Here is an example of how to set up a test for sorting:
import timeit setup = '''import randomrandom.seed('slartibartfast')s = [random.random() for i in range(1000)]timsort = list.sort'''print min(timeit.Timer('a=s[:]; timsort(a)', setup=setup).repeat(7, 1000))0.334147930145
Note that the series of statements makes a fresh copy of the unsorted data on every pass.
Also, note the timing technique of running the measurement suite seven times and keeping only the best time -- this can really help reduce measurement distortions due to other processes running on your system.
Those are my tips for using timeit correctly. Hope this helps :-)
I'll let you in on a secret: the best way to use
timeit is on the command line.
On the command line,
timeit does proper statistical analysis: it tells you how long the shortest run took. This is good because all error in timing is positive. So the shortest time has the least error in it. There's no way to get negative error because a computer can't ever compute faster than it can compute!
So, the command-line interface:
%~> python -m timeit "1 + 2"10000000 loops, best of 3: 0.0468 usec per loop
That's quite simple, eh?
You can set stuff up:
%~> python -m timeit -s "x = range(10000)" "sum(x)"1000 loops, best of 3: 543 usec per loop
which is useful, too!
If you want multiple lines, you can either use the shell's automatic continuation or use separate arguments:
%~> python -m timeit -s "x = range(10000)" -s "y = range(100)" "sum(x)" "min(y)"1000 loops, best of 3: 554 usec per loop
That gives a setup of
x = range(1000)y = range(100)
If you want to have longer scripts you might be tempted to move to
timeit inside a Python script. I suggest avoiding that because the analysis and timing is simply better on the command line. Instead, I tend to make shell scripts:
SETUP=" ... # lots of stuff " echo Minmod arr1 python -m timeit -s "$SETUP" "Minmod(arr1)" echo pure_minmod arr1 python -m timeit -s "$SETUP" "pure_minmod(arr1)" echo better_minmod arr1 python -m timeit -s "$SETUP" "better_minmod(arr1)" ... etc
This can take a bit longer due to the multiple initialisations, but normally that's not a big deal.
But what if you want to use
timeit inside your module?
Well, the simple way is to do:
def function(...): ...timeit.Timer(function).timeit(number=NUMBER)
and that gives you cumulative (not minimum!) time to run that number of times.
To get a good analysis, use
.repeat and take the minimum:
You should normally combine this with
functools.partial instead of
lambda: ... to lower overhead. Thus you could have something like:
from functools import partialdef to_time(items): ...test_items = [1, 2, 3] * 100times = timeit.Timer(partial(to_time, test_items)).repeat(3, 1000)# Divide by the number of repeatstime_taken = min(times) / 1000
You can also do:
timeit.timeit("...", setup="from __main__ import ...", number=NUMBER)
which would give you something closer to the interface from the command-line, but in a much less cool manner. The
"from __main__ import ..." lets you use code from your main module inside the artificial environment created by
It's worth noting that this is a convenience wrapper for
Timer(...).timeit(...) and so isn't particularly good at timing. I personally far prefer using
Timer(...).repeat(...) as I've shown above.
There are a few caveats with
timeit that hold everywhere.
Overhead is not accounted for. Say you want to time
x += 1, to find out how long addition takes:
"x = 0" "x += 1"10000000 loops, best of 3: 0.0476 usec per looppython -m timeit -s
Well, it's not 0.0476 µs. You only know that it's less than that. All error is positive.
So try and find pure overhead:
"x = 0" "" 100000000 loops, best of 3: 0.014 usec per looppython -m timeit -s
That's a good 30% overhead just from timing! This can massively skew relative timings. But you only really cared about the adding timings; the look-up timings for
xalso need to be included in overhead:
"x = 0" "x"100000000 loops, best of 3: 0.0166 usec per looppython -m timeit -s
The difference isn't much larger, but it's there.
Mutating methods are dangerous.
"x = *100000" "while x: x.pop()"10000000 loops, best of 3: 0.0436 usec per looppython -m timeit -s
But that's completely wrong!
xis the empty list after the first iteration. You'll need to reinitialize:
"x = *100000" "while x: x.pop()"100 loops, best of 3: 9.79 msec per looppython -m timeit
But then you have lots of overhead. Account for that separately.
"x = *100000" 1000 loops, best of 3: 261 usec per looppython -m timeit
Note that subtracting the overhead is reasonable here only because the overhead is a small-ish fraction of the time.
For your example, it's worth noting that both Insertion Sort and Tim Sort have completely unusual timing behaviours for already-sorted lists. This means you will require a
random.shufflebetween sorts if you want to avoid wrecking your timings.