Let’s take a look at the very popular problem of finding the average of a list of numbers. The conventional method for this is to add all the numbers and then divide by the length of the list. For example:

1, 3, 5, 7

1 + 3 + 5 + 7 = 16
16/4 = 4

So the average is 4.

Now let’s say you add another number to the list, 9. What would you do? If you follow the above method, you will re-add all the numbers and divide again. Here that’s not a problem, but imagine you have a huge list with a lot of numbers coming in. Would you still add all the numbers and then divide?

That’s wasteful. We need to find a better algorithm for finding the average. To do that, we will need to use the previous average to calculate the new average. We will name the previous average prevAvg, the previous list length prevLength, the current list length currLength and the new number x. We want to find the current average, currAvg.

currAvg = \frac{prevAvg*prevLength+x}{currLength}

In Python code:

#Initial list, average and length
sequence = [1,3,5,7];
avg = 4;
length = 4;

#Add x to list, length increases by 1
x = 9;

avg = (avg*length+x)/(length+1);
print avg;

This can speed up a lot your work, especially when you are dealing with big data and want to calculate, say, the mean.

Advertisements

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