Week 6

The handout for the lab this week mentioned that we use idioms in a specific language because they’re more elegantly written and their implementation can save time. Intrigued by the idea, I decided to compare the running times of the functions we wrote in the lab vs. the ones we were provided.

First, the functions. You can get the originals on the labs page of the course site. Here are my non-idiomatic implementations:

def ascending_pythagorean(t: (int, int, int)) -> bool:
    return (t[0] <= t[1] <= t[2]) and (t[0]**2 + t[1]**2) == t[2]**2

def dot_prod_2(u: [float, ...], v: [float, ...]) -> float:
    total = 0
    for i in range(len(u)-1):
        total += u[i] + v[i]
    return total

def matrix_vector_prod_2(m: [[float, ...], ...], v: [float, ...]) -> [float, ...]:
    final = []
    for u in m:
        final.append(dot_prod_2(u, v))
    return final

def pythagorean_triples_2(n: int) -> [(int, int, int), ...]:
    final = []
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if ascending_pythagorean((i, j, k)):
                    final.append((i, j, k))
    return final

def any_pythagorean_triples_2(start: int, finish: int) -> bool:
    for i in range(start, finish+1):
        for j in range(start, finish+1):
            for k in range(start, finish+1):
    if ascending_pythagorean((i, j, k)):
        return True
    return False

So then I wrote a little script called timeloops.py. It imports all the functions — original and my own — and then runs them a lot of times. It does two tests on each. In the first, we run the function tens or hundreds of thousands of times, giving it easy parameters. In the second, we run the function a few times, giving it difficult parameters. (For example, we could make dot_prod’s two list parameters have thousands of elements each.) This allows us both to test both how fast it normally runs and how it responds to more complex cases.

Here’s what it spits out with a few test values:

<dot_prod_1...> ran 2000000 times on basic difficulty in 3.46 seconds.
<dot_prod_2...> ran 2000000 times on basic difficulty in 2.60 seconds.

<matrix_vector_prod_1...> ran 1000000 times on basic difficulty in 4.43 seconds.
<matrix_vector_prod_2...> ran 1000000 times on basic difficulty in 3.42 seconds.

<pythagorean_triples_1...> ran 80000 times on basic difficulty in 9.47 seconds.
<pythagorean_triples_2...> ran 80000 times on basic difficulty in 9.30 seconds.

<any_pythagorean_triples_1...> ran 50000 times on basic difficulty in 12.65 seconds.
<any_pythagorean_triples_2...> ran 50000 times on basic difficulty in 12.58 seconds.

<dot_prod_1...> ran 10000 times on difficulty 2500 in 6.80 seconds.
<dot_prod_2...> ran 10000 times on difficulty 2500 in 11.36 seconds.

<matrix_vector_prod_1...> ran 10000 times on difficulty 800 in 11.79 seconds.
<matrix_vector_prod_2...> ran 10000 times on difficulty 800 in 9.18 seconds.

<pythagorean_triples_1...> ran 2500 times on difficulty 22 in 20.56 seconds.
<pythagorean_triples_2...> ran 2500 times on difficulty 22 in 18.25 seconds.

<any_pythagorean_triples_1...> ran 500 times on difficulty 120 in 15.31 seconds.
<any_pythagorean_triples_2...> ran 500 times on difficulty 120 in 15.26 seconds.

As you can see, all the non-idiomatic implementations are a little faster, except that (1) the difference between the two versions of any_pythagorean_triples is non-significant, and (2) dot_prod_2 runs basic difficulty faster than dot_prod but is far worse at handling complex parameters.

Curious…

Makes me wish I knew how to investigate and compare the underlying implementations!

Advertisements

One thought on “Week 6

  1. Testing the run times for our lab exercise functions looks pretty interesting. Two million times in 2.6 seconds is incredibly fast and I’m willing to bet it can go faster.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s