In richfitz/ring: Circular / Ring Buffers

``` {r echo=FALSE, results="hide"} knitr::opts_chunk$set( error=FALSE, fig.width=7, fig.height=5) set.seed(1)

The bytes-based ring buffer in the main vignette is a better data
structure to implement the simulation than the environment buffer
is because the expected elements in each entry of the buffer are
the same.  But with a bit of S3 syntactic sugar we can do a bit
better.  This vignette is an attempt at creating "ring" versions of
a vector and matrix data type.

NOTE: this vignette used to be implemented in the package itself,
but I pulled it out of the package because I felt that the
implementation wasn't quite right, and that it may not be ideal to
have objects that appear to have normal-R semantics operate by side
effect.  However, this may give some ideas for how to use ring
buffers in practice.

## Ring vector

The actual code for the buffer here is available in the package via
`system.file("examples/ring_vector.R", package = "ring")` (the path
depends on your R and package installations).

``` {r echo = FALSE, results = "asis"}
local({
  path <- system.file("examples/ring_vector.R", package = "ring")
  source(path, local = FALSE)
  writeLines(c("```r", readLines(path), "```"))
})

Then create an integer ring vector of length 5:

v <- ring_vector(5, "integer", FALSE)

Convert back out to be an R vector (involves a copy)

v[]

To add things to the vector, use the push generic:

push(v, 1L)
v[]

This can push multiple items on at once:

push(v, 2:4)
v[]
length(v)

Random read access works:

v[3]
v[[1]]

Resetting the buffer zeros this all:

v$buf$reset()
length(v)

Returning to the simulation example from the main vignette:

buf <- ring_vector(5, "integer", FALSE)
h <- integer(20)
x <- 0L
push(buf, x)
h[1L] <- x

step <- function(x) {
  if (runif(1) < 0.5) x - 1L else x + 1L
}

set.seed(1)
for (i in seq_len(length(h) - 1L)) {
  x <- step(x)
  push(buf, x)
  h[i + 1L] <- x
}

The whole history:

h

The last 5 steps:

buf[]

Now, rewriting again, this time with the step function taking the buffer itself. This simplifies the implementation, with most of the details being handled by the S3 methods for length, push and [.

step <- function(x) {
  if (length(x) > 1) {
    p <- mean(diff(x[])) / 2 + 0.5
  } else {
    p <- 0.5
  }
  if (runif(1) < p) x[length(x)] - 1L else x[length(x)] + 1L
}

buf <- ring_vector(5, "integer", FALSE)
h <- integer(100)
x <- 0L

push(buf, x)
h[1L] <- x

set.seed(1)
for (i in seq_len(length(h) - 1L)) {
  x <- step(buf)
  push(buf, x)
  h[i + 1L] <- x
}

par(mar=c(4, 4, .5, .5))
plot(h, type="l", xlab="step", ylab="y", las=1)

Ring matrix with ring_matrix

The ring_matrix data structure generalises the ring_vector; it is a buffer that looks to R like a matrix that grows by adding rows at the bottom and shrinks by consuming rows at the top.

{r echo = FALSE, results = "asis"} local({ path <- system.file("examples/ring_matrix.R", package = "ring") source(path, local = FALSE) dat <- readLines(path) writeLines(c("r", dat[!grepl("^###", dat)], "```")) })

This is even more contrived than above, but consider simultaneously
simulating the movement of `n` random particles with the same
reflecting random walk as above.  First create a 10 x 5 ring
matrix:

``` {r }
n <- 10
m <- ring_matrix(5, n, "integer", FALSE)

The current state of the matrix is:

m[]

We can set the initial state as:

push(m, matrix(0L, 1, n))
m[]

step <- function(m) {
  if (nrow(m) > 1) {
    p <- colMeans(diff(m[])) / 2 + 0.5
  } else {
    p <- rep(0.5, ncol(m))
  }
  m[nrow(m), ] + as.integer(ifelse(runif(length(p)) < p, -1, 1L))
}

m <- ring_matrix(5, n, "integer", FALSE)
x <- rep(0L, n)
push(m, x)

h <- matrix(NA, 200, n)
h[1, ] <- x
set.seed(1)
for (i in seq_len(nrow(h) - 1L)) {
  x <- step(m)
  push(m, x)
  h[i + 1L, ] <- x
}

par(mar=c(4, 4, .5, .5))
matplot(h, type="l", lty=1, las=1)

richfitz/ring documentation built on Nov. 29, 2023, 11:34 p.m.