[python] archive category

Top five reasons why Python won’t get you laid

From the Home Office in Fairford, Manitoba, here are tonight’s top-five reasons why Python won’t get you laid…

I’m so hungry…

 

>>> ================================ RESTART ================================
>>> import hashlib
>>> hashlib.sha512("I am so going to stuff my face with a burrito tomorrow...").hexdigest()
'256331e2f73ce5d1868b3db5ae004312db40a1d0df9a046bc7714c29b59fe8d24d0abc6892cd2783b
8d4097df78de3850306a34e49acf80320aa8bf14ef2744d'

Go faster with Horner’s rule

Consider the following polynomial:
Fourth order polynomial
This is a fourth-order polynomial. To evaluate this thing, you might write the following code in Python.

def f(x):
    return x**4 + x**3 + x**2 + x + 1

The problem is that calculating exponents is computationally expensive, so you might try to create a closed form of the equation. In this example, you can use the well known generating function:
Generating function form of the polynomial
This reduces the number of exponents that Python has to deal with. Watch the division by zero error if you let x=1!

def genf(x):
	return (1 - x**5)/(1-x)

If we could reduce or eliminate the number of exponents even further, we might expect that the code would run faster. Fortunately, you can apply Horner’s Rule to this problem. The rule removes the exponents by factorizing the equation into a series of multiplication and addition steps:
Horner's Rule applied to fourth order polynomial
The equation, now missing the expensive exponents, can be implemented like this:

def hornerf(x):
	return (((x+1)*x+1)*x+1)*x+1

So now you’re probably thinking, “Show me the money!”

The following code is a test harness that counts how much time it takes to execute the functions on a large set of numbers.

def timeit(fn):
	begin = time.time()
	for element in bigset:
		fn(element)
	end = time.time()
	return end - begin

The following is a transcript of the test run on my laptop:

>>> ================================ RESTART ================================
>>> def f(x):
        return x**4 + x**3 + x**2 + x + 1

>>> def genf(x):
	return (1 - x**5)/(1-x)

>>> def hornerf(x):
	return (((x+1)*x+1)*x+1)*x+1

>>> import time
>>> bigset = range(2,1000000)
>>> def timeit(fn):
	begin = time.time()
	for element in bigset:
		fn(element)
	end = time.time()
	return end - begin

>>> timeit(f)
9.2969999313354492
>>> timeit(genf)
4.4679999351501465
>>> timeit(hornerf)
2.1099998950958252

In this example, you could gain a speed improvement of over 70% from eliminating the exponents in your code. Although not all optimizations will be this dramatic, you will almost always gain some improvement by eliminating exponents.

Thanks to D Yoo