Smoothing Function in Python

def smoothen(heightProfile, travelTime):
    newHeightProfile = []

    # Berechne einen gleitenden Mittelwert
    smoothingInterval = 30 * travelTime

    for i in xrange(smoothingInterval):
        heightProfile.append(heightProfile[-1])

    for i in xrange(len(heightProfile) - smoothingInterval):
        mean = 0
        for j in xrange(i, i + smoothingInterval):
            mean += heightProfile[j]
        newHeightProfile.append(mean/smoothingInterval)

    return newHeightProfile

Input:

• heightProfile: an array of the size travelTime * 60

• travelTime: an integer

travelTime can be, for example, 500. heightProfile contains an array of random numbers of the size travelTime * 60. The height profile should describe the height of a random landscape. The function is used to smoothen the values.

However, this code is very slow and expensive, even when using xrange:

• Tests for travel time: 500

• CPython: 38.3s

• Pypy: 0.98s

Questions:

• Is there a construct in this code which is very inefficient?

• Would this be faster if I were to implement this function in C?

Any other recommendations for improvement are welcome.

Currently you are calculating the mean each time in the loop, so that's slice + sum for each of the len(heightProfile) - smoothingInterval iterations. We can remove this by calculating the mean of first smoothingInterval items and then inside of the loop simply subtract current ith item from the sum of the previous mean and add (i + smoothingInterval)th item to the sum and calculate the mean for the current window. With this approach we can do this in almost linear time.

Also as you're using Python 2 don't forget to add this line at the top of the file, otherwise normal division will result in integer division.

from __future__ import division

You can replace:

for i in range(smoothingInterval):
        heightProfile.append(heightProfile[-1])

with:

heightProfile.extend([heightProfile[-1]]*smoothingInterval)

If smoothingInterval is very huge then consider passing a generator expression to list.extend, but in most cases [heightProfile[-1]]*smoothingInterval is as fast as you can get:

last_val = heightProfile[-1]
heightProfile.extend(last_val for _ in xrange(smoothingInterval))

Full Code:

from __future__ import division

def smoothen_fast(heightProfile, travelTime):

    smoothingInterval = 30 * travelTime

    heightProfile.extend([heightProfile[-1]]*smoothingInterval)
    # Get the mean of first `smoothingInterval` items  
    first_mean = sum(heightProfile[:smoothingInterval]) / smoothingInterval
    newHeightProfile = [first_mean]

    for i in xrange(len(heightProfile)-smoothingInterval-1):
        prev = heightProfile[i]  # the item to be subtracted from the sum
        new = heightProfile[i+smoothingInterval] # item to be added
        # Calculate the sum of previous items by multiplying
        # last mean with smoothingInterval
        prev_sum = newHeightProfile[-1] * smoothingInterval
        new_sum = prev_sum - prev + new
        mean = new_sum / smoothingInterval
        newHeightProfile.append(mean)

    return newHeightProfile

Timing comparisons:

>>> from random import sample
>>> heightProfile = sample(xrange(1, 10**5), 10**4)
>>> travelTime = 1000
>>> %timeit smoothen(heightProfile[:], travelTime)
1 loops, best of 3: 11.3 s per loop
>>> %timeit smoothen_fast(heightProfile[:], travelTime)
100 loops, best of 3: 2.69 ms per loop

Note that in my function call I am passing a slice of the list because we are modifying the passed list object using its .extend method, which is usually a not a good idea unless the caller expects such modifications.

StackExchange Code Review Q#79310, answer score: 5