# Binary segmentation examples

In this vignette we explore the differences in asymptotic time complexity between different implementations of binary segmentation.

## Asymptotic time/memory measurement of different R expressions

The code below uses the following arguments:

• N is a numeric vector of data sizes,
• setup is an R expression to create the data,
• the other arguments have names to identify them in the results, and values which are R expressions to time,
library(data.table)
atime.list <- atime::atime(
N=2^seq(2, 20),
setup={
max.segs <- as.integer(N/2)
max.changes <- max.segs-1L
set.seed(1)
data.vec <- 1:N
},
"changepoint::cpt.mean"={
cpt.fit <- changepoint::cpt.mean(data.vec, method="BinSeg", Q=max.changes)
sort(c(N,cpt.fit@cpts.full[max.changes,]))
},
"binsegRcpp::binseg_normal"={
binseg.fit <- binsegRcpp::binseg_normal(data.vec, max.segs)
sort(binseg.fit$splits$end)
},
"fpop::multiBinSeg"={
mbs.fit <- fpop::multiBinSeg(data.vec, max.changes)
sort(c(mbs.fit$t.est, N)) }, "wbs::sbs"={ wbs.fit <- wbs::sbs(data.vec) split.dt <- data.table(wbs.fit$res)[order(-min.th, scale)]
sort(split.dt[, c(N, cpt)][1:max.segs])
},
binsegRcpp.list={
binseg.fit <- binsegRcpp::binseg(
"mean_norm", data.vec, max.segs, container.str="list")
sort(binseg.fit$splits$end)
},
##seconds.limit=0.1,
times=5)
plot(atime.list)


The default plot method creates a log-log plot of median time vs data size, for each of the specified R expressions. You can use references_best to get a tall/long data table that can be plotted to show both empirical time and memory complexity:

