O(1) JavaScript Circular Buffer With GetMax and GetMin

Question

So I've been scouring the web to find a way to do this but nothing I've found fits the exact solution we are looking for.

I have an app that stores float numbers in a circular buffer. The circular buffer class can be found here https://www.npmjs.com/package/circular-buffer.

In my app new numbers are coming in every few miliseconds and the buffer holds around 60K values.

For the purpose of this question though I created a circular buffer of 10 with a stream of 100 randomly generated numbers to simulate the incoming data. This is the line that generates the simulated stream:

for (let i = 0; i < valuesToEnqueueForDemoPurposes.length; i++) {

With my current setup, it is taking the cpu too much time to convert the circular buffer to an array and then calculate its min, max, min position / index number, max position / index number and standard deviations (but the stddev is not the focus of this question).

Here is my current code:

stats = require("stats-lite");
var CircularBuffer = require("circular-buffer");

var circularBuffer10 = new CircularBuffer(10);

var valuesToEnqueueForDemoPurposes = Array.from(Array(100)).map(x=>Math.random() * 1000)

for (let i = 0; i < valuesToEnqueueForDemoPurposes.length; i++) {
    var newValue = valuesToEnqueueForDemoPurposes[i];

    circularBuffer10.enq(newValue);

    let valuesArray = circularBuffer10.toarray();


    var maxIndex = valuesArray.reduce((iMax, x, i, arr) => x > arr[iMax] ? i : iMax, 0);
    var minIndex = valuesArray.reduce((iMin, x, i, arr) => x < arr[iMin] ? i : iMin, 0);
    var max = valuesArray[maxIndex];
    var min = valuesArray[minIndex];
    var standardDeviation = stats.stdev(valuesArray);


    console.log(maxIndex);
    console.log(max);
    console.log(minIndex);
    console.log(min);
    console.log(standardDeviation + "\n\n");
}

So I was wondering if it was possible to optimize this code with different data structures.

The closest answer I've found to solve this issue is from this SO answer: https://stackoverflow.com/a/48610455

It uses:

• a queue of N items
• a Min / Max Heap to track the min / max item.
• A hash map to track the frequency of each item.

But the problem with this solution is that the heap is always growing and with the amount of differing incoming data I receive, this would cause a serious problem. And it also only calculates the maximum.

Also found this c++ solution but it is only for a normal queue, a max (not min) and I wasn't able to reproduce in javascript: https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/

Does anyone know if it would be possible, using whatever combination of data structures, to find the Max or Min in O(1) for this type of scenario (with or without circular buffers)?

Answer 1

Thanks to @thomas's advice I was able to alter the circular buffer class I was using so that the sum, mean,max, min and standard deviations are calculated on average at O(1) but at the worst O(N). Worked like a charm for the performance I needed.

Please note that for my purposes I have only altered the "unshift" method of the CBuffer circular buffer class . So the other methods won't be updating the max, min and standard deviations correctly. Here is the link to the jsfiddle: https://jsfiddle.net/29f4an7s/

And here is my testing code:

// A standard deviation object constructor. Running deviation (avoid growing arrays) which
// is round-off error resistant. Based on an algorithm found in a Knuth book.
class StandardDeviation {

    constructor() {
        this.v = 0;
        this.w = 0;
        this.S = 0;
        this.count = 0;
    }

    // Add a measurement. Also calculates updates to stepwise parameters which are later used
    // to determine sigma.
    add(measurement) {
        this.count += 1;
        this.w = this.v;
        this.v = this.v + (measurement - this.v) / this.count;
        this.S = this.S + (measurement - this.w) * (measurement - this.v);
    }

    // Performs the final step needed to get the standard deviation and returns it.
    get() {
        if (this.count < 2) {
            // There are less measurements accumulated than necessary to perform computation
            return 0.0;
        } else {
            return Math.sqrt(this.S / (this.count));
        }
    }

    // Replaces the value x currently present in this sample with the
    // new value y. In a sliding window, x is the value that
    // drops out and y is the new value entering the window. The sample
    // count remains constant with this operation.
    replace(x, y) {
        const deltaYX = y - x;
        const deltaX = x - this.v;
        const deltaY = y - this.v;
        this.v = this.v + deltaYX / this.count;
        const deltaYp = y - this.v;
        const countMinus1 = this.count - 1;
        this.S = this.S - this.count / countMinus1 * (deltaX * deltaX - deltaY * deltaYp) - deltaYX * deltaYp / countMinus1;
    }

    // Remove a measurement. Also calculates updates to stepwise parameters which are later used
    // to determine sigma.
    remove(x) {
        this.w = (this.count * this.v - x) / (this.count - 1);
        this.S -= (x - this.v) * (x - this.w);
        this.v = this.w;
        this.count -= 1;
    }
}




function CBuffer() {
    // handle cases where "new" keyword wasn't used
    if (!(this instanceof CBuffer)) {
        // multiple conditions need to be checked to properly emulate Array
        if (arguments.length > 1 || typeof arguments[0] !== 'number') {
            return CBuffer.apply(new CBuffer(arguments.length), arguments);
        } else {
            return new CBuffer(arguments[0]);
        }
    }
    // if no arguments, then nothing needs to be set
    if (arguments.length === 0)
        throw new Error('Missing Argument: You must pass a valid buffer size');
    // this is the same in either scenario
    this.length = this.start = 0;
    // set to callback fn if data is about to be overwritten
    this.overflow = null;
    // set to callback fn if data is about to be overwritten
    this.maxIndex = null;
    this.minIndex = null;
    this.max = null;
    this.min = null;
    this.sum = null;
    this.mean = null;
    this.standardDeviation = new StandardDeviation();
    // emulate Array based on passed arguments
    if (arguments.length > 1 || typeof arguments[0] !== 'number') {
        this.data = new Array(arguments.length);
        this.end = (this.size = arguments.length) - 1;
        this.push.apply(this, arguments);
    } else {
        this.data = new Array(arguments[0]);
        this.end = (this.size = arguments[0]) - 1;
    }
    // need to `return this` so `return CBuffer.apply` works
    return this;
}

function defaultComparitor(a, b) {
    return a == b ? 0 : a > b ? 1 : -1;
}

function mod(n, m) {
    return ((n % m) + m) % m;
}

CBuffer.prototype = {
    // properly set constructor
    constructor : CBuffer,

    /* mutator methods */
    // pop last item
    pop : function () {
        var item;
        if (this.length === 0) return;
        item = this.data[this.end];
        // remove the reference to the object so it can be garbage collected
        delete this.data[this.end];
        this.end = (this.end - 1 + this.size) % this.size;
        this.length--;
        return item;
    },
    // push item to the end
    push : function () {
        var i = 0;
        var returnOverflow = false;
        // check if overflow is set, and if data is about to be overwritten
        if (this.overflow && this.length + arguments.length > this.size) {
            // call overflow function and send data that's about to be overwritten
            for (; i < this.length + arguments.length - this.size; i++) {
                returnOverflow = this.data[(this.end + i + 1) % this.size];
                // this.overflow(this.data[(this.end + i + 1) % this.size], this);
            }
        }
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for (i = 0; i < arguments.length; i++) {
            this.data[(this.end + i + 1) % this.size] = arguments[i];
        }
        // recalculate length
        if (this.length < this.size) {
            if (this.length + i > this.size) this.length = this.size;
            else this.length += i;
        }
        // recalculate end
        this.end = (this.end + i) % this.size;
        // recalculate start
        this.start = (this.size + this.end - this.length + 1) % this.size;
        // return number current number of items in CBuffer
        return returnOverflow;
    },
    // reverse order of the buffer
    reverse : function () {
        var i = 0,
            tmp;
        for (; i < ~~(this.length / 2); i++) {
            tmp = this.data[(this.start + i) % this.size];
            this.data[(this.start + i) % this.size] = this.data[(this.start + (this.length - i - 1)) % this.size];
            this.data[(this.start + (this.length - i - 1)) % this.size] = tmp;
        }
        return this;
    },
    // rotate buffer to the left by cntr, or by 1
    rotateLeft : function (cntr) {
        if (typeof cntr === 'undefined') cntr = 1;
        if (typeof cntr !== 'number') throw new Error("Argument must be a number");
        while (--cntr >= 0) {
            this.push(this.shift());
        }
        return this;
    },
    // rotate buffer to the right by cntr, or by 1
    rotateRight : function (cntr) {
        if (typeof cntr === 'undefined') cntr = 1;
        if (typeof cntr !== 'number') throw new Error("Argument must be a number");
        while (--cntr >= 0) {
            this.unshift(this.pop());
        }
        return this;
    },
    // remove and return first item
    shift : function () {
        var item;
        // check if there are any items in CBuff
        if (this.length === 0) return;
        // store first item for return
        item = this.data[this.start];
        // recalculate start of CBuffer
        this.start = (this.start + 1) % this.size;
        // decrement length
        this.length--;
        return item;
    },
    // sort items
    sort : function (fn) {
        this.data.sort(fn || defaultComparitor);
        this.start = 0;
        this.end = this.length - 1;
        return this;
    },
    // add item to beginning of buffer
    unshift : function () {
        var i = 0;
        var returnOverflow = false;

        if (this.length == this.size) {
            returnOverflow = this.last();
        }

        for (i = 0; i < arguments.length; i++) {
            this.data[(this.size + this.start - (i % this.size) - 1) % this.size] = arguments[i];
        }
        if (this.size - this.length - i < 0) {
            this.end += this.size - this.length - i;
            if (this.end < 0) this.end = this.size + (this.end % this.size);
        }
        if (this.length < this.size) {
            if (this.length + i > this.size) this.length = this.size;
            else this.length += i;
        }
        this.start -= arguments.length;
        if (this.start < 0) this.start = this.size + (this.start % this.size);

        this.recalculateMaxMin(arguments[0], returnOverflow);

        this.sum += arguments[0];
        if (returnOverflow) {
            this.sum -= returnOverflow;

            this.standardDeviation.replace(returnOverflow, arguments[0])
        }
        else {
            this.standardDeviation.add(arguments[0]);
        }

        this.mean = this.sum / this.length;



        return returnOverflow;
    },

    /* accessor methods */
    // return index of first matched element
    indexOf : function (arg, idx) {
        if (!idx) idx = 0;
        for (; idx < this.length; idx++) {
            if (this.data[(this.start + idx) % this.size] === arg) return idx;
        }
        return -1;
    },
    // return last index of the first match
    lastIndexOf : function (arg, idx) {
        if (!idx) idx = this.length - 1;
        for (; idx >= 0; idx--) {
            if (this.data[(this.start + idx) % this.size] === arg) return idx;
        }
        return -1;
    },

    // return the index an item would be inserted to if this
    // is a sorted circular buffer
    sortedIndex : function(value, comparitor, context) {
        comparitor = comparitor || defaultComparitor;
        var isFull = this.length === this.size,
            low = this.start,
            high = isFull ? this.length - 1 : this.length;

        // Tricky part is finding if its before or after the pivot
        // we can get this info by checking if the target is less than
        // the last item. After that it's just a typical binary search.
        if (low && comparitor.call(context, value, this.data[high]) > 0) {
            low = 0, high = this.end;
        }

        while (low < high) {
            var mid = (low + high) >>> 1;
            if (comparitor.call(context, value, this.data[mid]) > 0) low = mid + 1;
            else high = mid;
        }
        return !isFull ? low :
            // http://stackoverflow.com/a/18618273/1517919
            (((low - this.start) % this.length) + this.length) % this.length;
    },

    /* iteration methods */
    // check every item in the array against a test
    every : function (callback, context) {
        var i = 0;
        for (; i < this.length; i++) {
            if (!callback.call(context, this.data[(this.start + i) % this.size], i, this))
                return false;
        }
        return true;
    },
    // loop through each item in buffer
    // TODO: figure out how to emulate Array use better
    forEach : function (callback, context) {
        var i = 0;
        for (; i < this.length; i++) {
            callback.call(context, this.data[(this.start + i) % this.size], i, this);
        }
    },
    // construct new CBuffer of same length, apply map function, and return new CBuffer
    map : function (callback, context) {
        var outCBuffer = new CBuffer(this.size);
        for (var i = 0; i < this.length; i++) {
            var n = (this.start + i) % this.size;
            outCBuffer.push(callback.call(context, this.data[n], i, this));
        }
        return outCBuffer;
    },
    // check items agains test until one returns true
    // TODO: figure out how to emulate Array use better
    some : function (callback, context) {
        var i = 0;
        for (; i < this.length; i++) {
            if (callback.call(context, this.data[(this.start + i) % this.size], i, this))
                return true;
        }
        return false;
    },
    // calculate the average value of a circular buffer
    avg : function () {
        return this.length == 0 ? 0 : (this.sum() / this.length);
    },
    // loop through each item in buffer and calculate sum
    sum : function () {
        var index = this.length;
        var s = 0;
        while (index--) s += this.data[index];
        return s;
    },
    // loop through each item in buffer and calculate sum
    getMaxPosition : function () {
        // return 0
        return (this.start + this.start + this.maxIndex) % this.size;
    },
    // loop through each item in buffer and calculate sum
    getStandardDeviation : function () {
        // return 0
        return this.standardDeviation.get();
    },
    // loop through each item in buffer and calculate sum
    getMinPosition : function () {
        // return 0
        return (this.start + this.start + this.minIndex) % this.size;
    },
    recalculateMaxMin : function (newValue, returnOverflow) {

        if (this.length == 1) {

            this.max = newValue;
            this.maxIndex = this.start;

            this.min = newValue;
            this.minIndex = this.start;

            return;
        }



        // Max / Mins
        if (newValue > this.max) {
            this.max = newValue;
            this.maxIndex = this.start;
        }
        if (newValue < this.min) {
            this.min = newValue;
            this.minIndex = this.start;
        }

        // If overflow max or min recalculate
        if (
            returnOverflow && (returnOverflow >= this.max || returnOverflow <= this.min)
        ) {

            this.maxIndex = 0;
            this.minIndex = 0;
            this.max = this.data[0];
            this.min = this.data[0];

            for (let i = 0; i < this.length; i++) {

                if (this.data[i] > this.max) {
                    this.maxIndex = i;
                    this.max = this.data[i];
                }
                if (this.data[i] < this.min) {
                    this.minIndex = i;
                    this.min = this.data[i];
                }
            }
        }
    },
    // loop through each item in buffer and calculate median
    median : function () {
        if (this.length === 0)
            return 0;
        var values = this.slice().sort(defaultComparitor);
        var half = Math.floor(values.length / 2);
        if(values.length % 2)
            return values[half];
        else
            return (values[half-1] + values[half]) / 2.0;
    },
    /* utility methods */
    // reset pointers to buffer with zero items
    // note: this will not remove values in cbuffer, so if for security values
    //       need to be overwritten, run `.fill(null).empty()`
    empty : function () {
        var i = 0;
        this.length = this.start = 0;
        this.end = this.size - 1;
        return this;
    },
    // fill all places with passed value or function
    fill : function (arg) {
        var i = 0;
        if (typeof arg === 'function') {
            while(this.data[i] = arg(), ++i < this.size);
        } else {
            while(this.data[i] = arg, ++i < this.size);
        }
        // reposition start/end
        this.start = 0;
        this.end = this.size - 1;
        this.length = this.size;
        return this;
    },
    // return first item in buffer
    first : function () {
        return this.data[this.start];
    },
    // return last item in buffer
    last : function () {
        return this.data[this.end];
    },
    // return specific index in buffer
    get : function (arg) {
        return this.data[mod(this.start + arg, this.size)];
    },
    isFull : function (arg) {
        return this.size === this.length;
    },
    // set value at specified index
    set : function (idx, arg) {
        return this.data[(this.start + idx) % this.size] = arg;
    },
    // return clean array of values
    toArray : function () {
        return this.slice();
    },
    // return a string based on the array
    join : function(separator) {
        if (!separator) separator = ',';
        var outString = new String(this.data[0]);
        for (var i = 1; i < this.length; i++) {
            var n = (this.start + i) % this.size;
            outString = outString.concat(separator, this.data[i]);
        }
        return outString;
    },
    // slice the buffer to an arraay
    slice : function (start, end) {
        var size = this.length;

        start = +start || 0;

        if (start < 0) {
            if (start >= end)
                return [];
            start = (-start > size) ? 0 : size + start;
        }

        if (end == null || end > size)
            end = size;
        else if (end < 0)
            end += size;
        else
            end = +end || 0;

        size = start < end ? end - start : 0;

        var result = Array(size);
        for (var index = 0; index < size; index++) {
            result[index] = this.data[(this.start + start + index) % this.size];
        }
        return result;
    }
};

var bufferLength = 3;
var numbersToGenerate = 10;

var circularBufferN = new CBuffer(bufferLength);
var valuesToEnqueueForDemoPurposes = Array.from(Array(numbersToGenerate)).map(x=>Math.random() * 1000)

for (let i = 0; i < valuesToEnqueueForDemoPurposes.length; i++) {
    var newValue = valuesToEnqueueForDemoPurposes[i];

    console.log("\n\nNEW VALUE****************************************************************:");
    console.log(newValue);

    console.log("STARTING UNSHIFT:");
    console.log(circularBufferN.unshift(newValue));

    let valuesArray = circularBufferN.data;

    var maxIndex = circularBufferN.maxIndex;
    var minIndex = circularBufferN.minIndex;
    var max = valuesArray[maxIndex];
    var min = valuesArray[minIndex];

    console.log("Max Index");
    console.log(maxIndex);
    console.log("Max:");
    console.log(max);
    console.log("Min Index:");
    console.log(minIndex);
    console.log("Min:");
    console.log(min);
    console.log("Start:");
    console.log(circularBufferN.start);
    console.log("ORDERED ARRAY:");
    console.log(circularBufferN.toArray());
    console.log("Max Position:");
    console.log(circularBufferN.getMaxPosition());
    console.log("Min Position:");
    console.log(circularBufferN.getMinPosition());
    console.log('Sum:');
    console.log(circularBufferN.sum);
    console.log("mean:");
    console.log(circularBufferN.mean);
    console.log("Derived Standard Deviation");
    console.log(circularBufferN.getStandardDeviation());

}