Need to compare which code is faster, read on to find out how

A friend of mine, Mridu Bhatnagar, has been posting some really cool articles explaining how she's gone about solving some LeetCode challenges. They are all interesting, but due to time constraints, I have only attempted to see if I can do a couple of them.

Move Zeroes

One of the first that I attempted to do was Move Zeroes. I thought that I was being clever, and sure enough, my initial time test seemed to indicate the same. That is, until Suraj Sharma pointed out to me that once the numbers got bigger, that my implementation would be slower.

I decided to see if it was true, and sure enough, once I increased the starting size number, mine was way slower!! At any rate, Suraj really liked how I benchmarked the codes, so I decided to share it here.

I wanted to write a script that would indicate, whose code it was currently running with the results to the right of it. In order to keep it DRY, I decided to use decorators.

Here is what the results look like:

...
Working with 8 zeroes out of 100 numbers
   mridu: 0.0000221729
clamytoe: 0.0000185966
 striker: 0.0000629425
 ...
Working with 10003 zeroes out of 100,000 numbers
   mridu: 8.4343523979
clamytoe: 8.0974295139
 striker: 0.0438303947

Full code can be found in this gist.

Decorator: ID Checker

Part of the requirements for the challenge, was that the same object needed to be modified and not just create a new one. I'm not really sure if this is the way to do it, but I decided that checking to see if the id of the before and after objects were the same was the way to go.

def id_checker(func):
    @wraps(func)
    def wrapper(nums):
        before = id(nums)
        func(nums)
        after = id(nums)

        if DEBUG:
            print(f"{'before':>8}: {before}")
            print(f"{'after':>8}: {after}\n")

        if before != after:
            print("The nums list is not the same!")

    return wrapper

Since our functions all only passed the nums variable, I decided to just hard code it in instead of using *args. In hindsight, I should have used *args. Sometimes while developing code, I like to throw in a DEBUG global variable to turn on/off print statements, so those can be ignored.

Decorator: Timer

I decided that the easiest way to keep track of whose code was being benchmarked, would be to name each of our functions, with our nicknames. Then it would be simple enough to extract the function name from within the code.

To time the functions, I created this timer decorator. It's a pretty straight forward timer. The only unique part is how I extracted the function name.

def timer(func):
    @wraps(func)
    def wrapper(nums):
        start = time()
        func(nums)
        stop = time()
        print(f"{func.__name__:>8}: {stop - start:.10f}")

    return wrapper

If you are not familiar with formatting strings within f-strings, the :>8 simply means to right align it and use 8 spaces. The :.10f just means that it's a float value and that I want it to use 10 digits of accuracy.

Decorating the Functions

Each of the separate functions were decorated in the same manner. To try and keep this discussion short, I'll only illustrate mine.

@id_checker
@timer
def clamytoe(nums: List[int]):
    count = 0
    while True:
        try:
            nums.remove(0)
            count += 1
        except ValueError:
            break

    for _ in range(count):
        nums.insert(len(nums), 0)

The decorators are applied from bottom up. Meaning that the @timer decorator is the first to be ran, followed by the @id_checker. If you are not familiar with decorators, Dan Bader wrote a nice article on them.

Generating the Numbers

Since the size of the number played such a significant part in how the code runs, I decided to create a small little number generator.

def generate_nums(size: int) -> List[int]:
    numbers = [0]
    for _ in range(size - 1):
        numbers.extend(sample(range(10), 1))

    return numbers

I decided to go with list's built in .extend method in order to add the iterable generated by random.sample to my list of numbers.

Test Function

Originally, my intent was to create a "testing"/"benchmarking" function for each piece of code, but ended up being about to run them all from the one. I just forgot to rename it...

def test_one(original):
    nums1 = deepcopy(original)
    nums2 = deepcopy(original)
    nums3 = deepcopy(original)

    mridu(nums1)
    clamytoe(nums2)
    striker(nums3)

    try:
        assert nums1 == nums2 == nums3
    except AssertionError:
        print("Outputs do not match!")
        print(f"original: \n{original}")
        print(f"mridu: \n{nums1}")
        print(f"clamytoe: \n{nums2}")
        print(f"striker: \n{nums3}")

