In shaiq681/KnapSacked: An R Package to implement 'greedy search', 'brute-force search' and 'dynamic programming' on knapsack proble-set

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

library(KnapSacked)

Introduction

1.1.2 Brute force search

# Function to get time
get_time <- function(i){
  time <- system.time(expr = brute_force_knapsack(x = knapsack_objects[1:16,], W=i))[3]
  return(time)}

# Function to get mean execution time
mean(unlist(lapply(c(10,100,1000,10000, 100000), FUN = get_time)))

• Question: How much time does it takes to run the algorithm for n = 16 objects?
• Average Code Execution Time: 2.004 seconds

1.1.3 Dynamic Programming

# Data Object
n <-1000000
knapsack_objects <-
  data.frame(
    w=sample(1:4000, size = n, replace = TRUE),
    v=runif(n = n, 0, 10000)
  )
# Function to get time
get_time <- function(i){
  time <- system.time(expr = knapsack_dynamic(x = knapsack_objects[1:500,], W=i))[3]
  return(time)}

# Function to get mean execution time
mean(unlist(lapply(c(100,500,1000,1500,2000,3000,4000,5000), FUN = get_time)))

• Question: How much time does it takes to run the algorithm for n = 500 objects?
• Average Code Execution Time: 2.65 seconds

1.1.4 Greedy Heuristics

# Data Object
n <-1000000
knapsack_objects <-
  data.frame(
    w=sample(1:4000, size = n, replace = TRUE),
    v=runif(n = n, 0, 10000)
  )
# Function to get time
get_time <- function(i){
  time <- system.time(expr = greedy_knapsack(x = knapsack_objects[1:1000000,], W=i))[3]
  return(time)}


mean(unlist(lapply(c(1000,2500,5000,10000,15000,20000), FUN = get_time)))

# Function to get mean execution time
mean(unlist(lapply(c(1000,2500,5000,10000,15000,20000), FUN = get_time)))

• Question: How much time does it takes to run the algorithm for n = 1000000 objects?
• Average Code Execution Time: 0.34 seconds

1.1.6 Profile your code and optimize your code

• Question: What performance gain could you get by trying to improving your code?
• Implemented:
  • Code Organization : Reduced no. of operations per function, saving time on multiple code block execution.
  • Vectorization : Replaced loops with Vectorization wherever possible, which reduced code execution time
  • Parallelization : Added Parallel programming for Windows machine, which boosted execution time for large no. of values in 'brute_force_knapsack' program.

1.1.7 Parallelize brute force search

• Set parameter parallel = T

brute_force_knapsack(x = knapsack_objects[1:8,], W = 3500, parallel = T)
brute_force_knapsack(x = knapsack_objects[1:8,], W = 2000, parallel = T)

1.2 Profile and improve your existing API package

Solution-1: Add Memoization to reduce API calls overhead

install.packages("memoise")

library(memoise)

f <- memoise(func)

Solution-2: Chunking

• Limited no. of trials per call to 10,000 only.

shaiq681/KnapSacked documentation built on Oct. 13, 2020, 1:27 a.m.