2
\$\begingroup\$

I am working on a script in Python 3.5 that will take in data from several large files. The script takes a while to run, so I am trying to optimize the functions that take the longest. In particular, each file contains around 1 million arrays of around 200 floats.

I need to:

  1. compute the difference between consecutive values in each array
  2. find the point at which the difference between values becomes approximately zero (within some limit). Values beyond this point will be discarded.
  3. find the average value of the discarded data points

So for one array of one data set:

import numpy as np

# the input data is an array of 190 floats
input = array_of_floats

# compute the difference between consecutive floats in the data array
size = len(input)-1
differences = [(input[i+1]-input[i]) for i in np.arange(0,size)]

# reliable standard deviation used to determine discard limit
good_sigma = np.std(differences[20:60])

# get the upper and lower limit
upperbound = 0 + 3*good_sigma
lowerbound = 0 - 3*good_sigma

# find points between upper and lower bound to discard
discard = np.where((lowerbound < differences) & (differences < upperbound))

# find the average value of input data from the first discarded point to 
# the end of the input data array
average_discard = np.average(input[np.min(discard):])

# typically, for an array of around 200 floats, the last 60 data points are
# discarded. The rest of the input array is used for other functions in the
# script. 

The "differences" step is what takes the longest. For one data set it isn't so bad (~0.01sec), but each file has over 1 million input arrays that I will have to perform this function on. Can someone provide some insight on whether I have written this in the most optimal way? I was also considering using Cython.

Edited to add example input data

array_of_floats = 
    [  2.67944336e-02,   4.67507019e+02,   9.42140930e+02,
 1.43761255e+03,   1.87599805e+03,   2.36763574e+03,
 2.83424146e+03,   3.31971045e+03,   3.76542065e+03,
 4.25951953e+03,   4.72111377e+03,   5.20215820e+03,
 5.65431445e+03,   6.12919092e+03,   6.60266846e+03,
 7.07001367e+03,   7.52144385e+03,   7.98579102e+03,
 8.46145410e+03,   8.89987012e+03,   9.37324805e+03,
 9.82474414e+03,   1.02881533e+04,   1.07467061e+04,
 1.11988945e+04,   1.16621221e+04,   1.21015020e+04,
 1.25664697e+04,   1.30272354e+04,   1.34883242e+04,
 1.39572393e+04,   1.44017471e+04,   1.48729639e+04,
 1.53420791e+04,   1.57918623e+04,   1.62737021e+04,
 1.67290801e+04,   1.71610977e+04,   1.76309434e+04,
 1.80829941e+04,   1.85269258e+04,   1.89810938e+04,
 1.94234805e+04,   1.98656348e+04,   2.03295234e+04,
 2.07511074e+04,   2.11939336e+04,   2.16337148e+04,
 2.20985977e+04,   2.25441953e+04,   2.29944922e+04,
 2.34240684e+04,   2.38671055e+04,   2.42933281e+04,
 2.47243613e+04,   2.51660430e+04,   2.55904414e+04,
 2.60533496e+04,   2.64807930e+04,   2.69388066e+04,
 2.73816992e+04,   2.78312188e+04,   2.82667852e+04,
 2.87178203e+04,   2.91476543e+04,   2.95946309e+04,
 3.00434082e+04,   3.04553223e+04,   3.08737930e+04,
 3.13186289e+04,   3.17753789e+04,   3.21826094e+04,
 3.26074180e+04,   3.30163086e+04,   3.34446172e+04,
 3.38478047e+04,   3.43073906e+04,   3.47224141e+04,
 3.51193594e+04,   3.55621133e+04,   3.59837227e+04,
 3.64019414e+04,   3.68227656e+04,   3.72113984e+04,
 3.76188047e+04,   3.80122266e+04,   3.84034336e+04,
 3.87982461e+04,   3.91839023e+04,   3.96071328e+04,
 3.99813711e+04,   4.03818320e+04,   4.07885820e+04,
 4.11744141e+04,   4.15733477e+04,   4.19752812e+04,
 4.23835117e+04,   4.27578242e+04,   4.31517734e+04,
 4.35184570e+04,   4.39032695e+04,   4.42956719e+04,
 4.46545352e+04,   4.50035625e+04,   4.53278594e+04,
 4.56956250e+04,   4.60475664e+04,   4.63969258e+04,
 4.67411914e+04,   4.70916680e+04,   4.73866953e+04,
 4.77376367e+04,   4.80478594e+04,   4.83474922e+04,
 4.86498945e+04,   4.89277109e+04,   4.92157930e+04,
 4.94906094e+04,   4.97758086e+04,   5.00400352e+04,
 5.02743164e+04,   5.05048789e+04,   5.07182930e+04,
 5.08856797e+04,   5.09154609e+04,   5.09754453e+04,
 5.10226016e+04,   5.10574258e+04,   5.10819297e+04,
 5.10935078e+04,   5.11123477e+04,   5.10979922e+04,
 5.11024531e+04,   5.11305391e+04,   5.11065547e+04,
 5.11401133e+04,   5.11246992e+04,   5.11225039e+04,
 5.11162930e+04,   5.11391328e+04,   5.11314414e+04,
 5.11349570e+04,   5.11212422e+04,   5.11400430e+04,
 5.11528672e+04,   5.11323711e+04,   5.11348008e+04,
 5.11359648e+04,   5.11285898e+04,   5.11156602e+04,
 5.11257812e+04,   5.11293555e+04,   5.11290586e+04,
 5.11461758e+04,   5.11537109e+04,   5.11460273e+04,
 5.11330156e+04,   5.11367305e+04,   5.11117695e+04,
 5.11316523e+04,   5.11255156e+04,   5.11356445e+04,
 5.11348477e+04,   5.11349883e+04,   5.11344688e+04,
 5.11403672e+04,   5.11524258e+04,   5.11408828e+04,
 5.11490430e+04,   5.11274375e+04,   5.11171719e+04,
 5.11178750e+04,   5.11357109e+04,   5.11389062e+04,
 5.11551289e+04,   5.11504492e+04,   5.11347695e+04,
 5.11315117e+04,   5.11602109e+04,   5.11206133e+04,
 5.11212422e+04,   5.11430469e+04,   5.11394023e+04,
 5.11372461e+04,   5.11174414e+04,   5.11088906e+04,
 5.11134766e+04,   5.11321641e+04,   5.11333203e+04,
 5.11284531e+04]
\$\endgroup\$
  • \$\begingroup\$ Could you add at least one of the array_of_floats, so we can check to see if any changes we propose actually improve the timing? \$\endgroup\$ – Graipher Jan 5 '17 at 9:35
1
\$\begingroup\$

To reap the benefits of numpy, you need to use numpy arrays and functions throughout.

The simplest fix is using numpy.diff:

import numpy as np


for _ in range(10000):
    input = 100 * np.random.random(size=190)
    # size = len(input) - 1
    # differences = [(input[i + 1] - input[i]) for i in np.arange(0, size)]
    differences = np.diff(input)
    good_sigma = np.std(differences[20:60])
    upperbound = 3 * good_sigma
    lowerbound = -3 * good_sigma
    discard = np.where((lowerbound < differences) & (differences < upperbound))
    average_discard = np.average(input[np.min(discard):])

Swapping the two difference calls result in 1.8s for your list version vs 0.6s using numpy.diff (on my machine). Note that this includes the generation of ten-thousand random input vectors.

Apart from that, here are a few more tips:

  1. Avoid shadowing built-in functions/variables. input is already an existing function that takes user input.

  2. While the 0 + 3 * sigma helps to realize that the mean is at zero, a simple comment should be enough for that and save a few unneeded cycles.

  3. In general, comments should explain why you are doung something the way you are doing it, instead of what you are doing. The latter should be clear from the code itself (which is not really the case with your code). This is especially important for example for the np.std call. While you explain that using standard deviation is a good way to measure spread (duh), you don't explain why you only take it for `differences[20:60]. If it is not possible to understand what the code does from looking at it, encapsulate the hard-to-understand code in a properly named function with a descriptive docstring.

  4. Try to avoid creating copies of arrays by slicing.

  5. Some small improvements can be made by getting the right index of where to start discarding (this assumes that later you also discard all values after the first to be discarded value). For this I used the slightly faster numpy.argmax, as described here. It could be even faster if your array of floats was sorted. It uses max, because True == 1 and it returns the first maximum that appears.

  6. The algorithm as written seems to start discarding whenever the difference is smaller than three sigma, whereas normally you would probably want to start discarding as soon as the difference is larger than three sigma. For this you would have to turn around your logical operators (not done in code below).

import numpy as np


array_of_floats = 100 * np.random.random(size=190)
differences = np.diff(array_of_floats)
three_sigma = 3 * np.std(differences[20:60])

# choose three sigma region around mean of zero
upperbound = three_sigma
lowerbound = -three_sigma
discard = np.argmax((lowerbound < differences) &
                    (differences < upperbound))
average_discard = np.average(array_of_floats[discard:])

Running both versions 10000 times with the one given input, this results in the original code taking about 1.3s and the modified code about 0.5s.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.