I'm performing a nested loop in python that is included below. This serves as a basic way of searching through existing financial time series and looking for periods in the time series that match certain characteristics.
In this case there are two separate, equally sized, arrays representing the 'close' (i.e. the price of an asset) and the 'volume' (i.e. the amount of the asset that was exchanged over the period). For each period in time I would like to look forward at all future intervals with lengths between 1 and INTERVAL_LENGTH
and see if any of those intervals have characteristics that match my search (in this case the ratio of the close values is greater than 1.0001 and less than 1.5 and the summed volume is greater than 100).
My understanding is that one of the major reasons for the speedup when using NumPy is that the interpreter doesn't need to type-check the operands each time it evaluates something so long as you're operating on the array as a whole (e.g. numpy_array * 2
), but obviously the code below is not taking advantage of that.
Is there a way to replace the internal loop with some kind of window function which could result in a speedup, or any other way using numpy
/scipy
to speed this up substantially in native python?
Alternatively, is there a better way to do this in general (e.g. will it be much faster to write this loop in C++ and use weave)?
ARRAY_LENGTH = 500000
INTERVAL_LENGTH = 15
close = np.array( xrange(ARRAY_LENGTH) )
volume = np.array( xrange(ARRAY_LENGTH) )
close, volume = close.astype('float64'), volume.astype('float64')
results = []
for i in xrange(len(close) - INTERVAL_LENGTH):
for j in xrange(i+1, i+INTERVAL_LENGTH):
ret = close[j] / close[i]
vol = sum( volume[i+1:j+1] )
if ret > 1.0001 and ret < 1.5 and vol > 100:
results.append( [i, j, ret, vol] )
print results
Nested loops are significantly slower; avoid them when a loop has a large number of iterations to perform. Decreasing the amount of work done per iteration and the number of loops increases loop performance. Performance is not the only thing that matters. Code readability and maintainability are key.
Using break in a nested loop In a nested loop, a break statement only stops the loop it is placed in. Therefore, if a break is placed in the inner loop, the outer loop still continues. However, if the break is placed in the outer loop, all of the looping stops.
Update: (almost) completely vectorized version below in "new_function2"...
I'll add comments to explain things in a bit.
It gives a ~50x speedup, and a larger speedup is possible if you're okay with the output being numpy arrays instead of lists. As is:
In [86]: %timeit new_function2(close, volume, INTERVAL_LENGTH)
1 loops, best of 3: 1.15 s per loop
You can replace your inner loop with a call to np.cumsum()... See my "new_function" function below. This gives a considerable speedup...
In [61]: %timeit new_function(close, volume, INTERVAL_LENGTH)
1 loops, best of 3: 15.7 s per loop
vs
In [62]: %timeit old_function(close, volume, INTERVAL_LENGTH)
1 loops, best of 3: 53.1 s per loop
It should be possible to vectorize the entire thing and avoid for loops entirely, though... Give me an minute, and I'll see what I can do...
import numpy as np
ARRAY_LENGTH = 500000
INTERVAL_LENGTH = 15
close = np.arange(ARRAY_LENGTH, dtype=np.float)
volume = np.arange(ARRAY_LENGTH, dtype=np.float)
def old_function(close, volume, INTERVAL_LENGTH):
results = []
for i in xrange(len(close) - INTERVAL_LENGTH):
for j in xrange(i+1, i+INTERVAL_LENGTH):
ret = close[j] / close[i]
vol = sum( volume[i+1:j+1] )
if (ret > 1.0001) and (ret < 1.5) and (vol > 100):
results.append( (i, j, ret, vol) )
return results
def new_function(close, volume, INTERVAL_LENGTH):
results = []
for i in xrange(close.size - INTERVAL_LENGTH):
vol = volume[i+1:i+INTERVAL_LENGTH].cumsum()
ret = close[i+1:i+INTERVAL_LENGTH] / close[i]
filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100)
j = np.arange(i+1, i+INTERVAL_LENGTH)[filter]
tmp_results = zip(j.size * [i], j, ret[filter], vol[filter])
results.extend(tmp_results)
return results
def new_function2(close, volume, INTERVAL_LENGTH):
vol, ret = [], []
I, J = [], []
for k in xrange(1, INTERVAL_LENGTH):
start = k
end = volume.size - INTERVAL_LENGTH + k
vol.append(volume[start:end])
ret.append(close[start:end])
J.append(np.arange(start, end))
I.append(np.arange(volume.size - INTERVAL_LENGTH))
vol = np.vstack(vol)
ret = np.vstack(ret)
J = np.vstack(J)
I = np.vstack(I)
vol = vol.cumsum(axis=0)
ret = ret / close[:-INTERVAL_LENGTH]
filter = (ret > 1.0001) & (ret < 1.5) & (vol > 100)
vol = vol[filter]
ret = ret[filter]
I = I[filter]
J = J[filter]
output = zip(I.flat,J.flat,ret.flat,vol.flat)
return output
results = old_function(close, volume, INTERVAL_LENGTH)
results2 = new_function(close, volume, INTERVAL_LENGTH)
results3 = new_function(close, volume, INTERVAL_LENGTH)
# Using sets to compare, as the output
# is in a different order than the original function
print set(results) == set(results2)
print set(results) == set(results3)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With