HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Faster way to perform function calculation in Python?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
calculationfunctionwayfasterperformpython

Problem

I'm interested in whether there is a way to further improve a "fast" version of a function used in a homework assignment I received recently (I've already submitted the completed work).

from math import log

def func_fast(mass, density):
    return sum(map((log(mass * density)).__truediv__, range(1,10001)))

def func_slow(mass, density): 
    total = 0.0 
    for i in range(10000): 
        masslog = log(mass * density) 
        total += masslog/(i+1)

    return total

mass = 2.5 
density = 12.0


The fast version times in around 2-2.5ish seconds while the slow version nets 6-7 seconds.

Solution

This continues from Jaime's post.

This can be trivially sped up to \$\mathcal{O}(1)\$ by caching sum(1/j for j in range(1, 10001)) = 9.787606036044348. Then one just does

def func_O1(mass, density):
    # 9.7876... = sum(1/j for j in range(1, 10001))
    return log(mass * density) * 9.787606036044348


This gives a speedup by a factor of 3000.

If the limit (10000) is varied, use an approximation for the harmonic series:

from math import log

def harmonic(n):
    gamma = 0.57721566490153286060651209008240243104215933593992
    return gamma + log(n) + 0.5/n - 1./(12*n**2) + 1./(120*n**4)

def func_fastest(mass, density):
    return log(mass * density) * harmonic(10000)


harmonic is inaccurate below \$n \approx 120\$ so it would make sense to cache exact values up to harmonic(120). Note that whilst this is an approximation, for \$n\$ greater than \$120\$ it's exact \$\pm 1\text{eps}\$ whereas the summation gets steadily worse.

This only speeds up the function by a factor of 500.

Code Snippets

def func_O1(mass, density):
    # 9.7876... = sum(1/j for j in range(1, 10001))
    return log(mass * density) * 9.787606036044348
from math import log

def harmonic(n):
    gamma = 0.57721566490153286060651209008240243104215933593992
    return gamma + log(n) + 0.5/n - 1./(12*n**2) + 1./(120*n**4)

def func_fastest(mass, density):
    return log(mass * density) * harmonic(10000)

Context

StackExchange Code Review Q#76978, answer score: 8

Revisions (0)

No revisions yet.