brodie's challenge

fugly-but-fast.R

alistaire <- function(n){
    two_rows <- rep(seq_len(n/2L), each = 4L)
    out_mat <- matrix(0L, n, n)
    index_mat <- matrix(seq_len(n), nrow = 2L)
    for (i in seq_len(n/2L)){
        out_mat[index_mat[, i], ] <- two_rows
        two_rows <- two_rows + 1L
    }
    out_mat
}

alistaire2 <- function(n){
    out_mat <- matrix(rep(seq_len(n/2L) - 1L, each = 2L), n, n)
    index_mat <- matrix(seq_len(n), nrow = 2)
    for (i in seq_len(n/2L)){
        col_indices <- index_mat[, i]
        out_mat[, col_indices] <- out_mat[, col_indices] + i
    }
    out_mat
}

cody <- function(n) {
    matrix(rep(seq_len(n/2L), each = 2L), n, n) + 
    t(matrix(rep(seq_len(n/2L) - 1L, each = 2L), n, n))
}

cody2 <- function(n) {
    matrix(rep(seq_len(n/2L), each = 2L), n, n) + 
    matrix(rep(seq_len(n/2L) - 1L, each = 2L), n, n, byrow = TRUE)
}

baptiste <-  function(n) {
    kronecker(embed(seq_len(n - 1L), n/2L)[, rev(seq_len(n/2L))], 
              matrix(1L, 2L, 2L))
}
    
n <- 5000L
times <- bench::mark(
    alistaire(n),
    alistaire2(n),
    baptiste(n),
    cody(n),
    cody2(n), 
    min_iterations = 100
)

times
#> # A tibble: 5 x 13
#>   expression      min median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory
#>   <bch:expr>    <bch> <bch:>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list>
#> 1 alistaire(n)  329ms  368ms      2.72     239MB    1.17     70    30      25.7s <int[… <df[,…
#> 2 alistaire2(n) 339ms  357ms      2.78     287MB    1.56     64    36      23.1s <int[… <df[,…
#> 3 baptiste(n)   594ms  608ms      1.64     525MB    3.24     34    67      20.7s <dbl[… <df[,…
#> 4 cody(n)       417ms  430ms      2.30     286MB    0.893    72    28      31.4s <int[… <df[,…
#> 5 cody2(n)      379ms  394ms      2.53     191MB    0.633    80    20      31.6s <int[… <df[,…
#> # … with 2 more variables: time <list>, gc <list>

ggplot2::autoplot(times)

n = 10000

> times
# A tibble: 4 x 13
  expression      min median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory time 
  <bch:expr>    <bch> <bch:>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list> <lis>
1 alistaire(n)  1.62s  1.84s     0.553  954.34MB    0.365    50    33      1.51m <int[… <df[,… <bch…
2 alistaire2(n) 1.52s  1.73s     0.576    1.12GB    0.530    50    46      1.45m <int[… <df[,… <bch…
3 cody(n)       2.46s  2.62s     0.361    1.12GB    0.368    50    51      2.31m <int[… <df[,… <bch…
4 cody2(n)      2.07s  2.17s     0.457  763.07MB    0.302    50    33      1.82m <int[… <df[,… <bch…
# … with 1 more variable: gc <list>