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

Issue

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(
    timeseries::Array,
    column::Int
)
    current = timeseries[1,column]
    for row in 1:size(timeseries, 1)
        if timeseries[row,column] > current 
            return false
        end 
        current = copy(timeseries[row,column])
    end 
    return true
end

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)
false

And then for the opposite example:

julia> check_monotonicity(mono_matrix, 3)
true

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

Solution

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
    end
    return true
end

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)
false

1.7.2> ismonotonic(mono_matrix, 3, >=)
true

1.7.2> ismonotonic(mono_matrix, 1)
true

Answered By – DNF

Answer Checked By – Timothy Miller (BugsFixing Admin)