best.list <- atime::references_best(atime.list)
if(require(ggplot2)){
hline.df <- with(atime.list, data.frame(seconds.limit, unit="seconds"))
gg.both <- ggplot()+
theme_bw()+
facet_grid(unit ~ ., scales="free")+
geom_hline(aes(
yintercept=seconds.limit),
color="grey",
data=hline.df)+
geom_line(aes(
N, empirical, color=expr.name),
data=best.list$meas)+ geom_ribbon(aes( N, ymin=min, ymax=max, fill=expr.name), data=best.list$meas[unit=="seconds"],
alpha=0.5)+
scale_x_log10()+
scale_y_log10("median line, min/max band")
if(require(directlabels)){
gg.both+
directlabels::geom_dl(aes(
N, empirical, color=expr.name, label=expr.name),
method="right.polygons",
data=best.list$meas)+ theme(legend.position="none")+ coord_cartesian(xlim=c(1,2e7)) }else{ gg.both } } #> Warning: Transformation introduced infinite values in continuous y-axis #> Transformation introduced infinite values in continuous y-axis  The plots above show some speed differences between binary segmentation algorithms, but they could be even easier to see for larger data sizes (exercise for the reader: try modifying the N and seconds.limit arguments). You can also see that memory usage is much larger for changepoint than for the other packages. ## Closest asymptotic references You can use code like below to compute asymptotic references which are best fit for each expression. We do the best fit by adjusting each reference to the largest N, and then ranking each reference by distance to the measurement of the second to largest N. The code below uses each.sign.rank==1 to compute the closest reference above and below, best.refs <- best.list$ref[each.sign.rank==1]
(time.refs <- best.refs[unit=="seconds"])
#>        unit                 expr.name   fun.latex  fun.name     N empirical
#>      <char>                    <char>      <char>    <char> <num>     <num>
#>  1: seconds     changepoint::cpt.mean N^2 \\log N N^2 log N    64 0.0006806
#>  2: seconds     changepoint::cpt.mean N^2 \\log N N^2 log N   128 0.0015243
#>  3: seconds     changepoint::cpt.mean N^2 \\log N N^2 log N   256 0.0028454
#>  4: seconds     changepoint::cpt.mean N^2 \\log N N^2 log N   512 0.0095882
#>  5: seconds     changepoint::cpt.mean N^2 \\log N N^2 log N  1024 0.0426579
#>  6: seconds     changepoint::cpt.mean         N^3       N^3   128 0.0015243
#>  7: seconds     changepoint::cpt.mean         N^3       N^3   256 0.0028454
#>  8: seconds     changepoint::cpt.mean         N^3       N^3   512 0.0095882
#>  9: seconds     changepoint::cpt.mean         N^3       N^3  1024 0.0426579
#> 10: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N     4 0.0011581
#> 11: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N     8 0.0012121
#> 12: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N    16 0.0011799
#> 13: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N    32 0.0012079
#> 14: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N    64 0.0012091
#> 15: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N   128 0.0014017
#> 16: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N   256 0.0013594
#> 17: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N   512 0.0014678
#> 18: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N  1024 0.0015743
#> 19: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N  2048 0.0022298
#> 20: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N  4096 0.0042076
#> 21: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N  8192 0.0074088
#> 22: seconds binsegRcpp::binseg_normal    \\sqrt N    sqrt N 16384 0.0117257
#> 23: seconds binsegRcpp::binseg_normal           N         N   128 0.0014017
#> 24: seconds binsegRcpp::binseg_normal           N         N   256 0.0013594
#> 25: seconds binsegRcpp::binseg_normal           N         N   512 0.0014678
#> 26: seconds binsegRcpp::binseg_normal           N         N  1024 0.0015743
#> 27: seconds binsegRcpp::binseg_normal           N         N  2048 0.0022298
#> 28: seconds binsegRcpp::binseg_normal           N         N  4096 0.0042076
#> 29: seconds binsegRcpp::binseg_normal           N         N  8192 0.0074088
#> 30: seconds binsegRcpp::binseg_normal           N         N 16384 0.0117257
#> 31: seconds         fpop::multiBinSeg           N         N   128 0.0001044
#> 32: seconds         fpop::multiBinSeg           N         N   256 0.0001461
#> 33: seconds         fpop::multiBinSeg           N         N   512 0.0002638
#> 34: seconds         fpop::multiBinSeg           N         N  1024 0.0004573
#> 35: seconds         fpop::multiBinSeg           N         N  2048 0.0008781
#> 36: seconds         fpop::multiBinSeg           N         N  4096 0.0018928
#> 37: seconds         fpop::multiBinSeg           N         N  8192 0.0035885
#> 38: seconds         fpop::multiBinSeg           N         N 16384 0.0076828
#> 39: seconds         fpop::multiBinSeg           N         N 32768 0.0158226
#> 40: seconds         fpop::multiBinSeg   N \\log N   N log N   256 0.0001461
#> 41: seconds         fpop::multiBinSeg   N \\log N   N log N   512 0.0002638
#> 42: seconds         fpop::multiBinSeg   N \\log N   N log N  1024 0.0004573
#> 43: seconds         fpop::multiBinSeg   N \\log N   N log N  2048 0.0008781
#> 44: seconds         fpop::multiBinSeg   N \\log N   N log N  4096 0.0018928
#> 45: seconds         fpop::multiBinSeg   N \\log N   N log N  8192 0.0035885
#> 46: seconds         fpop::multiBinSeg   N \\log N   N log N 16384 0.0076828
#> 47: seconds         fpop::multiBinSeg   N \\log N   N log N 32768 0.0158226
#> 48: seconds                  wbs::sbs    \\sqrt N    sqrt N     4 0.0009284
#> 49: seconds                  wbs::sbs    \\sqrt N    sqrt N     8 0.0009728
#> 50: seconds                  wbs::sbs    \\sqrt N    sqrt N    16 0.0009764
#> 51: seconds                  wbs::sbs    \\sqrt N    sqrt N    32 0.0009763
#> 52: seconds                  wbs::sbs    \\sqrt N    sqrt N    64 0.0010639
#> 53: seconds                  wbs::sbs    \\sqrt N    sqrt N   128 0.0013404
#> 54: seconds                  wbs::sbs    \\sqrt N    sqrt N   256 0.0011391
#> 55: seconds                  wbs::sbs    \\sqrt N    sqrt N   512 0.0010643
#> 56: seconds                  wbs::sbs    \\sqrt N    sqrt N  1024 0.0015308
#> 57: seconds                  wbs::sbs    \\sqrt N    sqrt N  2048 0.0020376
#> 58: seconds                  wbs::sbs    \\sqrt N    sqrt N  4096 0.0033856
#> 59: seconds                  wbs::sbs    \\sqrt N    sqrt N  8192 0.0053414
#> 60: seconds                  wbs::sbs    \\sqrt N    sqrt N 16384 0.0086899
#> 61: seconds                  wbs::sbs    \\sqrt N    sqrt N 32768 0.0153591
#> 62: seconds                  wbs::sbs           N         N   128 0.0013404
#> 63: seconds                  wbs::sbs           N         N   256 0.0011391
#> 64: seconds                  wbs::sbs           N         N   512 0.0010643
#> 65: seconds                  wbs::sbs           N         N  1024 0.0015308
#> 66: seconds                  wbs::sbs           N         N  2048 0.0020376
#> 67: seconds                  wbs::sbs           N         N  4096 0.0033856
#> 68: seconds                  wbs::sbs           N         N  8192 0.0053414
#> 69: seconds                  wbs::sbs           N         N 16384 0.0086899
#> 70: seconds                  wbs::sbs           N         N 32768 0.0153591
#> 71: seconds           binsegRcpp.list   N \\log N   N log N    64 0.0012074
#> 72: seconds           binsegRcpp.list   N \\log N   N log N   128 0.0014042
#> 73: seconds           binsegRcpp.list   N \\log N   N log N   256 0.0012618
#> 74: seconds           binsegRcpp.list   N \\log N   N log N   512 0.0016393
#> 75: seconds           binsegRcpp.list   N \\log N   N log N  1024 0.0021220
#> 76: seconds           binsegRcpp.list   N \\log N   N log N  2048 0.0038511
#> 77: seconds           binsegRcpp.list   N \\log N   N log N  4096 0.0122753
#> 78: seconds           binsegRcpp.list         N^2       N^2   512 0.0016393
#> 79: seconds           binsegRcpp.list         N^2       N^2  1024 0.0021220
#> 80: seconds           binsegRcpp.list         N^2       N^2  2048 0.0038511
#> 81: seconds           binsegRcpp.list         N^2       N^2  4096 0.0122753
#>        unit                 expr.name   fun.latex  fun.name     N empirical
#>        reference  rank   i.N i.empirical i.reference i.rank          dist  sign
#>            <num> <num> <num>       <num>       <num>  <num>         <num> <num>
#>  1: 9.997945e-05     5   512   0.0095882 0.009598027      2 -0.0004449055    -1
#>  2: 4.665708e-04     4   512   0.0095882 0.009598027      2 -0.0004449055    -1
#>  3: 2.132895e-03     3   512   0.0095882 0.009598027      2 -0.0004449055    -1
#>  4: 9.598027e-03     2   512   0.0095882 0.009598027      2 -0.0004449055    -1
#>  5: 4.265790e-02     1   512   0.0095882 0.009598027      2 -0.0004449055    -1
#>  6: 8.331621e-05     4   512   0.0095882 0.005332238      2  0.2548275996     1
#>  7: 6.665297e-04     3   512   0.0095882 0.005332238      2  0.2548275996     1
#>  8: 5.332238e-03     2   512   0.0095882 0.005332238      2  0.2548275996     1
#>  9: 4.265790e-02     1   512   0.0095882 0.005332238      2  0.2548275996     1
#> 10: 1.832141e-04    13  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 11: 2.591038e-04    12  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 12: 3.664281e-04    11  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 13: 5.182076e-04    10  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 14: 7.328563e-04     9  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 15: 1.036415e-03     8  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 16: 1.465713e-03     7  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 17: 2.072830e-03     6  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 18: 2.931425e-03     5  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 19: 4.145661e-03     4  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 20: 5.862850e-03     3  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 21: 8.291322e-03     2  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 22: 1.172570e-02     1  8192   0.0074088 0.008291322      2 -0.0488759096    -1
#> 23: 9.160703e-05     8  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 24: 1.832141e-04     7  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 25: 3.664281e-04     6  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 26: 7.328563e-04     5  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 27: 1.465713e-03     4  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 28: 2.931425e-03     3  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 29: 5.862850e-03     2  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 30: 1.172570e-02     1  8192   0.0074088 0.005862850      2  0.1016390882     1
#> 31: 6.180703e-05     9 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 32: 1.236141e-04     8 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 33: 2.472281e-04     7 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 34: 4.944563e-04     6 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 35: 9.889125e-04     5 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 36: 1.977825e-03     4 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 37: 3.955650e-03     3 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 38: 7.911300e-03     2 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 39: 1.582260e-02     1 16384   0.0076828 0.007911300      2 -0.0127283258    -1
#> 40: 6.592750e-05     8 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 41: 1.483369e-04     7 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 42: 3.296375e-04     6 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 43: 7.252025e-04     5 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 44: 1.582260e-03     4 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 45: 3.428230e-03     3 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 46: 7.383880e-03     2 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 47: 1.582260e-02     1 16384   0.0076828 0.007383880      2  0.0172348976     1
#> 48: 1.696957e-04    14 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 49: 2.399859e-04    13 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 50: 3.393914e-04    12 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 51: 4.799719e-04    11 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 52: 6.787827e-04    10 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 53: 9.599438e-04     9 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 54: 1.357565e-03     8 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 55: 1.919888e-03     7 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 56: 2.715131e-03     6 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 57: 3.839775e-03     5 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 58: 5.430262e-03     4 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 59: 7.679550e-03     3 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 60: 1.086052e-02     2 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 61: 1.535910e-02     1 16384   0.0086899 0.010860524      2 -0.0968359914    -1
#> 62: 5.999648e-05     9 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 63: 1.199930e-04     8 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 64: 2.399859e-04     7 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 65: 4.799719e-04     6 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 66: 9.599438e-04     5 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 67: 1.919888e-03     4 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 68: 3.839775e-03     3 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 69: 7.679550e-03     2 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 70: 1.535910e-02     1 16384   0.0086899 0.007679550      2  0.0536790064     1
#> 71: 9.590078e-05     7  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 72: 2.237685e-04     6  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 73: 5.114708e-04     5  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 74: 1.150809e-03     4  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 75: 2.557354e-03     3  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 76: 5.626179e-03     2  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 77: 1.227530e-02     1  2048   0.0038511 0.005626179      2 -0.1646287623    -1
#> 78: 1.918016e-04     4  2048   0.0038511 0.003068825      2  0.0986126725     1
#> 79: 7.672063e-04     3  2048   0.0038511 0.003068825      2  0.0986126725     1
#> 80: 3.068825e-03     2  2048   0.0038511 0.003068825      2  0.0986126725     1
#> 81: 1.227530e-02     1  2048   0.0038511 0.003068825      2  0.0986126725     1
#>        reference  rank   i.N i.empirical i.reference i.rank          dist  sign
#>     overall.rank each.sign.rank
#>            <num>          <num>
#>  1:            1              1
#>  2:            1              1
#>  3:            1              1
#>  4:            1              1
#>  5:            1              1
#>  6:            3              1
#>  7:            3              1
#>  8:            3              1
#>  9:            3              1
#> 10:            1              1
#> 11:            1              1
#> 12:            1              1
#> 13:            1              1
#> 14:            1              1
#> 15:            1              1
#> 16:            1              1
#> 17:            1              1
#> 18:            1              1
#> 19:            1              1
#> 20:            1              1
#> 21:            1              1
#> 22:            1              1
#> 23:            2              1
#> 24:            2              1
#> 25:            2              1
#> 26:            2              1
#> 27:            2              1
#> 28:            2              1
#> 29:            2              1
#> 30:            2              1
#> 31:            1              1
#> 32:            1              1
#> 33:            1              1
#> 34:            1              1
#> 35:            1              1
#> 36:            1              1
#> 37:            1              1
#> 38:            1              1
#> 39:            1              1
#> 40:            2              1
#> 41:            2              1
#> 42:            2              1
#> 43:            2              1
#> 44:            2              1
#> 45:            2              1
#> 46:            2              1
#> 47:            2              1
#> 48:            3              1
#> 49:            3              1
#> 50:            3              1
#> 51:            3              1
#> 52:            3              1
#> 53:            3              1
#> 54:            3              1
#> 55:            3              1
#> 56:            3              1
#> 57:            3              1
#> 58:            3              1
#> 59:            3              1
#> 60:            3              1
#> 61:            3              1
#> 62:            1              1
#> 63:            1              1
#> 64:            1              1
#> 65:            1              1
#> 66:            1              1
#> 67:            1              1
#> 68:            1              1
#> 69:            1              1
#> 70:            1              1
#> 71:            3              1
#> 72:            3              1
#> 73:            3              1
#> 74:            3              1
#> 75:            3              1
#> 76:            3              1
#> 77:            3              1
#> 78:            1              1
#> 79:            1              1
#> 80:            1              1
#> 81:            1              1
#>     overall.rank each.sign.rank


