How do I use timeit
to compare the performance of my own functions such as "insertion_sort
" and "tim_sort
"?
15 Answers
If you want to use timeit
in an interactive Python session, there are two convenient options:
Use the IPython shell. It features the convenient
%timeit
special function:In [1]: def f(x): ...: return x*x ...: In [2]: %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 random
random.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.04485079200821929
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.
-
8Yes, it includes the list copy (which is very fast compared to the sort itself). If you don't copy though, the first pass sorts the list and remaining passed don't have to do any work. If you want to know the time just for the sort, then run the above with and without the
timsort(a)
and take the difference :-) Commented Feb 7, 2012 at 1:58 -
109@max Use the min() rather than the average of the timings. That is a recommendation from me, from Tim Peters, and from Guido van Rossum. The fastest time represents the best an algorithm can perform when the caches are loaded and the system isn't busy with other tasks. All the timings are noisy -- the fastest time is the least noisy. It is easy to show that the fastest timings are the most reproducible and therefore the most useful when timing two different implementations. Commented Apr 3, 2012 at 19:43
-
6You calculate an average (well, total, but it's equivalent) for 1000 inputs; then repeat 7 times, and take the minimum. You need the averaging over 1000 inputs because you want the average (not best-case) algorithm complexity. You need the minimum for precisely the reason you gave. I thought I can improve your approach by choosing one input, running the algorithm 7 times, taking the minimum; then repeating it for 1000 different inputs, and taking the average. What I didn't realize is that your
.repeat(7,1000)
already does this (by using the same seed)! So your solution is perfect IMO.– maxCommented Apr 3, 2012 at 21:04 -
6I can only add that how you allocate your budget of 7000 executions (e.g.,
.repeat(7, 1000)
vs..repeat(2, 3500)
vs.repeat(35, 200
) should depend on how the error due to system load compares to the error due to input variability. In the extreme case if your system is always under heavy load, and you see a long thin tail on the left of execution time distribution (when you catch it in a rare idle state), you might even find.repeat(7000,1)
to be more useful than.repeat(7,1000)
if you can't budget more than 7000 runs.– maxCommented Apr 3, 2012 at 21:19 -
1How about duplicating the array already in the setup, creating an iterator
it
over them, and then timing'a=next(it); timsort(a)'
? Commented Dec 26, 2017 at 3:13
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)
and times
sum(x)
min(y)
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:
min(timeit.Timer(function).repeat(repeat=REPEATS, number=NUMBER))
You should normally combine this with functools.partial
instead of lambda: ...
to lower overhead. Thus you could have something like:
from functools import partial
def to_time(items):
...
test_items = [1, 2, 3] * 100
times = timeit.Timer(partial(to_time, test_items)).repeat(3, 1000)
# Divide by the number of repeats
time_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 timeit
.
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.
Warnings
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:>>> python -m timeit -s "x = 0" "x += 1" 10000000 loops, best of 3: 0.0476 usec per loop
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:
>>> python -m timeit -s "x = 0" "" 100000000 loops, best of 3: 0.014 usec per loop
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
x
also need to be included in overhead:>>> python -m timeit -s "x = 0" "x" 100000000 loops, best of 3: 0.0166 usec per loop
The difference isn't much larger, but it's there.
Mutating methods are dangerous.
>>> python -m timeit -s "x = [0]*100000" "while x: x.pop()" 10000000 loops, best of 3: 0.0436 usec per loop
But that's completely wrong!
x
is the empty list after the first iteration. You'll need to reinitialize:>>> python -m timeit "x = [0]*100000" "while x: x.pop()" 100 loops, best of 3: 9.79 msec per loop
But then you have lots of overhead. Account for that separately.
>>> python -m timeit "x = [0]*100000" 1000 loops, best of 3: 261 usec per loop
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.shuffle
between sorts if you want to avoid wrecking your timings.
If you want to compare two blocks of code / functions quickly you could do:
import timeit
start_time = timeit.default_timer()
func1()
print(timeit.default_timer() - start_time)
start_time = timeit.default_timer()
func2()
print(timeit.default_timer() - start_time)
-
Just use
time.perf_counter
ortime.perf_counter_ns
instead– user3064538Commented Sep 22, 2023 at 3:42
I find the easiest way to use timeit is from the command line.
Given test.py:
def insertion_sort(): ...
def timsort(): ...
run timeit
like this:
% python -m timeit -s 'import test' 'test.insertion_sort()'
% python -m timeit -s 'import test' 'test.timsort()'
-
1Like it! Under a Windows command prompt, I had to use double quotes to avoid
SyntaxError: unterminated string literal
. Yes, very late to the party.– RolfBlyCommented Nov 11, 2023 at 12:39
for me, this is the fastest way:
import timeit
def foo():
print("here is my code to time...")
timeit.timeit(stmt=foo, number=1234567)
# Генерация целых чисел
def gen_prime(x):
multiples = []
results = []
for i in range(2, x+1):
if i not in multiples:
results.append(i)
for j in range(i*i, x+1, i):
multiples.append(j)
return results
import timeit
# Засекаем время
start_time = timeit.default_timer()
gen_prime(3000)
print(timeit.default_timer() - start_time)
# start_time = timeit.default_timer()
# gen_prime(1001)
# print(timeit.default_timer() - start_time)
This works great:
python -m timeit -c "$(cat file_name.py)"
-
1
-
5How do you pass parameters, if the script requires any? Commented Dec 20, 2018 at 9:32
-
@Shailen I found
python -m timeit -s $(cat file_name.py)
to work with PowerShell. With quotes around the$()
, PowerShell seems to output everything from file_name into one line which results in an error.– user8917573Commented Jan 24, 2023 at 19:14
simply pass your entire code as an argument of timeit:
import timeit
print(timeit.timeit(
"""
limit = 10000
prime_list = [i for i in range(2, limit+1)]
for prime in prime_list:
for elem in range(prime*2, max(prime_list)+1, prime):
if elem in prime_list:
prime_list.remove(elem)
"""
, number=10))
This has been answered a lot, but I just wanted to say that I find passing in the function directly much more ergonomic than passing in a string (as in all the other answers) or messing around with wrappers. For example,
import timeit
def my_sort(lst: list) -> list:
do_something()
lst = [2, 3, 1]
timeit.timeit(lambda: my_sort(lst))
As a side note, ```timeit.repeat`` is also very useful, as it returns a list of times you can use to perform your own analysis. Also will recommend perfplot, which does much of this internally and produces a nice looking graph at the end.
lets setup the same dictionary in each of the following and test the execution time.
The setup argument is basically setting up the dictionary
Number is to run the code 1000000 times. Not the setup but the stmt
When you run this you can see that index is way faster than get. You can run it multiple times to see.
The code basically tries to get the value of c in the dictionary.
import timeit
print('Getting value of C by index:', timeit.timeit(stmt="mydict['c']", setup="mydict={'a':5, 'b':6, 'c':7}", number=1000000))
print('Getting value of C by get:', timeit.timeit(stmt="mydict.get('c')", setup="mydict={'a':5, 'b':6, 'c':7}", number=1000000))
Here are my results, yours will differ.
by index: 0.20900007452246427
by get: 0.54841166886888
import timeit
def oct(x):
return x*x
timeit.Timer("for x in range(100): oct(x)", "gc.enable()").timeit()
-
-
Activation of the
Garbage Collection
that is usually deactivated during these timing runs. Commented Jul 9, 2021 at 18:55
The built-in timeit module works best from the IPython command line.
To time functions from within a module:
from timeit import default_timer as timer
import sys
def timefunc(func, *args, **kwargs):
"""Time a function.
args:
iterations=3
Usage example:
timeit(myfunc, 1, b=2)
"""
try:
iterations = kwargs.pop('iterations')
except KeyError:
iterations = 3
elapsed = sys.maxsize
for _ in range(iterations):
start = timer()
result = func(*args, **kwargs)
elapsed = min(timer() - start, elapsed)
print(('Best of {} {}(): {:.9f}'.format(iterations, func.__name__, elapsed)))
return result
Example of how to use Python REPL interpreter with function that accepts parameters.
>>> import timeit
>>> def naive_func(x):
... a = 0
... for i in range(a):
... a += i
... return a
>>> def wrapper(func, *args, **kwargs):
... def wrapper():
... return func(*args, **kwargs)
... return wrapper
>>> wrapped = wrapper(naive_func, 1_000)
>>> timeit.timeit(wrapped, number=1_000_000)
0.4458435332577161
You would create two functions and then run something similar to this.
Notice, you want to choose the same number of execution/run to compare apple to apple.
This was tested under Python 3.7.
Here is the code for ease of copying it
!/usr/local/bin/python3
import timeit
def fibonacci(n):
"""
Returns the n-th Fibonacci number.
"""
if(n == 0):
result = 0
elif(n == 1):
result = 1
else:
result = fibonacci(n-1) + fibonacci(n-2)
return result
if __name__ == '__main__':
import timeit
t1 = timeit.Timer("fibonacci(13)", "from __main__ import fibonacci")
print("fibonacci ran:",t1.timeit(number=1000), "milliseconds")