3
\$\begingroup\$

I have the following code which duplicates the previous input if any entry is less than zero or NaN, except the first row of a matrix.

Is there any other efficient way to do this without using multiple for loops? The input matrix values may differ in some case and may contain float values or alphabets. The matrix considered here is just an example. The actual table will be 14352 x 42 in shape.

import numpy as np

data = [[0, -1, 2],
        [7, 8.1, -3],
        [-8, 5, -1],
        ['N', 7, -1]]
m, n = np.shape(data)

for i in range(1, m):
    for j in range(n):
        if data[i][j] < 0 or not isinstance(data[i][j], (int, float,long)):
            data[i][j] = data[i-1][j]

The output is:

[[0,-1,2],
 [7,8.1,2],
 [7,5,2],
 [7,7,2]]
\$\endgroup\$
6
  • \$\begingroup\$ This is 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\$ – Markus Meskanen Aug 18 '15 at 12:04
  • \$\begingroup\$ No, I am trying to reduce the for loops \$\endgroup\$ – ita Aug 18 '15 at 12:07
  • 1
    \$\begingroup\$ Two for loops on a two dimensional matrix, I honestly don't see any issue here. \$\endgroup\$ – Markus Meskanen Aug 18 '15 at 12:08
  • \$\begingroup\$ Are you using numpy for anything but determining the dimensions of the nested list? \$\endgroup\$ – hpaulj Aug 22 '15 at 17:44
  • \$\begingroup\$ If the 'matrix' is a numpy array, it is possible 'vectorize' the inner loop by using a boolean mask. Roughly J = 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\$ – hpaulj Aug 23 '15 at 0:07
3
\$\begingroup\$

It's possible to solve this problem using a functional Pythonic approach a layer at a time.

First, the original code is refactored as functions for reference. Long type and numpy were not available on my current workstation but were not necessary to process the example data. A transpose and substituting generator are used to produce an alternative proof of concept. It is elaborated to include a "first qualified value or default to 0" rule because the original algorithm did not clean the first row and propagates unqualified values in a column until a qualified value occurs.

I've included a demo at the end that shows why a list comprehension fails since It does not alter the table in place.

#original code refactored as functions
data = [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]]
print("data: ", data)
def unnumeric_or_neg(z):
    return not isinstance(z, (int, float)) or z < 0

def clean1 (data,unqal):
    m, n = 4,3
    for i in range(1, m):
        for j in range(n):
            if unqal(data[i][j]) :
                data[i][j] = data[i-1][j]
clean1(data,unnumeric_or_neg)
print("result is in data", data)
#refresh data
data = [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]]
#help functions and another approach
def comp_transpose(t):
    "transpostion of rectangular table"
    return [[r[j] for r in t] for j,_ in enumerate(t[0])]

def sub_last_qal(lst,unqal):
    last_qual=0
    for (n,x) in enumerate(lst):
        if unqal(x):
            yield last_qual
        else:
            last_qual = x
            yield x
def clean2(data,unqal):
    data_t = comp_transpose(data)
    data_aug = [list(sub_last_qal(col,unqal)) for col in data_t]
    return [data[0],]+comp_transpose(data_aug)[1:]
print("2 step similar result",clean2(data,unnumeric_or_neg))
def first_qal(lst,unqal):
    """given a list return the first qualifying value given
    negative test unqal is set in scope"""
    for x in lst:
        if not unqal(x):
            return x
    return 0
def clean3(data,unqal):
    data_t = comp_transpose(data)
    data_aug = [list(sub_last_qal([first_qal(col,unqal),]+col,unqal)) for col in data_t]
    return comp_transpose(data_aug)[1:]
cn3 = clean3(data,unnumeric_or_neg)
print("augmented first qual rule ",cn3)

def first_qal_row(data_c,unqual):
    return [ first_qal(vlist,unqual) for vlist in comp_transpose(data_c)]

#list comprehensions do not support back references to results
def not_clean(data,unqal):
    return [data[0],]+[[(data[i-1][j] if unqal(x) else x ) \
        for (i,x) in enumerate(y)] for (j,y) in enumerate(data[1:])]
cn = not_clean(data,unnumeric_or_neg)
print("result is unclean", cn)
print("data is not changed ", data == [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]])

Output:

data:  [[0, -1, 2], [7, 8.1, -3], [-8, 5, -1], ['N', 7, -1]]
result is in data [[0, -1, 2], [7, 8.1, 2], [7, 5, 2], [7, 7, 2]]
2 step similar result [[0, -1, 2], [7, 8.1, 2], [7, 5, 2], [7, 7, 2]]
augmented first qual rule  [[0, 8.1, 2], [7, 8.1, 2], [7, 5, 2], [7, 7, 2]]
result is unclean [[0, -1, 2], [7, 8.1, 7], [7, 5, 8.1], [-1, 7, -3]]
data is not changed  True
\$\endgroup\$
2
\$\begingroup\$

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
\$\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.