Then you can plot these references with the empirical data using the ggplot code below,

ref.color <- "red"
## try() to avoid CRAN error 'from' must be a finite number, on
## Flavors: r-devel-linux-x86_64-debian-gcc, r-release-linux-x86_64,
## due to https://github.com/r-lib/scales/issues/307
(seconds.dt <- best.list$meas[unit=="seconds"]) #> unit N expr.name min median itr/sec #> <char> <num> <char> <num> <num> <num> #> 1: seconds 4 changepoint::cpt.mean 0.0003476 0.0003581 2664.35756 #> 2: seconds 8 changepoint::cpt.mean 0.0004182 0.0004255 2193.84845 #> 3: seconds 16 changepoint::cpt.mean 0.0004555 0.0004716 1955.49298 #> 4: seconds 32 changepoint::cpt.mean 0.0005064 0.0005301 1747.51852 #> 5: seconds 64 changepoint::cpt.mean 0.0006489 0.0006806 1432.74686 #> 6: seconds 128 changepoint::cpt.mean 0.0012199 0.0015243 635.27558 #> 7: seconds 256 changepoint::cpt.mean 0.0027500 0.0028454 350.86734 #> 8: seconds 512 changepoint::cpt.mean 0.0094915 0.0095882 104.04874 #> 9: seconds 1024 changepoint::cpt.mean 0.0425511 0.0426579 23.35668 #> 10: seconds 4 binsegRcpp::binseg_normal 0.0011419 0.0011581 809.06149 #> 11: seconds 8 binsegRcpp::binseg_normal 0.0011690 0.0012121 783.66221 #> 12: seconds 16 binsegRcpp::binseg_normal 0.0011571 0.0011799 817.98253 #> 13: seconds 32 binsegRcpp::binseg_normal 0.0011854 0.0012079 807.40226 #> 14: seconds 64 binsegRcpp::binseg_normal 0.0011676 0.0012091 796.86355 #> 15: seconds 128 binsegRcpp::binseg_normal 0.0013572 0.0014017 709.93735 #> 16: seconds 256 binsegRcpp::binseg_normal 0.0012912 0.0013594 724.37523 #> 17: seconds 512 binsegRcpp::binseg_normal 0.0013334 0.0014678 684.48144 #> 18: seconds 1024 binsegRcpp::binseg_normal 0.0015275 0.0015743 607.91013 #> 19: seconds 2048 binsegRcpp::binseg_normal 0.0019778 0.0022298 393.85895 #> 20: seconds 4096 binsegRcpp::binseg_normal 0.0041151 0.0042076 237.44622 #> 21: seconds 8192 binsegRcpp::binseg_normal 0.0069979 0.0074088 138.08626 #> 22: seconds 16384 binsegRcpp::binseg_normal 0.0112815 0.0117257 86.83646 #> 23: seconds 4 fpop::multiBinSeg 0.0000496 0.0000554 16485.32806 #> 24: seconds 8 fpop::multiBinSeg 0.0000515 0.0000568 15948.96332 #> 25: seconds 16 fpop::multiBinSeg 0.0000571 0.0000606 15188.33536 #> 26: seconds 32 fpop::multiBinSeg 0.0000635 0.0000696 13709.89855 #> 27: seconds 64 fpop::multiBinSeg 0.0000817 0.0000860 10658.70816 #> 28: seconds 128 fpop::multiBinSeg 0.0000983 0.0001044 8643.04235 #> 29: seconds 256 fpop::multiBinSeg 0.0001412 0.0001461 6275.10040 #> 30: seconds 512 fpop::multiBinSeg 0.0002448 0.0002638 3647.23904 #> 31: seconds 1024 fpop::multiBinSeg 0.0004526 0.0004573 2148.87399 #> 32: seconds 2048 fpop::multiBinSeg 0.0008694 0.0008781 1125.26444 #> 33: seconds 4096 fpop::multiBinSeg 0.0017559 0.0018928 545.86643 #> 34: seconds 8192 fpop::multiBinSeg 0.0035621 0.0035885 272.09552 #> 35: seconds 16384 fpop::multiBinSeg 0.0075842 0.0076828 129.66469 #> 36: seconds 32768 fpop::multiBinSeg 0.0155764 0.0158226 62.75494 #> 37: seconds 4 wbs::sbs 0.0008916 0.0009284 1056.01081 #> 38: seconds 8 wbs::sbs 0.0009138 0.0009728 1006.80601 #> 39: seconds 16 wbs::sbs 0.0009661 0.0009764 970.13912 #> 40: seconds 32 wbs::sbs 0.0009413 0.0009763 1000.64041 #> 41: seconds 64 wbs::sbs 0.0009280 0.0010639 944.09093 #> 42: seconds 128 wbs::sbs 0.0010934 0.0013404 698.04130 #> 43: seconds 256 wbs::sbs 0.0010755 0.0011391 854.40875 #> 44: seconds 512 wbs::sbs 0.0010347 0.0010643 893.03256 #> 45: seconds 1024 wbs::sbs 0.0013307 0.0015308 658.42321 #> 46: seconds 2048 wbs::sbs 0.0018771 0.0020376 487.57179 #> 47: seconds 4096 wbs::sbs 0.0027530 0.0033856 295.56417 #> 48: seconds 8192 wbs::sbs 0.0050595 0.0053414 187.92489 #> 49: seconds 16384 wbs::sbs 0.0082104 0.0086899 117.21921 #> 50: seconds 32768 wbs::sbs 0.0133442 0.0153591 69.98978 #> 51: seconds 4 binsegRcpp.list 0.0011258 0.0011288 855.40272 #> 52: seconds 8 binsegRcpp.list 0.0012047 0.0012240 795.91219 #> 53: seconds 16 binsegRcpp.list 0.0011251 0.0011591 817.83535 #> 54: seconds 32 binsegRcpp.list 0.0011430 0.0011840 838.96840 #> 55: seconds 64 binsegRcpp.list 0.0011839 0.0012074 783.96939 #> 56: seconds 128 binsegRcpp.list 0.0013015 0.0014042 625.54735 #> 57: seconds 256 binsegRcpp.list 0.0012257 0.0012618 775.79519 #> 58: seconds 512 binsegRcpp.list 0.0014270 0.0016393 617.07064 #> 59: seconds 1024 binsegRcpp.list 0.0020595 0.0021220 464.47250 #> 60: seconds 2048 binsegRcpp.list 0.0036596 0.0038511 236.83326 #> 61: seconds 4096 binsegRcpp.list 0.0122287 0.0122753 79.91191 #> unit N expr.name min median itr/sec #> gc/sec n_itr n_gc result memory #> <num> <int> <num> <list> <list> #> 1: 1332.178778 4 2 0,4 <Rprofmem[2757x3]> #> 2: 0.000000 5 0 0,2,4,8 <Rprofmem[12x3]> #> 3: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[11x3]> #> 4: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[16x3]> #> 5: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[86x3]> #> 6: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[215x3]> #> 7: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[435x3]> #> 8: 0.000000 5 0 0, 2, 4, 6, 8,10,... <Rprofmem[845x3]> #> 9: 5.839171 4 1 0, 2, 4, 6, 8,10,... <Rprofmem[1640x3]> #> 10: 0.000000 5 0 2,4 <Rprofmem[1514x3]> #> 11: 0.000000 5 0 2,4,6,8 <Rprofmem[11x3]> #> 12: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[12x3]> #> 13: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[24x3]> #> 14: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[74x3]> #> 15: 177.484337 4 1 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 16: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 17: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 18: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 19: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 20: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 21: 34.521566 4 1 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 22: 57.890974 3 2 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 23: 0.000000 5 0 2,4 <Rprofmem[31x3]> #> 24: 0.000000 5 0 2,4,6,8 <Rprofmem[0x3]> #> 25: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[0x3]> #> 26: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[2x3]> #> 27: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[6x3]> #> 28: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 29: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 30: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 31: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 32: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 33: 136.466607 4 1 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 34: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 35: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 36: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[9x3]> #> 37: 0.000000 5 0 2,4 <Rprofmem[109x3]> #> 38: 0.000000 5 0 2,4,6,8 <Rprofmem[16x3]> #> 39: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[15x3]> #> 40: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[38x3]> #> 41: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[47x3]> #> 42: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 43: 213.602187 4 1 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 44: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 45: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 46: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 47: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 48: 46.981222 4 1 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 49: 29.304802 4 1 2, 4, 6, 8,10,12,... <Rprofmem[49x3]> #> 50: 46.659854 3 2 2, 4, 6, 8,10,12,... <Rprofmem[79x3]> #> 51: 0.000000 5 0 2,4 <Rprofmem[11x3]> #> 52: 0.000000 5 0 2,4,6,8 <Rprofmem[11x3]> #> 53: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[12x3]> #> 54: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[24x3]> #> 55: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[74x3]> #> 56: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 57: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 58: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 59: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> 60: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[207x3]> #> 61: 0.000000 5 0 2, 4, 6, 8,10,12,... <Rprofmem[131x3]> #> gc/sec n_itr n_gc result memory #> time gc kilobytes #> <list> <list> <num> #> 1: 124ms,442µs,358µs,354µs,348µs <tbl_df[5x3]> 6415.765625 #> 2: 559µs,418µs,453µs,423µs,426µs <tbl_df[5x3]> 18.664062 #> 3: 671µs,496µs,463µs,472µs,456µs <tbl_df[5x3]> 3.523438 #> 4: 743µs,553µs,506µs,530µs,529µs <tbl_df[5x3]> 10.750000 #> 5: 814µs,688µs,649µs,658µs,681µs <tbl_df[5x3]> 51.437500 #> 6: 1.52ms,1.22ms,1.23ms,1.88ms,2.02ms <tbl_df[5x3]> 191.421875 #> 7: 2.94ms,2.85ms,2.89ms,2.75ms,2.83ms <tbl_df[5x3]> 697.210938 #> 8: 9.58ms,9.49ms,9.59ms,9.69ms,9.7ms <tbl_df[5x3]> 2619.789062 #> 9: 42.7ms,42.6ms,42.6ms,47.7ms,43.4ms <tbl_df[5x3]> 10114.601562 #> 10: 1.49ms,1.23ms,1.16ms,1.14ms,1.16ms <tbl_df[5x3]> 2666.906250 #> 11: 1.53ms,1.27ms,1.21ms,1.17ms,1.2ms <tbl_df[5x3]> 70.007812 #> 12: 1.39ms,1.22ms,1.18ms,1.17ms,1.16ms <tbl_df[5x3]> 70.187500 #> 13: 1.39ms,1.21ms,1.21ms,1.2ms,1.18ms <tbl_df[5x3]> 72.820312 #> 14: 1.48ms,1.23ms,1.21ms,1.17ms,1.18ms <tbl_df[5x3]> 88.726562 #> 15: 1.5ms,1.36ms,1.38ms,5.15ms,1.4ms <tbl_df[5x3]> 121.273438 #> 16: 1.53ms,1.36ms,1.32ms,1.41ms,1.29ms <tbl_df[5x3]> 166.773438 #> 17: 1.68ms,1.48ms,1.47ms,1.34ms,1.33ms <tbl_df[5x3]> 257.773438 #> 18: 1.92ms,1.65ms,1.57ms,1.55ms,1.53ms <tbl_df[5x3]> 439.773438 #> 19: 3.29ms,3.21ms,2.23ms,1.98ms,1.98ms <tbl_df[5x3]> 803.773438 #> 20: 4.25ms,4.2ms,4.29ms,4.12ms,4.21ms <tbl_df[5x3]> 1531.773438 #> 21: 12.12ms, 7.41ms, 7ms, 7.49ms, 7.07ms <tbl_df[5x3]> 2987.773438 #> 22: 16.6ms,11.3ms,11.7ms,15.6ms,11.5ms <tbl_df[5x3]> 5899.773438 #> 23: 85.9µs,61.7µs,55.4µs,50.7µs,49.6µs <tbl_df[5x3]> 32.531250 #> 24: 86µs,64.9µs,56.8µs,54.3µs,51.5µs <tbl_df[5x3]> 0.000000 #> 25: 84.6µs,67µs,60.6µs,59.9µs,57.1µs <tbl_df[5x3]> 0.000000 #> 26: 92.2µs,75.3µs,69.6µs,63.5µs,64.1µs <tbl_df[5x3]> 0.593750 #> 27: 106.8µs,109.2µs, 86µs, 85.4µs, 81.7µs <tbl_df[5x3]> 2.265625 #> 28: 153.8µs,119µs,103µs, 98.3µs,104.4µs <tbl_df[5x3]> 5.156250 #> 29: 206µs,159µs,146µs,144µs,141µs <tbl_df[5x3]> 9.906250 #> 30: 282µs,264µs,246µs,335µs,245µs <tbl_df[5x3]> 19.406250 #> 31: 497µs,467µs,453µs,457µs,453µs <tbl_df[5x3]> 38.406250 #> 32: 932µs,891µs,878µs,869µs,874µs <tbl_df[5x3]> 76.406250 #> 33: 1.89ms,5.34ms,1.92ms,1.76ms,1.76ms <tbl_df[5x3]> 152.406250 #> 34: 3.95ms,3.69ms,3.59ms,3.58ms,3.56ms <tbl_df[5x3]> 304.406250 #> 35: 7.96ms,7.72ms,7.68ms,7.61ms,7.58ms <tbl_df[5x3]> 608.406250 #> 36: 16.6ms,15.6ms,15.8ms,15.9ms,15.8ms <tbl_df[5x3]> 1216.406250 #> 37: 1.09ms,928.4µs,895.2µs,891.6µs,928.9µs <tbl_df[5x3]> 179.218750 #> 38: 1.14ms,964.4µs,972.8µs,974.4µs,913.8µs <tbl_df[5x3]> 82.984375 #> 39: 1.23ms,976.3µs, 1.01ms,966.1µs,976.4µs <tbl_df[5x3]> 83.734375 #> 40: 1.12ms,976.3µs,942.8µs,941.3µs, 1.01ms <tbl_df[5x3]> 92.671875 #> 41: 1.11ms, 1.02ms,928µs, 1.06ms, 1.18ms <tbl_df[5x3]> 105.593750 #> 42: 1.31ms,1.09ms,1.34ms,2.03ms,1.39ms <tbl_df[5x3]> 128.937500 #> 43: 1.33ms,1.14ms,1.07ms,4.83ms,1.13ms <tbl_df[5x3]> 174.937500 #> 44: 1.31ms,1.14ms,1.06ms,1.03ms,1.05ms <tbl_df[5x3]> 266.937500 #> 45: 1.53ms,1.46ms,1.74ms,1.53ms,1.33ms <tbl_df[5x3]> 450.937500 #> 46: 2.04ms,1.93ms,2.32ms,2.09ms,1.88ms <tbl_df[5x3]> 818.937500 #> 47: 3.91ms,2.75ms,3.39ms,3.36ms,3.5ms <tbl_df[5x3]> 1554.937500 #> 48: 5.69ms,5.06ms,9.83ms,5.34ms,5.19ms <tbl_df[5x3]> 3026.937500 #> 49: 80.25ms, 8.21ms, 8.72ms, 8.5ms, 8.69ms <tbl_df[5x3]> 5970.937500 #> 50: 15.4ms,18.6ms,14.2ms,16ms,13.3ms <tbl_df[5x3]> 11866.203125 #> 51: 1.28ms,1.18ms,1.13ms,1.13ms,1.13ms <tbl_df[5x3]> 70.007812 #> 52: 1.37ms,1.22ms,1.21ms,1.28ms,1.21ms <tbl_df[5x3]> 70.007812 #> 53: 1.44ms,1.27ms,1.16ms,1.13ms,1.12ms <tbl_df[5x3]> 70.187500 #> 54: 1.27ms,1.18ms,1.14ms,1.17ms,1.19ms <tbl_df[5x3]> 72.820312 #> 55: 1.46ms,1.21ms,1.18ms,1.19ms,1.34ms <tbl_df[5x3]> 88.726562 #> 56: 2.51ms,1.48ms,1.4ms,1.3ms,1.3ms <tbl_df[5x3]> 121.273438 #> 57: 1.43ms,1.28ms,1.25ms,1.23ms,1.26ms <tbl_df[5x3]> 166.773438 #> 58: 1.74ms,1.64ms,1.43ms,1.74ms,1.56ms <tbl_df[5x3]> 257.773438 #> 59: 2.2ms,2.09ms,2.06ms,2.29ms,2.12ms <tbl_df[5x3]> 439.773438 #> 60: 3.85ms,3.66ms,3.78ms,4.79ms,5.03ms <tbl_df[5x3]> 822.179688 #> 61: 13.5ms,12.3ms,12.3ms,12.3ms,12.2ms <tbl_df[5x3]> 1531.773438 #> time gc kilobytes #> q25 q75 max mean sd fun.name fun.latex #> <num> <num> <num> <num> <num> <char> <char> #> 1: 0.0003536 0.0004420 0.1239093 0.02508212 5.524609e-02 N^2 log N N^2 \\log N #> 2: 0.0004231 0.0004533 0.0005590 0.00045582 5.928243e-05 N^2 log N N^2 \\log N #> 3: 0.0004629 0.0004961 0.0006708 0.00051138 9.042061e-05 N^2 log N N^2 \\log N #> 4: 0.0005289 0.0005526 0.0007432 0.00057224 9.695629e-05 N^2 log N N^2 \\log N #> 5: 0.0006580 0.0006878 0.0008145 0.00069796 6.706313e-05 N^2 log N N^2 \\log N #> 6: 0.0012273 0.0018793 0.0020198 0.00157412 3.674246e-04 N^2 log N N^2 \\log N #> 7: 0.0028256 0.0028869 0.0029425 0.00285008 7.164905e-05 N^2 log N N^2 \\log N #> 8: 0.0095828 0.0096889 0.0097030 0.00961088 8.678662e-05 N^2 log N N^2 \\log N #> 9: 0.0426154 0.0434328 0.0477435 0.04380014 2.233464e-03 N^2 log N N^2 \\log N #> 10: 0.0011551 0.0012318 0.0014931 0.00123600 1.479747e-04 sqrt N \\sqrt N #> 11: 0.0011968 0.0012704 0.0015320 0.00127606 1.477939e-04 sqrt N \\sqrt N #> 12: 0.0011695 0.0012193 0.0013868 0.00122252 9.474393e-05 sqrt N \\sqrt N #> 13: 0.0011971 0.0012086 0.0013937 0.00123854 8.725103e-05 sqrt N \\sqrt N #> 14: 0.0011821 0.0012327 0.0014831 0.00125492 1.299874e-04 sqrt N \\sqrt N #> 15: 0.0013798 0.0014956 0.0051532 0.00215750 1.675475e-03 sqrt N \\sqrt N #> 16: 0.0013158 0.0014083 0.0015278 0.00138050 9.364283e-05 sqrt N \\sqrt N #> 17: 0.0013429 0.0014776 0.0016831 0.00146096 1.413149e-04 sqrt N \\sqrt N #> 18: 0.0015540 0.0016483 0.0019208 0.00164498 1.605944e-04 sqrt N \\sqrt N #> 19: 0.0019816 0.0032135 0.0032922 0.00253898 6.602093e-04 sqrt N \\sqrt N #> 20: 0.0041967 0.0042451 0.0042929 0.00421148 6.573075e-05 sqrt N \\sqrt N #> 21: 0.0070670 0.0074937 0.0121146 0.00821640 2.189540e-03 sqrt N \\sqrt N #> 22: 0.0115405 0.0155953 0.0166483 0.01335826 2.554953e-03 sqrt N \\sqrt N #> 23: 0.0000507 0.0000617 0.0000859 0.00006066 1.489406e-05 N N #> 24: 0.0000543 0.0000649 0.0000860 0.00006270 1.395116e-05 N N #> 25: 0.0000599 0.0000670 0.0000846 0.00006584 1.109518e-05 N N #> 26: 0.0000641 0.0000753 0.0000922 0.00007294 1.177850e-05 N N #> 27: 0.0000854 0.0001068 0.0001092 0.00009382 1.307639e-05 N N #> 28: 0.0001030 0.0001190 0.0001538 0.00011570 2.266186e-05 N N #> 29: 0.0001439 0.0001593 0.0002063 0.00015936 2.714771e-05 N N #> 30: 0.0002458 0.0002818 0.0003347 0.00027418 3.707117e-05 N N #> 31: 0.0004530 0.0004671 0.0004968 0.00046536 1.852061e-05 N N #> 32: 0.0008735 0.0008906 0.0009318 0.00088868 2.538261e-05 N N #> 33: 0.0017624 0.0019167 0.0053400 0.00253356 1.570560e-03 N N #> 34: 0.0035810 0.0036918 0.0039525 0.00367518 1.630590e-04 N N #> 35: 0.0076087 0.0077244 0.0079609 0.00771220 1.499676e-04 N N #> 36: 0.0157764 0.0159197 0.0165799 0.01593500 3.816123e-04 N N #> 37: 0.0008952 0.0009289 0.0010907 0.00094696 8.227340e-05 N N #> 38: 0.0009644 0.0009744 0.0011408 0.00099324 8.615270e-05 N N #> 39: 0.0009763 0.0010098 0.0012253 0.00103078 1.099852e-04 N N #> 40: 0.0009428 0.0010139 0.0011225 0.00099936 7.496104e-05 N N #> 41: 0.0010160 0.0011077 0.0011805 0.00105922 9.508905e-05 N N #> 42: 0.0013141 0.0013889 0.0020261 0.00143258 3.506250e-04 N N #> 43: 0.0011324 0.0013346 0.0048290 0.00190212 1.639106e-03 N N #> 44: 0.0010545 0.0011355 0.0013099 0.00111978 1.128836e-04 N N #> 45: 0.0014573 0.0015354 0.0017397 0.00151878 1.486441e-04 N N #> 46: 0.0019301 0.0020895 0.0023206 0.00205098 1.726297e-04 N N #> 47: 0.0033617 0.0035053 0.0039112 0.00338336 4.157260e-04 N N #> 48: 0.0051926 0.0056916 0.0098315 0.00622332 2.030784e-03 N N #> 49: 0.0085012 0.0087226 0.0802495 0.02287472 3.207412e-02 N N #> 50: 0.0141601 0.0160117 0.0186232 0.01549966 2.029709e-03 N N #> 51: 0.0011282 0.0011779 0.0012845 0.00116904 6.812924e-05 N^2 N^2 #> 52: 0.0012059 0.0012776 0.0013699 0.00125642 7.000819e-05 N^2 N^2 #> 53: 0.0011272 0.0012656 0.0014367 0.00122274 1.325965e-04 N^2 N^2 #> 54: 0.0011664 0.0011932 0.0012731 0.00119194 4.924173e-05 N^2 N^2 #> 55: 0.0011857 0.0013440 0.0014568 0.00127556 1.210931e-04 N^2 N^2 #> 56: 0.0013049 0.0014762 0.0025062 0.00159860 5.126010e-04 N^2 N^2 #> 57: 0.0012449 0.0012803 0.0014323 0.00128900 8.261677e-05 N^2 N^2 #> 58: 0.0015558 0.0017366 0.0017441 0.00162056 1.329830e-04 N^2 N^2 #> 59: 0.0020874 0.0022017 0.0022943 0.00215298 9.532050e-05 N^2 N^2 #> 60: 0.0037766 0.0047926 0.0050320 0.00422238 6.391255e-04 N^2 N^2 #> 61: 0.0122592 0.0122892 0.0135165 0.01251378 5.609897e-04 N^2 N^2 #> q25 q75 max mean sd fun.name fun.latex #> expr.class expr.latex #> <char> <char> #> 1: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 2: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 3: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 4: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 5: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 6: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 7: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 8: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 9: changepoint::cpt.mean\nN^2 log N changepoint::cpt.mean\n$O(N^2 \\log N)$#> 10: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 11: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 12: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 13: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 14: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 15: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 16: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 17: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 18: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 19: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 20: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 21: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 22: binsegRcpp::binseg_normal\nsqrt N binsegRcpp::binseg_normal\n$O(\\sqrt N)$#> 23: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 24: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 25: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 26: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 27: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 28: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 29: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 30: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 31: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 32: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 33: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 34: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 35: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 36: fpop::multiBinSeg\nN fpop::multiBinSeg\n$O(N)$#> 37: wbs::sbs\nN wbs::sbs\n$O(N)$#> 38: wbs::sbs\nN wbs::sbs\n$O(N)$#> 39: wbs::sbs\nN wbs::sbs\n$O(N)$#> 40: wbs::sbs\nN wbs::sbs\n$O(N)$#> 41: wbs::sbs\nN wbs::sbs\n$O(N)$#> 42: wbs::sbs\nN wbs::sbs\n$O(N)$#> 43: wbs::sbs\nN wbs::sbs\n$O(N)$#> 44: wbs::sbs\nN wbs::sbs\n$O(N)$#> 45: wbs::sbs\nN wbs::sbs\n$O(N)$#> 46: wbs::sbs\nN wbs::sbs\n$O(N)$#> 47: wbs::sbs\nN wbs::sbs\n$O(N)$#> 48: wbs::sbs\nN wbs::sbs\n$O(N)$#> 49: wbs::sbs\nN wbs::sbs\n$O(N)$#> 50: wbs::sbs\nN wbs::sbs\n$O(N)$#> 51: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 52: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 53: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 54: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 55: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 56: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 57: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 58: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 59: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 60: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> 61: binsegRcpp.list\nN^2 binsegRcpp.list\n$O(N^2)$#> expr.class expr.latex #> empirical #> <num> #> 1: 0.0003581 #> 2: 0.0004255 #> 3: 0.0004716 #> 4: 0.0005301 #> 5: 0.0006806 #> 6: 0.0015243 #> 7: 0.0028454 #> 8: 0.0095882 #> 9: 0.0426579 #> 10: 0.0011581 #> 11: 0.0012121 #> 12: 0.0011799 #> 13: 0.0012079 #> 14: 0.0012091 #> 15: 0.0014017 #> 16: 0.0013594 #> 17: 0.0014678 #> 18: 0.0015743 #> 19: 0.0022298 #> 20: 0.0042076 #> 21: 0.0074088 #> 22: 0.0117257 #> 23: 0.0000554 #> 24: 0.0000568 #> 25: 0.0000606 #> 26: 0.0000696 #> 27: 0.0000860 #> 28: 0.0001044 #> 29: 0.0001461 #> 30: 0.0002638 #> 31: 0.0004573 #> 32: 0.0008781 #> 33: 0.0018928 #> 34: 0.0035885 #> 35: 0.0076828 #> 36: 0.0158226 #> 37: 0.0009284 #> 38: 0.0009728 #> 39: 0.0009764 #> 40: 0.0009763 #> 41: 0.0010639 #> 42: 0.0013404 #> 43: 0.0011391 #> 44: 0.0010643 #> 45: 0.0015308 #> 46: 0.0020376 #> 47: 0.0033856 #> 48: 0.0053414 #> 49: 0.0086899 #> 50: 0.0153591 #> 51: 0.0011288 #> 52: 0.0012240 #> 53: 0.0011591 #> 54: 0.0011840 #> 55: 0.0012074 #> 56: 0.0014042 #> 57: 0.0012618 #> 58: 0.0016393 #> 59: 0.0021220 #> 60: 0.0038511 #> 61: 0.0122753 #> empirical try(if(require(ggplot2)){ gg <- ggplot()+ geom_line(aes( N, reference, group=fun.name), color=ref.color, data=time.refs)+ geom_line(aes( N, empirical), size=1, data=seconds.dt)+ scale_x_log10()+ scale_y_log10("median line, min/max band")+ facet_wrap("expr.name")+ theme_bw() if(require(directlabels)){ gg+ directlabels::geom_dl(aes( N, reference, label=fun.name), data=time.refs, color=ref.color, method="bottom.polygons") }else{ gg } })  ## Custom asymptotic references If you have one or more expected time complexity classes that you want to compare with your empirical measurements, you can use the fun.list argument: my.refs <- list( "N \\log N"=function(N)log10(N) + log10(log(N)), "N^2"=function(N)2*log10(N), "N^3"=function(N)3*log10(N)) my.best <- atime::references_best(atime.list, fun.list=my.refs)  Note that in the code above, each R function should take as input the data size N and output log base 10 of the reference function. (my.best.time.refs <- my.best$ref[unit=="seconds"])
#>        unit                 expr.name fun.latex fun.name     N empirical
#>      <char>                    <char>    <char>   <char> <num>     <num>
#>  1: seconds     changepoint::cpt.mean N \\log N  N log N     8 0.0004255
#>  2: seconds     changepoint::cpt.mean N \\log N  N log N    16 0.0004716
#>  3: seconds     changepoint::cpt.mean N \\log N  N log N    32 0.0005301
#>  4: seconds     changepoint::cpt.mean N \\log N  N log N    64 0.0006806
#>  5: seconds     changepoint::cpt.mean N \\log N  N log N   128 0.0015243
#>  6: seconds     changepoint::cpt.mean N \\log N  N log N   256 0.0028454
#>  7: seconds     changepoint::cpt.mean N \\log N  N log N   512 0.0095882
#>  8: seconds     changepoint::cpt.mean N \\log N  N log N  1024 0.0426579
#>  9: seconds     changepoint::cpt.mean       N^2      N^2    64 0.0006806
#> 10: seconds     changepoint::cpt.mean       N^2      N^2   128 0.0015243
#> 11: seconds     changepoint::cpt.mean       N^2      N^2   256 0.0028454
#> 12: seconds     changepoint::cpt.mean       N^2      N^2   512 0.0095882
#> 13: seconds     changepoint::cpt.mean       N^2      N^2  1024 0.0426579
#> 14: seconds     changepoint::cpt.mean       N^3      N^3   128 0.0015243
#> 15: seconds     changepoint::cpt.mean       N^3      N^3   256 0.0028454
#> 16: seconds     changepoint::cpt.mean       N^3      N^3   512 0.0095882
#> 17: seconds     changepoint::cpt.mean       N^3      N^3  1024 0.0426579
#> 18: seconds binsegRcpp::binseg_normal N \\log N  N log N   256 0.0013594
#> 19: seconds binsegRcpp::binseg_normal N \\log N  N log N   512 0.0014678
#> 20: seconds binsegRcpp::binseg_normal N \\log N  N log N  1024 0.0015743
#> 21: seconds binsegRcpp::binseg_normal N \\log N  N log N  2048 0.0022298
#> 22: seconds binsegRcpp::binseg_normal N \\log N  N log N  4096 0.0042076
#> 23: seconds binsegRcpp::binseg_normal N \\log N  N log N  8192 0.0074088
#> 24: seconds binsegRcpp::binseg_normal N \\log N  N log N 16384 0.0117257
#> 25: seconds binsegRcpp::binseg_normal       N^2      N^2  2048 0.0022298
#> 26: seconds binsegRcpp::binseg_normal       N^2      N^2  4096 0.0042076
#> 27: seconds binsegRcpp::binseg_normal       N^2      N^2  8192 0.0074088
#> 28: seconds binsegRcpp::binseg_normal       N^2      N^2 16384 0.0117257
#> 29: seconds binsegRcpp::binseg_normal       N^3      N^3  4096 0.0042076
#> 30: seconds binsegRcpp::binseg_normal       N^3      N^3  8192 0.0074088
#> 31: seconds binsegRcpp::binseg_normal       N^3      N^3 16384 0.0117257
#> 32: seconds         fpop::multiBinSeg N \\log N  N log N   256 0.0001461
#> 33: seconds         fpop::multiBinSeg N \\log N  N log N   512 0.0002638
#> 34: seconds         fpop::multiBinSeg N \\log N  N log N  1024 0.0004573
#> 35: seconds         fpop::multiBinSeg N \\log N  N log N  2048 0.0008781
#> 36: seconds         fpop::multiBinSeg N \\log N  N log N  4096 0.0018928
#> 37: seconds         fpop::multiBinSeg N \\log N  N log N  8192 0.0035885
#> 38: seconds         fpop::multiBinSeg N \\log N  N log N 16384 0.0076828
#> 39: seconds         fpop::multiBinSeg N \\log N  N log N 32768 0.0158226
#> 40: seconds         fpop::multiBinSeg       N^2      N^2  2048 0.0008781
#> 41: seconds         fpop::multiBinSeg       N^2      N^2  4096 0.0018928
#> 42: seconds         fpop::multiBinSeg       N^2      N^2  8192 0.0035885
#> 43: seconds         fpop::multiBinSeg       N^2      N^2 16384 0.0076828
#> 44: seconds         fpop::multiBinSeg       N^2      N^2 32768 0.0158226
#> 45: seconds         fpop::multiBinSeg       N^3      N^3  8192 0.0035885
#> 46: seconds         fpop::multiBinSeg       N^3      N^3 16384 0.0076828
#> 47: seconds         fpop::multiBinSeg       N^3      N^3 32768 0.0158226
#> 48: seconds                  wbs::sbs N \\log N  N log N   256 0.0011391
#> 49: seconds                  wbs::sbs N \\log N  N log N   512 0.0010643
#> 50: seconds                  wbs::sbs N \\log N  N log N  1024 0.0015308
#> 51: seconds                  wbs::sbs N \\log N  N log N  2048 0.0020376
#> 52: seconds                  wbs::sbs N \\log N  N log N  4096 0.0033856
#> 53: seconds                  wbs::sbs N \\log N  N log N  8192 0.0053414
#> 54: seconds                  wbs::sbs N \\log N  N log N 16384 0.0086899
#> 55: seconds                  wbs::sbs N \\log N  N log N 32768 0.0153591
#> 56: seconds                  wbs::sbs       N^2      N^2  2048 0.0020376
#> 57: seconds                  wbs::sbs       N^2      N^2  4096 0.0033856
#> 58: seconds                  wbs::sbs       N^2      N^2  8192 0.0053414
#> 59: seconds                  wbs::sbs       N^2      N^2 16384 0.0086899
#> 60: seconds                  wbs::sbs       N^2      N^2 32768 0.0153591
#> 61: seconds                  wbs::sbs       N^3      N^3  8192 0.0053414
#> 62: seconds                  wbs::sbs       N^3      N^3 16384 0.0086899
#> 63: seconds                  wbs::sbs       N^3      N^3 32768 0.0153591
#> 64: seconds           binsegRcpp.list N \\log N  N log N    64 0.0012074
#> 65: seconds           binsegRcpp.list N \\log N  N log N   128 0.0014042
#> 66: seconds           binsegRcpp.list N \\log N  N log N   256 0.0012618
#> 67: seconds           binsegRcpp.list N \\log N  N log N   512 0.0016393
#> 68: seconds           binsegRcpp.list N \\log N  N log N  1024 0.0021220
#> 69: seconds           binsegRcpp.list N \\log N  N log N  2048 0.0038511
#> 70: seconds           binsegRcpp.list N \\log N  N log N  4096 0.0122753
#> 71: seconds           binsegRcpp.list       N^2      N^2   512 0.0016393
#> 72: seconds           binsegRcpp.list       N^2      N^2  1024 0.0021220
#> 73: seconds           binsegRcpp.list       N^2      N^2  2048 0.0038511
#> 74: seconds           binsegRcpp.list       N^2      N^2  4096 0.0122753
#> 75: seconds           binsegRcpp.list       N^3      N^3  1024 0.0021220
#> 76: seconds           binsegRcpp.list       N^3      N^3  2048 0.0038511
#> 77: seconds           binsegRcpp.list       N^3      N^3  4096 0.0122753
#>        unit                 expr.name fun.latex fun.name     N empirical
#>        reference  rank   i.N i.empirical i.reference i.rank        dist  sign
#>            <num> <num> <num>       <num>       <num>  <num>       <num> <num>
#>  1: 9.997945e-05     8   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  2: 2.666119e-04     7   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  3: 6.665297e-04     6   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  4: 1.599671e-03     5   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  5: 3.732566e-03     4   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  6: 8.531580e-03     3   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  7: 1.919606e-02     2   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  8: 4.265790e-02     1   512   0.0095882 0.019196055      2 -0.30147490    -1
#>  9: 1.666324e-04     5   512   0.0095882 0.010664475      2 -0.04620240    -1
#> 10: 6.665297e-04     4   512   0.0095882 0.010664475      2 -0.04620240    -1
#> 11: 2.666119e-03     3   512   0.0095882 0.010664475      2 -0.04620240    -1
#> 12: 1.066448e-02     2   512   0.0095882 0.010664475      2 -0.04620240    -1
#> 13: 4.265790e-02     1   512   0.0095882 0.010664475      2 -0.04620240    -1
#> 14: 8.331621e-05     4   512   0.0095882 0.005332238      2  0.25482760     1
#> 15: 6.665297e-04     3   512   0.0095882 0.005332238      2  0.25482760     1
#> 16: 5.332238e-03     2   512   0.0095882 0.005332238      2  0.25482760     1
#> 17: 4.265790e-02     1   512   0.0095882 0.005332238      2  0.25482760     1
#> 18: 1.046938e-04     7  8192   0.0074088 0.005444075      2  0.13382377     1
#> 19: 2.355609e-04     6  8192   0.0074088 0.005444075      2  0.13382377     1
#> 20: 5.234688e-04     5  8192   0.0074088 0.005444075      2  0.13382377     1
#> 21: 1.151631e-03     4  8192   0.0074088 0.005444075      2  0.13382377     1
#> 22: 2.512650e-03     3  8192   0.0074088 0.005444075      2  0.13382377     1
#> 23: 5.444075e-03     2  8192   0.0074088 0.005444075      2  0.13382377     1
#> 24: 1.172570e-02     1  8192   0.0074088 0.005444075      2  0.13382377     1
#> 25: 1.832141e-04     4  8192   0.0074088 0.002931425      2  0.40266908     1
#> 26: 7.328563e-04     3  8192   0.0074088 0.002931425      2  0.40266908     1
#> 27: 2.931425e-03     2  8192   0.0074088 0.002931425      2  0.40266908     1
#> 28: 1.172570e-02     1  8192   0.0074088 0.002931425      2  0.40266908     1
#> 29: 1.832141e-04     3  8192   0.0074088 0.001465713      2  0.70369908     1
#> 30: 1.465713e-03     2  8192   0.0074088 0.001465713      2  0.70369908     1
#> 31: 1.172570e-02     1  8192   0.0074088 0.001465713      2  0.70369908     1
#> 32: 6.592750e-05     8 16384   0.0076828 0.007383880      2  0.01723490     1
#> 33: 1.483369e-04     7 16384   0.0076828 0.007383880      2  0.01723490     1
#> 34: 3.296375e-04     6 16384   0.0076828 0.007383880      2  0.01723490     1
#> 35: 7.252025e-04     5 16384   0.0076828 0.007383880      2  0.01723490     1
#> 36: 1.582260e-03     4 16384   0.0076828 0.007383880      2  0.01723490     1
#> 37: 3.428230e-03     3 16384   0.0076828 0.007383880      2  0.01723490     1
#> 38: 7.383880e-03     2 16384   0.0076828 0.007383880      2  0.01723490     1
#> 39: 1.582260e-02     1 16384   0.0076828 0.007383880      2  0.01723490     1
#> 40: 6.180703e-05     5 16384   0.0076828 0.003955650      2  0.28830167     1
#> 41: 2.472281e-04     4 16384   0.0076828 0.003955650      2  0.28830167     1
#> 42: 9.889125e-04     3 16384   0.0076828 0.003955650      2  0.28830167     1
#> 43: 3.955650e-03     2 16384   0.0076828 0.003955650      2  0.28830167     1
#> 44: 1.582260e-02     1 16384   0.0076828 0.003955650      2  0.28830167     1
#> 45: 2.472281e-04     3 16384   0.0076828 0.001977825      2  0.58933167     1
#> 46: 1.977825e-03     2 16384   0.0076828 0.001977825      2  0.58933167     1
#> 47: 1.582260e-02     1 16384   0.0076828 0.001977825      2  0.58933167     1
#> 48: 6.399625e-05     8 16384   0.0086899 0.007167580      2  0.08364223     1
#> 49: 1.439916e-04     7 16384   0.0086899 0.007167580      2  0.08364223     1
#> 50: 3.199813e-04     6 16384   0.0086899 0.007167580      2  0.08364223     1
#> 51: 7.039588e-04     5 16384   0.0086899 0.007167580      2  0.08364223     1
#> 52: 1.535910e-03     4 16384   0.0086899 0.007167580      2  0.08364223     1
#> 53: 3.327805e-03     3 16384   0.0086899 0.007167580      2  0.08364223     1
#> 54: 7.167580e-03     2 16384   0.0086899 0.007167580      2  0.08364223     1
#> 55: 1.535910e-02     1 16384   0.0086899 0.007167580      2  0.08364223     1
#> 56: 5.999648e-05     5 16384   0.0086899 0.003839775      2  0.35470900     1
#> 57: 2.399859e-04     4 16384   0.0086899 0.003839775      2  0.35470900     1
#> 58: 9.599438e-04     3 16384   0.0086899 0.003839775      2  0.35470900     1
#> 59: 3.839775e-03     2 16384   0.0086899 0.003839775      2  0.35470900     1
#> 60: 1.535910e-02     1 16384   0.0086899 0.003839775      2  0.35470900     1
#> 61: 2.399859e-04     3 16384   0.0086899 0.001919888      2  0.65573900     1
#> 62: 1.919888e-03     2 16384   0.0086899 0.001919888      2  0.65573900     1
#> 63: 1.535910e-02     1 16384   0.0086899 0.001919888      2  0.65573900     1
#> 64: 9.590078e-05     7  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 65: 2.237685e-04     6  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 66: 5.114708e-04     5  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 67: 1.150809e-03     4  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 68: 2.557354e-03     3  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 69: 5.626179e-03     2  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 70: 1.227530e-02     1  2048   0.0038511 0.005626179      2 -0.16462876    -1
#> 71: 1.918016e-04     4  2048   0.0038511 0.003068825      2  0.09861267     1
#> 72: 7.672063e-04     3  2048   0.0038511 0.003068825      2  0.09861267     1
#> 73: 3.068825e-03     2  2048   0.0038511 0.003068825      2  0.09861267     1
#> 74: 1.227530e-02     1  2048   0.0038511 0.003068825      2  0.09861267     1
#> 75: 1.918016e-04     3  2048   0.0038511 0.001534413      2  0.39964267     1
#> 76: 1.534413e-03     2  2048   0.0038511 0.001534413      2  0.39964267     1
#> 77: 1.227530e-02     1  2048   0.0038511 0.001534413      2  0.39964267     1
#>        reference  rank   i.N i.empirical i.reference i.rank        dist  sign
#>     overall.rank each.sign.rank
#>            <num>          <num>
#>  1:            3              2
#>  2:            3              2
#>  3:            3              2
#>  4:            3              2
#>  5:            3              2
#>  6:            3              2
#>  7:            3              2
#>  8:            3              2
#>  9:            1              1
#> 10:            1              1
#> 11:            1              1
#> 12:            1              1
#> 13:            1              1
#> 14:            2              1
#> 15:            2              1
#> 16:            2              1
#> 17:            2              1
#> 18:            1              1
#> 19:            1              1
#> 20:            1              1
#> 21:            1              1
#> 22:            1              1
#> 23:            1              1
#> 24:            1              1
#> 25:            2              2
#> 26:            2              2
#> 27:            2              2
#> 28:            2              2
#> 29:            3              3
#> 30:            3              3
#> 31:            3              3
#> 32:            1              1
#> 33:            1              1
#> 34:            1              1
#> 35:            1              1
#> 36:            1              1
#> 37:            1              1
#> 38:            1              1
#> 39:            1              1
#> 40:            2              2
#> 41:            2              2
#> 42:            2              2
#> 43:            2              2
#> 44:            2              2
#> 45:            3              3
#> 46:            3              3
#> 47:            3              3
#> 48:            1              1
#> 49:            1              1
#> 50:            1              1
#> 51:            1              1
#> 52:            1              1
#> 53:            1              1
#> 54:            1              1
#> 55:            1              1
#> 56:            2              2
#> 57:            2              2
#> 58:            2              2
#> 59:            2              2
#> 60:            2              2
#> 61:            3              3
#> 62:            3              3
#> 63:            3              3
#> 64:            2              1
#> 65:            2              1
#> 66:            2              1
#> 67:            2              1
#> 68:            2              1
#> 69:            2              1
#> 70:            2              1
#> 71:            1              1
#> 72:            1              1
#> 73:            1              1
#> 74:            1              1
#> 75:            3              2
#> 76:            3              2
#> 77:            3              2
#>     overall.rank each.sign.rank
try(if(require(ggplot2)){
gg <- ggplot()+
geom_line(aes(
N, reference, group=fun.name),
color=ref.color,
data=my.best.time.refs)+
geom_line(aes(
N, empirical),
size=1,
data=seconds.dt)+
scale_x_log10()+
scale_y_log10("median line, min/max band")+
facet_wrap("expr.name")+
theme_bw()
if(require(directlabels)){
gg+
directlabels::geom_dl(aes(
N, reference, label=fun.name),
data=my.best.time.refs,
color=ref.color,
method="bottom.polygons")
}else{
gg
}
})


From the plot above you should be able to see the asymptotic time complexity class of each algorithm.

• the fastest packages are log-linear (fpop, wbs, binsegRcpp),
• that the binsegRcpp implementation that uses the list container is much slower (quadratic).
• the changepoint package uses a super-quadratic algorithm (actually cubic, which you could see if you increase N even larger).

## Exercises for the reader

• increase seconds.limit to see the differences more clearly.
• compute and plot asymptotic references for memory instead of time (including expected memory complexity, linear).