14

Here's a ubiquitous data structure in, say, game and UX programming:

  • there're a fixed number of items (say, "5")
  • they're all "zero" to begin with
  • you can put one in on the "left" (FWIW I usually call it something like shove to distinguish from the usual meaning of push)
  • once there are 5, each time you put a new one in on the left, the one on the "right" falls out and is gone
  • in fact, it's not possible to / there's no need to access any individual item, ever
  • you can get the total at any time

Here's a trivial naturalistic example. (Obviously, there're several ways to do it.)

I've always wondered if there's a common term for this.

I sometimes call it a "piece of pipe" (imagine a short piece of pipe that you can push tennis balls through from one end).

///A "pipe" ongoing sum. First in is first thrown-away. class Pipe { private var r: [Whatever] = [] private var i: Int = 0 private var k: Int = 0 ///Start fresh, with a given fixed length. public func begin(with: Int) { k = with r = Array(repeating: .zero, count: k) i = 0 } ///Add one on the left public func shove(p: CGPoint) { r[i] = p i = (i + 1) % k } ///Supply the current value at this moment. public var sum: CGPoint { return r.reduce(.zero, +) / CGFloat(k) } ///Debugging string. public var say: String { return r.reduce("pipe: "){ a,b in "\(a) .. \(b.say)"} + " t " + sum.say } }
Improve this question
16
  • 16
    Is it possible you're talking about a circular buffer, or at least generically some kind of buffer? With the particular feature that no individual item is ever accessed, only the total, but the individual items are retained so as to know how the total alters when an item is dropped from the tail, I think that's possibly more a peculiarity of this application, than something that would have its own name. Commented Oct 27, 2022 at 11:46
  • 1
    Also Fattie, just trying to reconcile what @Laiv has said, are you sure the algorithm you describe is LIFO? If items fall off the right as new items are added on the left, that's FIFO surely? Commented Oct 27, 2022 at 11:50
  • 1
    Related: stackoverflow.com/questions/5852863/… Commented Oct 27, 2022 at 18:53
  • 1
    This is a circular buffer. But if you implement it using an array it is a very inefficiently implemented circular buffer. Except if you are using arrays in a language like javascript or lists in a language like lisp or tcl - then it's not inefficient because arrays/lists in those languages are basically linked lists. Commented Oct 29, 2022 at 0:10
  • 1
    @slebetman: JavaScript arrays have no defined representation, and I wouldn't count on them having linked list-like performance for FIFO queues. Some implementations might dynamically convert from sparse or dense array representations to a linked-list-like implementation based on usage (the modern JIT optimizers get crazy), but it's not something inherent in the language spec (unlike Lisp for example). Commented Oct 29, 2022 at 15:30

2 Answers 2

Reset to default
35

This sounds a lot like a circular buffer or ring buffer. It meets most of the criteria:

  • It has a fixed size of items.
  • They don't have to be a specific value at the start, but they could be initialized to a reasonable default, empty, or null value depending on your implementation.
  • You insert values at the end and read from the marker.
  • If you are writing faster than you are reading, items will fall out of the buffer before they can be read.

You could have some specialized implementations of a ring buffer that address other concerns. I suspect that it would be close enough to a ring buffer that the name would still apply and be meaningful.

