In Philhoels/AdvRLab6: The knapsack package

library(profvis)
library(parallel)

1.1.2 Brute force search

Question:

• How much time does it takes to run the algorithm for n = 16 objects?

system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500))

Answer: By using the dynamic_knapsack function, does the time for 16 objects be 3.589 seconds.

1.1.3 Dynamic Programming

Question:

• How much time does it takes to run the algorithm for n = 500 objects?

system.time(dynamic_knapsack(x = knapsack_objects[1:500,], W = 3500))

Answer: By using the dynamic_knapsack function, does the time for 500 objects be 5.644 seconds.

1.1.4 Greedy heuristic

Question:

• How much time does it takes to run the algorithm for n = 1000000 objects?

system.time(greedy_knapsack(x = knapsack_objects[1:1000000,], W = 3500))

Answer: To run the algorithm, it takes for n = 1000000 objects 1.674 seconds.

1.1.6 Profile your code and optimize your code

Question:

• What performance gain could you get by trying to improving your code?

> install.packages("lineprof")
Warning in install.packages :
  package ‘lineprof’ is not available (for R version 3.5.1)

It is not possible to install "lineprof", we used "profvis" instead.

op <- profvis::profvis(
  {
    # the greedy algorithm
    if(W < 1){
      stop("The argument W needs to be positive")
    }
    #value per weight
    vpw <- x[,2]/x[,1]
    x$vpw <- vpw
    #order
    x <- x[order(x$vpw, decreasing = TRUE),]
    weight <- W
    sum <- 0
    i <-1
    elements <- c()
    nrow <- nrow(x)
    #sum value until reach the weight
    for (i in 1:nrow)
    {
      if (x$w[i] < weight)
      {
        if (weight > 0)
        {
          weight <- weight - x$w[i]
          sum <- sum + x$v[i]
          elements <- c(elements, as.numeric(row.names(x)[i]))
        }
      } else  break()
    }

    output <- list(value = round(sum, 0), elements = elements)
    return(output)
  })

Answer: We can see most time consuming is the for loop, it takes 10ms. There are several techniques to improve the performance of the code. For loops are always very time-consuming in R, in Hadly Wickham is in the chapter some techniques listed. For example to vectorize or parallelize (which we used to speed up the Brute force search) the code. But the most matching techniques to improve the speed would be to write this part of the function in C++.

1.1.8 (*) Parallelize brute force search

Question:

• What performance gain could you get by parallelizing brute force search?

system.time(brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500, parallel = TRUE))

Answer:

## time dynamic_knapsack function 3.589
## time dynamic_knapsack parallel function 3.381
3.589 - 3.381

By using the dynamic_knapsack function parallel, does the time for 16 objects be 3.381 seconds. We checked the parallized dynamic_knapsack function parallel on n = 16 objects, like in the first question 1.1.2 of the Brute force search. We could gane a time reduce of 0.208 seconds.

Philhoels/AdvRLab6 documentation built on May 22, 2019, 2:16 p.m.