RollingWindow实现错误导致Variance计算值不符，单元测试失败

当前RollingWindow是FIFO（先进先出）实现，但实际需要是LIFO（后进先出），导致方差计算的实际值与预期值不符，单元测试失败。

当前窗口实际状态（错误）与期望状态对比 #

10 0 0 0
10 12 0 0
10 12 9 0
10 12 9 10
15 12 9 10 (错误) => 12 9 10 15 (正确)
15 13 9 10 (错误) => 9 10 15 13 (正确)

方差定义及计算示例 #

v1 = 40
v2 = 30
v3 = 20

avg = (40 + 30 + 20) / 3 = 30
variance = sum((v1-avg)^2, (v2-avg)^2, (v3-avg)^2)) / 3
variance = sum((40-30)^2, (30-30)^2, (20-30)^2) / 3 = 66.6667
stdev = sqrt(variance) = 8.16497

预期方差计算结果 #

输入序列：10, 12, 9, 10, 15, 13, 18, 18, 20, 24

variance of 10, 12, 9, 10 = 1.1875
variance of 12, 9, 10, 15 = 5.25
variance of 9, 10, 15, 13 = 5.6875
variance of 10, 15, 13, 18 = 8.5
variance of 15, 13, 18, 18 = 4.5
variance of 13, 18, 18, 20 = 6.6875
variance of 18, 18, 20, 24 = 6

实现代码 #

Variance类及接口 #

public sealed class Variance : IIndicator<decimal, decimal>
{
    private readonly RollingWindow<decimal> _window;
    private readonly int _period;
    private decimal _rollingSum;
    private decimal _rollingSumOfSquares;

    public Variance(int period)
    {
        if (period <= 1)
        {
            throw new ArgumentOutOfRangeException(nameof(period), "The period cannot be less than or equal to 1");
        }

        _period = period;
        _window = new RollingWindow<decimal>(period);
    }

    public bool IsReady => throw new NotImplementedException();

    public List<decimal> Source => throw new NotImplementedException();

    public decimal ComputeNextValue(decimal source)
    {
        _window.Add(source);

        _rollingSum += source;
        _rollingSumOfSquares += source * source;

        if (_window.Count < _period)
        {
            return 0;
        }

        var meanValue1 = _rollingSum / _period;
        var meanValue2 = _rollingSumOfSquares / _period;

        if (_period == _window.WindowSize)
        {
            var removedValue = _window[_period - 1];
            _rollingSum -= removedValue;
            _rollingSumOfSquares -= removedValue * removedValue;
        }

        return meanValue2 - (meanValue1 * meanValue1);
    }

    public void Reset()
    {
        _rollingSum = 0;
        _rollingSumOfSquares = 0;
    }
}

public interface IIndicator<TInput, out TOutput>
    where TInput : notnull
    where TOutput : struct
{
    bool IsReady { get; }
    List<TInput> Source { get; }
    TOutput ComputeNextValue(TInput source);
    void Reset();
}

RollingWindow类 #

public sealed class RollingWindow<T> : IList<T>
{
    private readonly T[] _window;
    private int _start;

    private int _version;

    public RollingWindow(int windowSize)
    {
        if (windowSize <= 0)
        {
            throw new ArgumentOutOfRangeException(nameof(windowSize), "windowSize must be at least 1");
        }

        WindowSize = windowSize;
        _window = new T[windowSize];
    }

    public int Count { get; private set; }

    public int WindowSize { get; }

