By eliminating the multiple loops I take it that you would like 'vectorize' this with numpy
. That is, implement the replacement with numpy
operations that work on the whole 'matrix' at once. Technically these operations still loop, but they do so in compiled code. Usually that's faster, though the overhead of creating numpy arrays is not trivial. It also limits the value of time tests on small unrealistic samples.
Your original approach is:
def original(data):
m,n = np.shape(data)
for i in range(1,m):
for j in range(n):
if (data[i][j]=='N') or (data[i][j]<0):
data[i][j] = data[i-1][j]
data = [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]]
original(data)
producing a modified data
:
[[0, -1, 2], [7, 8.1, 2], [7, 5, 2], [7, 7, 2]]
Here numpy
is used only to get the dimensions of the nested list. The rest is pure list iteration. I changed the test a bit because I'm using Python3, which does not have long
, and does not like doing 'N'<0
. In a real world application the test would be wrapped in a function that can hide all the nuances.
With the Ipython
timing magic
In [333]: %%timeit data = [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]]
original(data)
.....:
100000 loops, best of 3: 17.9 µs per loop
For this small size list that time does not look bad. It would be interesting to see if John Hall's
alternatives improve on this.
data
as it stands does not translate well into a numpy array. That letter produces a character array, not a numeric one
In [336]: np.array(data)
Out[336]:
array([['0', '-1', '2'],
['7', '8.1', '-3'],
['-8', '5', '-1'],
['N', '7', '-1']],
dtype='<U3')
Changing 'N'
to np.nan
does better:
In [338]: data = np.array([[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], [np.nan, 7, -1]])
In [339]: data
Out[339]:
array([[ 0. , -1. , 2. ],
[ 7. , 8.1, -3. ],
[-8. , 5. , -1. ],
[ nan, 7. , -1. ]])
To simplify further exploration, I'm going to change the 'N'
to a negative number.
data = np.array([[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], [-100, 7, -1]])
Admittedly if you have to iterate through the whole nested list to convert letters to negative numbers, you might as well do this duplication business at the same time.
But continuing with the array exploration
The inner loop could be replaced with a masked replacement
def oneloop(data):
for i in range(1, data.shape[0]):
j = data[i]<0
data[i,j] = data[i-1,j]
But timing looks bad
In [354]: %%timeit data = np.array([[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], [-100, 7, -1]])
oneloop(data)
.....:
10000 loops, best of 3: 67.3 µs per loop
Two things - masked or advanced indexing is slower than indexing with slices. It can't work with contiguous blocks of data. And the small array size means the array overhead is relatively large.
I didn't replace the row iteration because the changes we desire to make to row i
depend on changes, if any, made to row i-1
. That kind of sequential iteration does not fit well with numpy matrix operations. (todo - try to use ufunc method .at
)
Ignoring the chaining, I generate a mask for the whole array:
In [361]: J=data[1:]<0
In [362]: J
Out[362]:
array([[False, False, True],
[ True, False, True],
[ True, False, True]], dtype=bool)
In [363]: data[1:][J] = data[:-1][J]
In [364]: data
Out[364]:
array([[ 0. , -1. , 2. ],
[ 7. , 8.1, 2. ],
[ 7. , 5. , -3. ],
[-8. , 7. , -1. ]])
This changes each negative to the value of the row before, but does not chain the result. But I could repeat the operation until no negatives remain:
def whileloop(data):
while True:
J = data[1:]<0
if np.any(J):
data[1:][J] = data[:-1][J]
else:
break
In [359]: %%timeit data = np.array([[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], [-100, 7, -1]])
whileloop(data)
.....:
10000 loops, best of 3: 27.7 µs per loop
Even in this case where the chain extends all the way, it is still faster than oneloop
. How this translates to a large realistic array is still a guess.
Replacing the boolean index with np.where
improves speed
def foo1(data):
while True:
i,j = np.where(data[1:]<0)
if i.shape[0]==0: break
data[1:][i,j] = data[:-1][i,j]
# or data[i+1,j] = data[i,j]
In [381]: %%timeit data = np.array([[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], [-100, 7, -1]])
foo1(data)
.....:
100000 loops, best of 3: 14.8 µs per loop
O(N)
, what's the issue? Have you had actual problems with the execution when using your real input matrix? I don't think you can get much faster than this. \$\endgroup\$for
loops \$\endgroup\$numpy
for anything but determining the dimensions of the nested list? \$\endgroup\$numpy
array, it is possible 'vectorize' the inner loop by using a boolean mask. RoughlyJ = data[i]<0; data[i, J] = data[i-1, j]
. The only hope for 'vectorizing' the outer loop might be a clever use of the ufunc.at
method (which bypasses some buffering issues). \$\endgroup\$