README.Rmd

---
output: github_document
---

<!-- README.md is generated from README.Rmd. Please edit that file -->

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%",
  dpi = 300,
  fig.width = 8
)
```

# binpackr

<!-- badges: start -->

[![R-CMD-check](https://github.com/lschneiderbauer/binpackr/actions/workflows/R-CMD-check.yaml/badge.svg)](https://github.com/lschneiderbauer/binpackr/actions/workflows/R-CMD-check.yaml) [![Codecov test coverage](https://codecov.io/gh/lschneiderbauer/binpackr/branch/master/graph/badge.svg)](https://app.codecov.io/gh/lschneiderbauer/binpackr?branch=master) [![Lifecycle: experimental](https://img.shields.io/badge/lifecycle-experimental-orange.svg)](https://lifecycle.r-lib.org/articles/stages.html#experimental) [![CRAN status](https://www.r-pkg.org/badges/version/binpackr)](https://CRAN.R-project.org/package=binpackr)

<!-- badges: end -->

This package implements the First Fit Decreasing algorithm to achieve one dimensional heuristic bin packing. Its run time is of order $\mathcal{O}(n\,log(n))$ where $n$ is the number of items to pack.

## Installation

You can install the latest CRAN release of binpackr with:

``` r
install.packages("binpackr")
```

Alternatively, you can install the development version of binpackr from [GitHub](https://github.com/) with:

``` r
# install.packages("devtools")
devtools::install_github("lschneiderbauer/binpackr")
```

## Example

This is a basic example which shows to retrieve the solution for the bin packing problem.

```{r example}
library(binpackr)

# Generate a vector of item sizes
set.seed(42)
x <- sample(100, 1000, replace = TRUE)

# Pack those items into bins of capacity 130
bins <- bin_pack_ffd(x, cap = 130)

# Number of bins needed to pack the items
print(length(unique(bins)))
```

## Benchmarks

The implementation in this package is compared to an implementation of the same algorithm in the [BBmisc](https://github.com/berndbischl/BBmisc) package. The authors made it clear that speed was none of their concern. BBmisc's implementation is written in R while this package uses a C++ implementation.

```{r benchmark_calc, echo=FALSE, message=FALSE, warning=FALSE}
result <- readRDS("./benchmark/results.rds")

library(ggplot2)
library(dplyr)
```

### Run time

```{r benchmark_runtime, echo = FALSE}
result |>
  mutate(
    ymin = as.numeric(mean - std),
    ymax = as.numeric(mean + std),
    median = as.numeric(median)
  ) |>
  ggplot(aes(
    x = n, y = median, color = name, fill = name,
    ymin = ymin, ymax = ymax
  )) +
  scale_x_continuous(
    name = "Number of items",
    labels = scales::label_number(
      scale_cut = scales::cut_long_scale()
    )
  ) +
  scale_y_continuous(
    name = "Runtime (in seconds)",
    labels = scales::label_number(
      suffix = "s",
      scale_cut = scales::cut_long_scale()
    )
  ) +
  geom_ribbon(alpha = 0.3, linewidth = 0) +
  geom_point() +
  geom_line() +
  theme_minimal() +
  theme(legend.position = "bottom") +
  labs(fill = "Implementation", color = "Implementation")
```

### Memory allocation

```{r benchmark_memory, echo = FALSE}
result |>
  ggplot(aes(x = n, y = mem_alloc, color = name)) +
  scale_x_continuous(
    name = "Number of items",
    labels = scales::label_number(
      scale_cut = scales::cut_long_scale()
    )
  ) +
  scale_y_continuous(
    name = "Memory allocation",
    labels = scales::label_number(
      suffix = "B",
      scale_cut = scales::cut_long_scale()
    )
  ) +
  geom_point() +
  geom_line() +
  facet_wrap(vars(name), scales = "free_y", ncol = 1) +
  theme_minimal() +
  theme(legend.position = "bottom") +
  labs(fill = "Implementation", color = "Implementation")
```