    public bool IsReadOnly => false;

    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException(nameof(index),
                    "index must be greater than zero and less than the size of the collection");
            }

            return _window[WrapIndex(_start + index)];
        }
        set
        {
            if (index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException(nameof(index),
                    "index must be greater than zero and less than the size of the collection");
            }

            _window[WrapIndex(_start + index)] = value;
        }
    }

    public void Add(T item)
    {
        if (Count < WindowSize)
        {
            Count++;
        }
        else
        {
            _start = WrapIndex(_start + 1);
        }

        this[Count - 1] = item;

        _version++;
    }

    public void Insert(int index, T item)
    {
        if (index < 0 || index > Count)
        {
            throw new ArgumentOutOfRangeException(nameof(index),
                "index must be greater than zero and less than or equal to the size of the collection");
        }

        if (Count >= WindowSize)
        {
            throw new InvalidOperationException("Unable to insert item; rolling window is full");
        }

        // Increase count first to
        // prevent out of range indexes
        Count++;

        if (index <= WindowSize / 2)
        {
            // Shift left to make room
            _start = WrapIndex(_start - 1);

            for (var i = 0; i < index; i++)
            {
                this[i] = this[i + 1];
            }
        }
        else
        {
            // Shift right to make room
            for (var i = Count - 1; i > index; i--)
            {
                this[i] = this[i - 1];
            }
        }

        // Insert the item and
        // increment the version
        this[index] = item;
        _version++;
    }

    public bool Remove(T item)
    {
        var index = IndexOf(item);

        if (index < 0)
        {
            return false;
        }

        RemoveAt(index);
        return true;
    }

    public void RemoveAt(int index)
    {
        if (index <= WindowSize / 2)
        {
            // Shift right to fill space
            for (var i = index; i > 0; i--)
            {
                this[i] = this[i - 1];
            }

            this[0] = default!;
            _start++;
        }
        else
        {
            // Shift left to fill space
            for (var i = index; i < Count - 1; i++)
            {
                this[i] = this[i + 1];
            }

            this[Count - 1] = default!;
        }

        Count--;
        _version++;
    }

    public int IndexOf(T item)
    {
        var i = 0;

        foreach (var obj in this)
        {
            if (Equals(obj, item))
            {
                return i;
            }

            i++;
        }

        return -1;
    }

    public bool Contains(T item)
    {
        return IndexOf(item) >= 0;
    }

    public void Clear()
    {
        for (var i = 0; i < WindowSize; i++)
        {
            _window[i] = default!;
        }

        Count = 0;
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        int i;

        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }

        if (arrayIndex < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(arrayIndex), "arrayIndex must be greater than zero");
        }

        if (Count > array.Length - arrayIndex)
        {
            throw new ArgumentException("Not enough available space in array to copy elements from rolling window");
        }

        i = 0;

        foreach (var item in this)
        {
            array[i] = item;
            i++;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        var version = _version;
        var count = 0;

        for (var i = _start; i < WindowSize; i++)
        {
            if (version != _version)
            {
                throw new InvalidOperationException("Collection was modified; enumeration operation may not execute");
            }

            if (count >= Count)
            {
                break;
            }

            count++;

            yield return _window[i];
        }

        for (var i = 0; i < _start; i++)
        {
            if (version != _version)
            {
                throw new InvalidOperationException("Collection was modified; enumeration operation may not execute");
            }

            if (count >= Count)
            {
                break;
            }

            count++;

            yield return _window[i];
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    private int WrapIndex(int index)
    {
        return (int)Euclidean.Mod(index, WindowSize);
    }
}

Euclidean工具类 #

public static class Euclidean
{
    public static double Mod(double numerator, double denominator)
    {
        var quotient = Math.Floor(numerator / denominator);
        return numerator - (quotient * denominator);
    }

    public static double Wrap(double value, double minimum, double range)
    {
        var transform = value - minimum;
        var remainder = Mod(transform, range);
        return remainder + minimum;
    }

    public static int GreatestCommonDenominator(this IEnumerable<int> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(GreatestCommonDenominator);
    }

    public static int GreatestCommonDenominator(params int[] source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(GreatestCommonDenominator);
    }

    public static int GreatestCommonDenominator(int a, int b)
    {
        return b != 0 ? GreatestCommonDenominator(b, a % b) : a;
    }

    public static long GreatestCommonDenominator(this IEnumerable<long> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(GreatestCommonDenominator);
    }

    public static long GreatestCommonDenominator(params long[] source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(GreatestCommonDenominator);
    }

    public static long GreatestCommonDenominator(long a, long b)
    {
        return b != 0 ? GreatestCommonDenominator(b, a % b) : a;
    }

    public static int LeastCommonMultiple(this IEnumerable<int> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(LeastCommonMultiple);
    }

    public static int LeastCommonMultiple(params int[] source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(LeastCommonMultiple);
    }

    public static int LeastCommonMultiple(int a, int b)
    {
        return a * (b / GreatestCommonDenominator(a, b));
    }

    public static long LeastCommonMultiple(this IEnumerable<long> source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(LeastCommonMultiple);
    }

    public static long LeastCommonMultiple(params long[] source)
    {
        if (source == null)
        {
            throw new ArgumentNullException(nameof(source), "source is null");
        }

        return source.Aggregate(LeastCommonMultiple);
    }

    public static long LeastCommonMultiple(long a, long b)
    {
        return a * (b / GreatestCommonDenominator(a, b));
    }
}

单元测试代码 #

[Fact]
public void ComputeNextValue_ShouldReturnExpectedValues_WhenGivenPrices()
{
    // Arrange
    const int period = 4;
    var prices = new decimal[] { 10, 12, 9, 10, 15, 13, 18, 18, 20, 24 };
    var expected = new[]
    {
        0, 0, 0, 1.1875m, 5.25m, 5.6875m, 8.5m, 4.5m, 6.6875m, 6
    };

    var variance = new Variance(period);

    // Act
    var actual = prices
        .Select(x => variance.ComputeNextValue(x))
        .ToList();

    // Assert
    actual.Should().BeEquivalentTo(expected);
}

内容的提问来源于stack exchange，提问作者nop