I started off by making copies of the original number and then used the copies to make sure that all three implementations were returning the same numbers.

Benchmarking

Phew, finally getting to kicking it all off! The following bit of code runs the benchmark and generates the report.

if __name__ == "__main__":
    sizes = [10, 100, 1_000, 10_000, 100_000]
    for size in sizes:
        original = generate_nums(size)
        print(f"Working with {original.count(0)} zeroes out of {len(original):,} numbers")
        test_one(original)

I first start with a list of the number lengths that I want to benchmark against. I then iterate over that list and using the generate_nums() function, generate the numbers. This is followed by printing some information of how many zeroes are actually in the number and the length of the number being used. Then finally the actual benchmark is performed.

This is repeated until all of the sizes have been benchmarked.

A Better Way to Benchmark Code

I was working through another one of the challenges that Mridu had completed, Reverse words in a string III. When it came time to compare my implementation with hers, I decided to use the timeit module this time around.

Python comes with the timeit module in the standard library. I don't like that you have to pass the code that you want to benchmark to it as a string, but it works pretty well. It times how long a particular piece of code takes to execute a certain number of times, and returns the fastest time.

Here is the script in it's entirety:

from timeit import timeit

setup_code = """
s = "Let's take LeetCode contest"
"""

mridu = """
def reverseWords(s: str) -> str:
    s = s.split()
    s1 = ''
    for x in range(0, len(s)):
        if x == len(s) - 1:
            s1 += s[x][::-1]
        else:
            s1 += s[x][::-1] + ' '
    return s1


reverseWords(s)
"""

clamytoe = """
def reverse_words(s):
    return " ".join([word[::-1] for word in s.split()])


reverse_words(s)
"""


codes = {
    "clamytoe": clamytoe,
    "mridu": mridu
}

for code in codes:
    print(code, timeit(stmt=codes[code], setup=setup_code))

The results from running it, look like this:

clamytoe 1.9202047239996318
mridu 3.630925637000473

As you can see, in the timeit function, I'm passing stmt and setup variables. The stmt is the actual code to benchmark, while setup is used to setup any code that will be required for it to run properly. The values passed, just need to be strings, so the easiest thing to do is to just enclose your code in triple double quotes and set it to a variable.

You can also pass a number variable that allows you to modify how many times the code is ran, with the default being 1,000,000.

I didn't see a way of using decorators here, so I simply used a dictionary to do the identifying for me.

Summary

I hope that you will now know how to benchmark any of your code. The first method, using time is more suited towards larger code, while timeit is good for shorter snippets of code. The timeit module can do a few more things. I suggest reading up on it if you're curious.

Until next time, keep on coding!

Update

I've always thought that having to enclose your code in triple double quotes was kind of clunky. Well, my buddy Harrison Morgan just demonstrated to me that you don't have to! The same thing can be done with a decorator and a lambda expression!

from functools import wraps
from timeit import timeit


def test_performance(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        result = timeit(lambda: func(*args, **kwargs))
        print(f"{func.__name__:>8}: {result}")

    return wrapper


@test_performance
def mridu(s: str) -> str:
    s = s.split()
    s1 = ''
    for x in range(0, len(s)):
        if x == len(s) - 1:
            s1 += s[x][::-1]
        else:
            s1 += s[x][::-1] + ' '
    return s1


@test_performance
def clamytoe(s):
    return " ".join([word[::-1] for word in s.split()])


if __name__ == "__main__":
    s = "Let's take LeetCode contest"
    clamytoe(s)
    mridu(s)

And the results:

clamytoe: 1.9616992009999876
   mridu: 3.411077960000057

How awesome is that? This is why the Python community is so great! Everyone is willing to freely share in their knowledge and help each other, thanks again Harrison!