I'm getting different values than the expected ones, so the unit test below fails as a result. The issue is that RollingWindow is FIFO and it's supposed to be LIFO.
This is what _window actually is:
10 0 0 0
10 12 0 0
10 12 9 0
10 12 9 10
15 12 9 10 (wrong) => 12 9 10 15 (correct)
15 13 9 10 (wrong) => 9 10 15 13 (correct)
What variance is and how it is calculated:
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
These are the expected values:
input = 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
Code
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();
}
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);
}
}
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));
}
}
Unit test
[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);
}
CodePudding user response：
The problem is here:
var removedValue = _window[_period - 1];
Because _period === 4, you are removing the last number in the window. The correct code should be
var removedValue = _window[0];