Fast check of first inequality

user_10212610 0
Viewed 94

I am looking for a function similar to match, but it should have an inequality as test and stop at the first occurrence.

a <- c(1,3,5,7,9,12)
b <- 6
# the output should be 4
# i tried this one:  match(min(a [b <= a ]),a ), but with much data it is slow
r performance
4 Answers

Probably this is was fastest. @Gregor found a faster one.

which(b <= a)[1]
# [1] 4

Benchmark

set.seed(42)
a <- sort(sample(1:100, 1e6, replace=T))
b <- 6

microbenchmark::microbenchmark(match(min(a[b <= a ]), a),
                               min(which(a >= b)),
                               which(b <= a)[1],
                               match(TRUE, b <= a))

Unit: milliseconds
                    expr       min        lq      mean    median        uq       max neval cld
match(min(a[b <= a]), a) 14.273060 14.770065 27.228264 26.043620 29.675095 273.45221   100   b
      min(which(a >= b))  9.537230  9.781012 13.306348 10.207344 10.445258  27.28422   100  a
        which(b <= a)[1]  8.192664  8.475993 14.774976  8.869157 19.935542 267.22919   100  a
     match(TRUE, b <= a)  6.045952  6.274809  9.125632  6.404545  6.845165  24.42210   100  a
user_65740380

1) if you have large vectors, where the stop should happen in the beginning, like:

a <- c(1,3,5,7,9,12, 100:1e6)
b <- 6

other approaches could be faster.

2) as we are benchmarking such a fast functions also compilation could make a difference, so I defined the approaches separately:

v1 <- function() match(min(a[b <= a ]), a)
v2 <- function() min(which(a >= b))
v3 <- function() which(b <= a)[1]
v4 <- function() match(TRUE, b <= a)
v5 <- function() Position(function(x) b <= x, a)

microbenchmark::microbenchmark(
 v1(), v2(), v3(), v4(), v5()
)
# Unit: microseconds
# expr     min       lq      mean   median       uq      max neval cld
# v1() 10109.4 13822.10 23205.556 23481.95 26661.30 152809.4   100   c
# v2()  5796.8  6475.75 10404.439  6839.30 16991.90  34333.7   100  b 
# v3()  5144.8  5648.75  9381.664  5963.05  6801.25 142202.0   100  b 
# v4()  3963.0  4497.35  6938.296  4799.55  5419.80  22011.4   100  b 
# v5()     4.3    14.20    35.509    16.85    18.45   1858.8   100 a

For original data, the last approach isn't the fastest:

a <- c(1,3,5,7,9,12)
b <- 6
microbenchmark::microbenchmark(
  v1(), v2(), v3(), v4(), v5()
)
# Unit: nanoseconds
# expr  min   lq mean median   uq   max neval cld
# v1()  800  900 1151   1000 1100 12600   100  b 
# v2()  900 1000 1105   1000 1100  5600   100  b 
# v3()  800  900  953    900 1000  2700   100  b 
# v4()  400  500  584    600  600  1500   100 a  
# v5() 3600 3700 3983   3800 3900 10600   100   c

Additional comments on this can been seen, here: Find position of first value greater than X in a vector

user_70633750

findInterval gives the index of b in a or the index of the largest value in a less than b if there is no match; therefore, use findInterval and then add 1 if it is not an exact match since you want the next rather than prior index. a must be sorted in ascending order. 

ix <- findInterval(b, a, all.inside = TRUE)
ix <- ix + (a[ix] < b)

ix
## [1] 4

or possibly the first line is sufficient if you can change the requirements slightly. There is some question regarding how edge cases are to be handled but I have added all.inside = TRUE to handle one such situation.

user_5165480

You can still use match: match(TRUE, b <= a)

user_9030610
Related