带有GetMax和GetMin的O(1) GetMin循环缓冲器

Question

因此，我一直在搜索网络，以找到一种方法来做到这一点，但我没有发现符合我们正在寻找的确切解决方案。

我有一个应用程序，可以将浮点数存储在循环缓冲区中。循环缓冲区类可以在这里找到https://www.npmjs.com/package/circular-buffer。

在我的应用程序中，每隔几毫秒就会有新的数字出现，缓冲区保存着大约60K的值。

不过，为了解决这个问题，我创建了一个10的循环缓冲区，其中包含100个随机生成的数字流，以模拟输入的数据。这是生成模拟流的行：

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

在我当前的设置中，cpu花了太多时间将循环缓冲区转换为数组，然后计算其min、max、min位置/索引数、最大位置/索引数和标准偏差(但stddev不是这个问题的焦点)。

以下是我的当前代码：

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");
}

所以我想知道是否有可能用不同的数据结构来优化这段代码。

我找到的最接近解决这个问题的答案就是这个答案：https://stackoverflow.com/a/48610455

它使用：

• ：N项的队列
• a Min / Max Heap来跟踪min / max项。
• 是一个哈希映射以跟踪每个项目的频率。

但是，这个解决方案的问题是堆总是在增长，而且由于接收到的不同传入数据的数量不同，这将导致一个严重的问题。而且它也只计算出最大值。

也找到了这个c++解决方案，但它只适用于正常队列，最大值(非最小)，我无法在javascript：https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/中进行复制。

有人知道是否可以使用任何组合的数据结构，在O(1)中找到这类场景中的最大值或最小值(有或没有循环缓冲区)？

Answer 1

由于@thomas的建议，我能够更改我所使用的循环缓冲区类，以便在O(1)时平均计算和、平均、最大、最小和标准偏差，但在最坏的O(N)时计算。对我所需要的表演很有魅力。

请注意，就我的目的而言，我只更改了CBuffer循环缓冲区类的"unshift“方法。因此，其他方法不能正确地更新最大值、最小值和标准差。下面是到jsfiddle的链接：https://jsfiddle.net/29f4an7s/

这是我的测试代码：

// 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());

}