--- title: "Algorithmic Complexity" author: "JJB + Course" date: "07/24/2018" output: html_document --- # Empirical Run Time ## Example: Elementary Benchmark ```{r} out = system.time({Sys.sleep(1)}) out out[3] ``` What does this say about elapsed vs. relative + system? ## Example: Benchmarking Data Structures ```{r, cache = TRUE} # Set seed for reproducibility set.seed(1337) # Construct large matrix object matrix.op = matrix(rnorm(10000*100), 10000, 100) # Convert matrix object to data.frame dataframe.op = as.data.frame(matrix.op) library("rbenchmark") bench_ops = benchmark(mat.op = apply(matrix.op, 2, sd), df.op = apply(dataframe.op, 2, sd)) bench_ops ``` ## Example: Benchmarking } vs. ( ```{r, cache = TRUE} # install.packages("Rcpp") # Different R implementations f = function(n, x = 1) for (i in 1:n) x = 1/(1+x) g = function(n, x = 1) for (i in 1:n) x = (1/(1+x)) h = function(n, x = 1) for (i in 1:n) x = (1+x)^(-1) j = function(n, x = 1) for (i in 1:n) x = {1/{1+x} } k = function(n, x = 1) for (i in 1:n) x = 1/{1+x} Rcpp::cppFunction(code = 'int d(int n, double x = 1.0) { for (int i = 0; i < n; ++i) x = 1/(1+x); return x; }') library("rbenchmark") N = 1e6 # Number of Times to Run Loop bench_curly = # Test Approaches benchmark(f(N, 1), g(N, 1), h(N, 1), j(N, 1), k(N, 1), d(N, 1), order = "relative", # Fastest first (lower is better) replications = 20) # Run each function x times bench_curly ``` ## Example: Benchmark of the Preallocation of space ```{r, cache = TRUE} append_elements = function(n) { vec = numeric(0) # Vector of length 0 for(i in seq_len(n)) vec = c(vec, i) # Append results vec } preallocate_elements = function(n) { vec = rep(NA, n) # Vector of length n for(i in seq_len(n)) vec[i] = i # Access and update vec } vectorized_element = function(n) { seq_len(n) } n = 10000 bench_growth = benchmark(append = append_elements(n), preallocate = preallocate_elements(n), vectorized = vectorized_element(n)) bench_growth ``` ## Example: Microbenchmarking Code ```{r growth_micro, cache = TRUE} # install.packages("microbenchmark") library("microbenchmark") n = 10000 microbench_growth = microbenchmark( append = append_elements(n), preallocate = preallocate_elements(n), vectorized = vectorized_element(n) ) microbench_growth ``` ```{r cache = TRUE, dependson="growth_micro"} library("ggplot2") autoplot(microbench_growth) ``` # Theoretical Run Time ## Example: Big Oh Runtimes ```{r, echo = FALSE, message = FALSE} # install.packages(c("ggplot2", "reshape2")) library("ggplot2");library("reshape2") N = 1:50 # Calculate some different N sample sizes obs = length(N) # Determine length # Create a wide data set d = data.frame(Constant = rep(1,obs), SquareRoot = sqrt(N), Logarithmic = log(N), Quadlogarithmic = log(N)^2, LogLinear = N*log(N), Quadratic = N^2, Exponential = 2^N, Factorial = factorial(N), Size = N) # Wide to Long d2 = melt(d, id.vars = "Size", variable.name = "Method", value.name = "RunTime") d2 = d2[is.finite(d2\$RunTime) & d2\$RunTime < 1e4,] ggplot(d2) + geom_line(aes(x = Size, y = RunTime, color = Method)) + ggtitle("Run Time vs. Sample Size") + xlab("Sample Size") + ylab("Run Time") + theme(plot.title = element_text(size=17), legend.title=element_text(size=17), axis.text = element_text(size=15), # Axis labels axis.title = element_text(size=17), # Axis names legend.text = element_text(size=15)) + ylim(0, 150) ``` ```{r} n = 1:1000 data.frame(n = n , nlogn = n*log(n)) ```