In herwineric/Lab6_Albin_Eric: Lab6

This package contains the three different methods for comuting the knapsack problem. The methods with functions are:

• brute_force_knapsack: Performs a brute force computation and you can have the option of parallel-compute this aswell.
• dynamic_knapsack: Performes a dynamic computation
• greedy_knapsack: Performes a dreedy method of the knapsack problem

All of these methods are producing a output of a list with the maximum value of the opimal weight and elements that produces the maximum value.

More reading about the knapsack problem can be found here

Question for 1.1.2

How long time does it take to run the brute force search on $n = 16$?

library(Lab6VarmKorv)

set.seed(42)
knapsack_objects <-
data.frame(
  w=sample(1:4000, size = 2000, replace = TRUE),
  v=runif(n = 2000, 0, 10000))
#Brute force


x <- Sys.time()
brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500,parallel = FALSE)
y <- Sys.time()
time <- y-x

#brute_force_knapsack(x = knapsack_objects[1:16,], W = 3500,parallel = FALSE)
time

We can see in the chunk how long time it takes for the brute force function.

Question for 1.1.3

How much time does it takes to run the algorithm, with the dynamic method, to calculate $n = 500$?

x <- Sys.time()
knapsack_dynamic(x = knapsack_objects[1:500,], W = 3500)
y <- Sys.time()
time <- y-x

#knapsack_dynamic(x = knapsack_objects[1:500,], W = 3500)
time

Question for 1.1.4

How much time does it takes to run the algorithm, with the greedy method, to calculate $n = 1000000$?

knapsack_objects <-
data.frame(
  w=sample(1:4000, size = 1000000, replace = TRUE),
  v=runif(n = 2000, 0, 10000))

x <- Sys.time()
lord <- lapply(seq(1001, 1000000, 1000) , function(z){
  greedy_knapsack(x = knapsack_objects[(z-1000)  :z,], W = 3500)
} )
y <- Sys.time()
time <- y-x

#knapsack_dynamic(x = knapsack_objects[1:1000000,], W = 3500)
time

Question for 1.1.6

So we will use the package lineprof to see if the code can be more efficient. To install the package, you have to use the code: devtools::install_github("hadley/lineprof").

brute force, no parallel

#lineprof(hej <- brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500,parallel = FALSE))

In this approach of the brute force method the lineprof funciton found that the lapply functions are the ones that slows it down. For this approah, there is probably very little to do to make this approach faster. Mabye to make calls to C++, Python or something equivalent.

brute force, with parallel

#lineprof(hej <- brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500,parallel = TRUE))

In this function, according to lineprof the step that takes the longest, and significant, amount of time is a cluster function makeCluster which is needed to set how many cores that are avaliable. Though i do not think you can make this any faster then to just swqitch from the OS Windows to, for example, Linux.

knapsack_dynamic

#lineprof(hej <- knapsack_dynamic(x = knapsack_objects[1:8,], W = 3500))

In this function the time that everything takes to run is very spread out, so basically just to improve the whole for and replace with, for example implementing function from the apply() family. Though with that approach will be complicated, due to the limitations of indexing with an apply.

greedy_knapsack

#lineprof(hej <- greedy_knapsack(x = knapsack_objects[1:800,], W = 3500))

In this function it is the sorting that take the most of the time. To make this faster an implementation of, for example the package dplyr could be used which is written in the language: C. For the sorting problem you could use the function arrange() in the package dplyr.

herwineric/Lab6_Albin_Eric documentation built on May 21, 2019, 3:03 a.m.