Speed improvement for roll_median
#44
Comments
This comment was marked as outdated.
This comment was marked as outdated.
|
Thanks for the feedback. I recently implemented efficient algorithms for the Also available on r-universe: Could you rerun the benchmarks with version 1.1.8? |
|
Great to hear! I just re-ran the tests, and it's definitely a lot faster for the larger windows (though slower for the smaller windows). It's still about 8 times slower than library(tibble)
library(dplyr)
library(ggplot2)
library(tinytable)
library(tidyr)
library(microbenchmark)
library(zoo)
library(RollingWindow)
library(RcppRoll)
library(roll)
library(robfilter)
packageVersion("roll")
#> [1] '1.1.8'
df <- tibble(x = rnorm(1000000))
windows <- c(5, 11, 15, 21, 31, 41, 51, 61, 71, 81, 91, 101, 201, 301)
df_median <- tibble()
for (n in windows){
n_half <- floor(n/2)
res <- microbenchmark(
"RollingWindow::RollingMedian" = RollingWindow::RollingMedian(df$x, n),
"zoo::rollmedian" = zoo::rollmedian(df$x, k = n, fill = NA),
"roll::roll_median" = roll::roll_median(df$x, width = n),
"RcppRoll::roll_median" = RcppRoll::roll_median(df$x, n = n, fill = NA),
"robfilter::med.filter" = robfilter::med.filter(df$x, n, online = TRUE),
times = 5) |>
mutate(window = n)
df_median <- dplyr::bind_rows(df_median, res)
}
# Plot it
df_median_summarised <- df_median |>
group_by(expr, window) |>
summarise(time = median(time) / 1000000)
#> `summarise()` has grouped output by 'expr'. You can override using the
#> `.groups` argument.
df_median |>
mutate(time = time / 1000000) |>
ggplot(aes(window, time, colour = expr)) +
geom_jitter(alpha = 0.1) +
geom_line(data = df_median_summarised)df_median_summarised |>
pivot_wider(id_cols = window,
names_from = expr,
values_from = time) |>
tt()
sessionInfo()
#> R version 4.4.0 (2024-04-24)
#> Platform: x86_64-apple-darwin20
#> Running under: macOS 15.0
#>
#> Matrix products: default
#> BLAS: /Library/Frameworks/R.framework/Versions/4.4-x86_64/Resources/lib/libRblas.0.dylib
#> LAPACK: /Library/Frameworks/R.framework/Versions/4.4-x86_64/Resources/lib/libRlapack.dylib; LAPACK version 3.12.0
#>
#> locale:
#> [1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
#>
#> time zone: Europe/Copenhagen
#> tzcode source: internal
#>
#> attached base packages:
#> [1] stats graphics grDevices utils datasets methods base
#>
#> other attached packages:
#> [1] robfilter_4.1.5 lattice_0.22-6 MASS_7.3-60.2
#> [4] robustbase_0.99-4 roll_1.1.8 RcppRoll_0.3.1
#> [7] RollingWindow_0.2 zoo_1.8-12 microbenchmark_1.5.0
#> [10] tidyr_1.3.1 tinytable_0.4.0 ggplot2_3.5.1
#> [13] dplyr_1.1.4 tibble_3.2.1
#>
#> loaded via a namespace (and not attached):
#> [1] gtable_0.3.5 compiler_4.4.0 tidyselect_1.2.1 reprex_2.1.1
#> [5] Rcpp_1.0.13 scales_1.3.0 yaml_2.3.10 fastmap_1.2.0
#> [9] R6_2.5.1 labeling_0.4.3 generics_0.1.3 knitr_1.48
#> [13] munsell_0.5.1 pillar_1.9.0 rlang_1.1.4 utf8_1.2.4
#> [17] xfun_0.47 fs_1.6.4 RcppParallel_5.1.9 cli_3.6.3
#> [21] withr_3.0.1 magrittr_2.0.3 digest_0.6.37 grid_4.4.0
#> [25] rstudioapi_0.16.0 lifecycle_1.0.4 DEoptimR_1.1-3 vctrs_0.6.5
#> [29] evaluate_0.24.0 glue_1.7.0 farver_2.1.2 fansi_1.0.6
#> [33] colorspace_2.1-1 rmarkdown_2.28 purrr_1.0.2 tools_4.4.0
#> [37] pkgconfig_2.0.3 htmltools_0.5.8.1Created on 2024-09-19 with reprex v2.1.1 |
|
Thanks for sharing the results. The In contrast, the |
|
Sorry about the delay in getting back to you. 😊 Regarding benchmarking, I don't quite agree. The benchmarks I ran was on 1.000.000 observations, not a small number, and most users likely use it on fewer, but on multiple groups and data sets. Sure, I could run the benchmark on 1.000.000.000 observations, but I think the smaller number here is more realistic (the page you refer to also notes that "Main focus of benchmark should be on real use case scenarios"). I'd probably argue that both types of benchmarks offer insight of different types. And there's absolutely no need to run a ton of iterations if the difference is clear (the signal-to-noise ratio is good), but it certainly doesn't hurt either. As an aside, it would be great to have an example in the README explaining the different ways roll handles NAs as it's unclear from the there alone, I personally had to dig through issues and PRs to understand it. By the way, I hope this doesn't come across wrong - it's only because I find roll to be an amazing project that I'm thrilled to have come across! |
|
Agree on benchmarks and need to consider the practicality of real use cases. This further illustrates the absolute speed improvements of the algorithms rather than just relative gains. For the Closing this issue now as the benchmarks have demonstrated speed improvements. Feel free to share the blog post whenever it’s ready. |
|
Have written the first version of the blog post. I'll update it along the way. E.g. I currently don't test scaling as I did above (I'll add that next week), and I'll also try to add a table that covers the features of the different packages. Feel free to comment or open an issue if there's something you feel should be added or taken into consideration that currently isn't. :-) |
Hi @jasonjfoster!
Thanks for this amazing package first of all! I'm doing a bunch of benchmarks (I'll update once I've published them as a blog post), and roll is right up there with data.table for rolling mean and sum, and the best for min and max.
So I was surprised to see that it actually is rather slow for the rolling median - slower even than zoo for larger window widths. I've also tested the RollingWindow package, which is the fastest (an order of magnitude faster than roll), and the only one that seems not to increase time with larger window widths, so maybe it's possible to get some inspiration from their implementation to improve the speed? The package has been abandoned seemingly, and can only be installed from Github. I'm aware that it relies on
roll_quantilewhich doesn't have an online implementation, which explains why it's slower, but it still surprised me.I really like your philosophy of not making rolling functions for a ton of different things, but focusing on ensuring the ones you make are fast, which is why I thought it might be worthwhile exploring a re-implementation of
roll_medianas it's such a common function (also used in a lot of smoothing, e.g. why it's in robfilter).Here's the reprex of my test:
Created on 2024-09-19 with reprex v2.1.1
The text was updated successfully, but these errors were encountered: