Efficiently check if numpy ndarray values are strictly increasing

Question

I'm having a numpy ndarray where I would like to check if each row vector is monotonically increasing.

Example:

a = np.asarray([[1,2,3],[1,5,7],[4,3,6]])
monotonically_increasing(a)

Expected return:

[True, True, False]

I'm not entirely sure how to efficiently do this, since the matrices are expected to be quite large (~1000x1000), and was hoping for some help.

Calceiform

Answer 1

>>> import numpy as np
>>> a = np.asarray([[1,2,3],[1,5,7],[4,3,6]])

Find the difference between each element. np.diff has an argument that lets you specify the axis to perform the diff

>>> np.diff(a)
array([[ 1,  1],
       [ 4,  2],
       [-1,  3]])

Check to see if each difference is greater than 0.

>>> np.diff(a) > 0
array([[ True,  True],
       [ True,  True],
       [False,  True]], dtype=bool)

Check to see if all the differences are > 0

>>> np.all(np.diff(a) > 0)
False
>>> 

---

As suggested by @Jaime - check that each element is greater than the element to its left:

np.all(a[:, 1:] >= a[:, :-1], axis=1)

Which appears to be about twice as fast/efficient as my diff solution.

Despoil

It's probably faster to compare each item to the adjacent one directly, rather than comparing if their difference is greater than zero: np.all(a[:, 1:] >= a[:, :-1], axis=1) – Poirer

Concur. Worst case yours makes one pass and mine makes one pass for the diff and a shorter pass for np.all. – Despoil

@Poirer this is indeed the case, for 10**6 elements, np.all(x[:-1] > x[1:]) takes 600us, while np.all(np.diff(x) < 0) takes 2.03ms, about 3 times longer. – Chaplin

What if for strictly decreasing ? – Teratogenic

@Teratogenic - Python - How to check list monotonicity - too bad I didn't search and find that when I answered. Others searching with variations of python numpy strictly decreasing site:stackoverflow.com - this one too Make a numpy array monotonic without a Python loop – Despoil

Answer 2

You can make a function like this:

def monotonically_increasing(l):
    return all(x < y for x, y in zip(l, l[1:]))

and then check for it, sublist for sublist, so

[monotonically_increasing(sublist) for sublist in a]

Keeleykeelhaul

the question is about numpy arrays, which may be GBs in size; looping over them is extremely slow; this answer could be improved by benchmarking various approaches with various array sizes – Tana

Answer 3

To add to the answers provided @Jaime and all, to get the exact place where there are violations, in addition to just determining if they are strictly increasing or decreasing, I chained this as follows

a = np.array( [[1,2,3], [5,4,3], [4,5,6], [4,6,3]])
a[np.where 
   ( np.invert  
     (np.all(a[:, 1:] >= a[:, :-1], axis=1)) 
   ) 
 ]
 Result:
  array([[5, 4, 3],
   [4, 6, 3]])

Torrlow

Answer 4

There was another question related to how to handle strictly decreasing from @igorkf. I combined that answer into a useful function.

def check_monotonicity (data: np.array, increasing: bool, axis: int) -> np.array :
  if increasing: # strictly increasing
    return data [np.where (
             np.invert (
                 (np.all(data[:, 1:] >= data[:, :-1], axis=axis))
             ) ) ]
  else: # strictly decreasing
    return data [np.where (
             np.invert (
                 (np.all(data[:, 0:-1] >= data[:, 1:], axis=axis))
             ) ) ]

Torrlow

Answer 5

A function f defined on a subset of the real numbers with real values is called monotonic if and only if it is either entirely non-increasing, or entirely non-decreasing.

is_monotonic = np.all(np.diff(a) > 0) | np.all(np.diff(a) < 0)

Raving