How to find longest sequence of values above threshold efficiently in R

user_4703808 0
Viewed 111

I am working on spatiotemporal observations of temperatures, stored in arrays of size 100*100*504 (100*100 grid, for 504 different hours representing 21 days). I am computing various indicators from those observations, for different periods (3 to 21 days), which obviously require some time, and I'm looking at improving computation efficiency. I am not really accustomed with R so I am not sure if what I am doing is the most efficient way.

One of the things I want to do is to find (for each cell) the longest continuous period of time where temperature is above a certain threshold. This is what I'm doing at the moment :

  1. First I compute a boolean array based on the threshold using the following function.
utci_test = array(runif(100*100*504, min = 18, max = 42), c(100,100,504))
to_hs = function(utci, period=1:length(utci[1,1,]), hs_threshold){
  utci_hs = utci*0
  utci_hs[which(utci > hs_threshold)] = 1
  utci_hs[is.na(utci)] = 0
  return(utci_hs)
}
  1. Then I transform each vector representing the hourly value for each cell into an rle object, and I return the maximum length of the 1's sequences (representing a continuous period over threshold).
max_duration_hs = function(utci_hs, period=1:length(utci_hs[1,1,]) ){
  apply(utci_hs, MARGIN=c(1,2), FUN=function(x){
    r = rle(x)
    max(r$lengths[as.logical(r$values)], fill = 0)
  })
}

Looking at the time required I noticed the second step is taking some time (bear in mind that I have to repeat this operation ~8000 times in total)

system.time(to_hs(utci_test, hs_threshold=32.0))
# utilisateur     système      écoulé 
#      0.051       0.004       0.055 
system.time(to_hs(utci_test, hs_threshold=32.0))
# utilisateur     système      écoulé 
#      0.053       0.000       0.052 
utci_test_sh = to_hs(utci_test, hs_threshold=32.0)
system.time(max_duration_hs(utci_test_sh))
# utilisateur     système      écoulé 
#      0.456       0.012       0.468

So, I'm wondering if there is a more efficient way to do this as I guess transforming into rle object might be inefficient ?

r performance
1 Answers

You can get a bit of a speed bump by writing your own version of the rle() function that works because you know you want runs of 1's, and does a little less comparison. This gets you about 2x faster, down to a median time of about 250 milliseconds or so on my machine (a generic macbook).

If you have to do this 8,000 times you'll save yourself the most time by parallelizing the code to run on a multicore machine, which is straightforward to do in R (check out e.g. the parallel package).

Below the code for the speedup.

# generate data
set.seed(123)
utci_test <- array(runif(100*100*504, min = 18, max = 42), c(100,100,504))

# original functions
to_hs = function(utci, period=1:length(utci[1,1,]), hs_threshold){
  utci_hs = utci*0
  utci_hs[which(utci > hs_threshold)] = 1
  utci_hs[is.na(utci)] = 0
  return(utci_hs)
}

max_duration_hs = function(utci_hs, period=1:length(utci_hs[1,1,]) ){
  apply(utci_hs, MARGIN=c(1,2), FUN=function(x){
    r = rle(x)
    max(r$lengths[as.logical(r$values)], fill = 0)
  })
}

# helper func for rle
rle_max <- function(v) {
  max(diff(c(0L, which(v==0), length(v)+1))) - 1
}

max_dur_hs_2 <- function(utci_hs) {
  apply(utci_hs, MARGIN=c(1,2), FUN= rle_max)
 }

# Check equivalence
utci_hs <- to_hs(utci = utci_test, hs_threshold = 32)

all.equal(max_dur_hs_2(utci_hs), 
          max_duration_hs(utci_hs))
#> [1] TRUE

# Test speed
library(microbenchmark)

microbenchmark(max_dur_hs_2(utci_hs), 
               max_duration_hs(utci_hs))
#> Unit: milliseconds
#>                      expr      min       lq     mean   median       uq      max
#>     max_dur_hs_2(utci_hs) 216.1481 236.7825 250.9277 247.9918 262.4369 296.0146
#>  max_duration_hs(utci_hs) 454.5740 476.5710 501.5119 489.9536 509.8750 774.9963
#>  neval cld
#>    100  a 
#>    100   b

Created on 2020-05-07 by the reprex package (v0.3.0)

user_49784640
Related