Improve this answer
14
  • 2
    Thanks. Hmm, you know, I usually think of a circular buffer as a particular type of queue. (In my mind: a queue is platonic, and can be as long as you want and has no performance problems "shifting everything" all the time. Then, in my mind, a circular buffer is a good way to implement a queue in many situations, but it suffers from the problem you might run out of room.) Thanks to your comment it occurred to me after years that what I'm describing is indeed "a somewhat unusual queue" (ie it deliberately runs out of room all the time, and also there's no need to access items)... Commented Oct 27, 2022 at 12:53
  • 4
    @Fattie We've been using the term ring buffer or circular buffer for ages. A queue is a type of buffer (things line up and wait their turn). MS-DOS, for example, had a keyboard buffer to store 16 keypresses in a 32-byte wide buffer, and would beep at you if the buffer was full on keypress/release (e.g. a program was caught in an infinite loop and so couldn't read keys). We've had fixed buffers even earlier than that, but that was my earliest recollection of the word. Ring/circular is used to distinguish between variable-sized buffers like a stack or queue. Commented Oct 27, 2022 at 19:59
  • 1
    The everyday meaning of "buffer" is not something that avoids losing data, it's something that sits between two other things to somehow decouple them - mechanically (for trains) or logically (for producers and consumers). Not wanting to lose data is a common property of consumers, but it's not intrinsic to the buffer. There's even an outgoing buffer somewhere for UDP sends, and those are permitted to be dropped on the floor at any time for any reason. Commented Oct 28, 2022 at 14:31
  • 2
    @Fattie But what you are doing with your data structure no matter what you call it IS buffering. You are slowing down your data stream so that your logic can process a bunch of it at a time. Otherwise, if you don't need to "slow it down", you don't need the array. You can just use a single variable and process the data as is (one piece/byte at a time) Commented Oct 29, 2022 at 0:26
  • 1
    I do note that the very Wikipedia article you quote mentions that there are two ways to handle the buffer full condition: either overwriting or not. Ring Buffers are typically used in xPxC concurrent queues, and there they do NOT overwrite. Similarly, the LMax Disruptor pattern uses a Ring buffer and does NOT overwrite. With overwriting not being intrinsic to Ring Buffers, I'd argue you need to specify this property on top. Commented Oct 29, 2022 at 11:24
20

Like the other answer suggests, a fixed-length fifo queue is a ring buffer, although usually writing past the capacity will be prevented, instead of overwriting the next element.

  • in fact, it's not possible to / there's no need to access any individual item, ever
  • you can get the total at any time

With this feature, it is known as a sliding window. I would be implemented as follows:

class SlidingWindow<Whatever extends Numeric> { private var r: [Whatever] = [] private var i: Int = 0 private var k: Int = 0 ///Running sum over the contents of the sliding window public var sum: Whatever = .zero ///Start fresh, with a given fixed length. public func begin(with: Int) { k = with r = Array(repeating: .zero, count: k) i = 0 sum = .zero } ///Add a new value, remove the oldest value, update the sum public func advance(p: Whatever) { sum = sum - r[i] + p r[i] = p i = (i + 1) % k } }
Improve this answer
17
  • 2
    Beware that the accumulator is subject to rounding-error for inexact numeric types (floating point). The total risks gradually drifting away from the true result. Commented Oct 28, 2022 at 10:52
  • 3
    @Fattie: Keeping track of the total sum and updating it as new values are added (and pushed off) seems like a pretty natural optimization if the sums are needed frequently, and the buffer isn't so small that summing it takes negligible time. I'm surprised you haven't seen it, although I suppose it likely depends on the application domain you typically work in. Commented Oct 28, 2022 at 11:56
  • 4
    … In particular, this kind of data structure is a natural choice for applying a boxcar convolution (a.k.a. a simple moving average of the past k data points) to a data stream, where you need to obtain the updated sum after each new data point (and in which case you'd typically just have the advance operation directly return the new sum). Here, having the sum update take just two arithmetic operations instead of k is a clear win whenever k ≫ 2. Commented Oct 28, 2022 at 11:56
  • 8
    @Fattie: It depends on your domain. Moving average filters of non-trivial size are common in digital signal processing kernels on the critical path of the system, such as in image processing. My day job deals in underpowered embedded devices where this type of optimization is helpful in hitting real-time deadlines and power budgets. YMMV. Commented Oct 28, 2022 at 13:57
  • 3
    @Fattie "it is a window, but, specifically not a sliding window" - why not? It's a window sliding over the input stream Commented Oct 28, 2022 at 18:40

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.