[SOLVED] Efficient method for checking monotonicity in array Julia?


Trying to come up with a fast way to make sure a is monotonic in Julia.

The slow (and obvious) way to do it that I have been using is something like this:

function check_monotonicity(
    current = timeseries[1,column]
    for row in 1:size(timeseries, 1)
        if timeseries[row,column] > current 
            return false
        current = copy(timeseries[row,column])
    return true

So that it works something like this:

julia> using Distributions

julia>mono_matrix = hcat(collect(0:0.1:10), rand(Uniform(0.4,0.6),101),reverse(collect(0.0:0.1:10.0)))
101×3 Matrix{Float64}:
  0.0  0.574138  10.0
  0.1  0.490671   9.9
  0.2  0.457519   9.8
  0.3  0.567687   9.7
  9.8  0.513691   0.2
  9.9  0.589585   0.1
 10.0  0.405018   0.0
julia> check_monotonicity(mono_matrix, 2)

And then for the opposite example:

julia> check_monotonicity(mono_matrix, 3)

Does anyone know a more efficient way to do this for long time series?


Your implementation is certainly not slow! It is very nearly optimally fast. You should definitely get rid of the copy. Though it doesn’t hurt when the matrix elements are just plain data, it can be bad in other cases, perhaps for BigInt for example.

This is close to your original effort, but also more robust with respect to indexing and array types:

function ismonotonic(A::AbstractMatrix, column::Int, cmp = <)
    current = A[begin, column] # begin instead of 1
    for i in axes(A, 1)[2:end] # skip the first element
        newval = A[i, column] # don't use copy here
        cmp(newval, current) && return false
        current = newval
    return true

Another tip: You don’t need to use collect. In fact, you should almost never use collect. Do this instead (I removed Uniform since I don’t have Distributions.jl):

mono_matrix = hcat(0:0.1:10, rand(101), reverse(0:0.1:10)) # or 10:-0.1:0

Or perhaps this is better, since you have more control over the numer of elements in the range:

mono_matrix = hcat(range(0, 10, 101), rand(101), range(10, 0, 101))

Then you can use it like this:

1.7.2> ismonotonic(mono_matrix, 3)

1.7.2> ismonotonic(mono_matrix, 3, >=)

1.7.2> ismonotonic(mono_matrix, 1)

Answered By – DNF

Answer Checked By – Timothy Miller (BugsFixing Admin)

Leave a Reply

Your email address will not be published.