In fengye0907/LAB6C: A package for lab6

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

library(LAB6C)

1.1.2 Brute force search

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

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

# example
#    user  system elapsed 
#    0.24    0.03    0.26

1.1.3 Dynamic programming

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

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

# example
#    user  system elapsed 
#    9.28    0.05    9.34

1.1.4 Greedy heuristic

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

set.seed(42)
n <- 1000000
example <-
data.frame(
w=sample(1:4000, size = n, replace = TRUE),
v=runif(n = n, 0, 10000)
)
system.time(
  knapsack(x=example, W=3500)$greedy_knapsack()
)

# example
#    user  system elapsed 
#    0.38    0.03    0.41

1.1.6 Profile your code and optimize your code

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

x1<-lineprof(knapsack(x=knapsack_objects[1:15,], W=3500)$brute_force_knapsack())
shine(x1)

Of course, the calculate speed is quicker by modification or delete the comments from lineprof and it is also possible to give us some ideas to use less memory sometimes.

1.1.8

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

## single core
N1 <- 10
N2 <- 20
system.time(
  knapsack(x=knapsack_objects[1:N1,], W=3500)$brute_force_knapsack()
)
#    user  system elapsed 
#    0.02    0.00    0.01
system.time(
  knapsack(x=knapsack_objects[1:N2,], W=3500)$brute_force_knapsack()
)
#    user  system elapsed 
#    7.56    0.23    7.93

## multiple cores
system.time(
  knapsack(x=knapsack_objects[1:N1,], W=3500)$brute_force_knapsack(TRUE)
)
#    user  system elapsed 
#    0.13    0.07    1.95

system.time(
  knapsack(x=knapsack_objects[1:N2,], W=3500)$brute_force_knapsack(TRUE)
)
#    user  system elapsed 
#    2.35    0.64    6.28

Evidently, parallelization is more efficient when the number of elements increasing. However, we also notice that multiple cores is not better than single core when running brute_force_knapsack() with small number of elements (here especially for N<=10).

fengye0907/LAB6C documentation built on May 10, 2019, 8:25 a.m.