Spotting Metrics - Star Luminosities

gistfile1.txt

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Order;

using System;
using System.Linq;

namespace BackToSchool.CSharp.Misc
{
    public class SpottingMetrics
    {
        public static double GetSpottingMetric_StripZeros(int[] results)
        {
            var result = double.MaxValue;

            // couldn't we just strip out all the zeros?
            results = results.ToList().Where(x => x != 0).ToArray();
            var max = results.Length - 3;

            for (var i = 0; i <= max; i++)
            {
                // get each window of 3
                var window = results[i..(3 + i)];
                var windowResult = window.Sum() / 3.00;
                if (windowResult < result)
                {
                    result = windowResult;
                }
            }

            return result;
        }

        public static double GetSpottingMetric_TwoPointers(int[] results, int targetWindowSize)
        {
            // seems to be a two-pointer situation
            // need all recorded "3 successful measurements" (i.e. non-zero)

            var result = double.MaxValue;

            var left = 0;
            var right = 1;
            var windowLength = 0;

            var max = results.Length - targetWindowSize;

            while (left < max)
            {
                // if array value at left is non-zero, begin moving right pointer
                if (results[left] != 0) 
                {
                    // begin creating windows of length = targetWindowSize with non-zero elements
                    while (windowLength < targetWindowSize && right < results.Length - 1)
                    {
                        right++;
                        if (results[right] != 0)
                        {
                            windowLength = right - left;
                        }
                    }

                    // we now have a window of length = targetWindowSize
                    // sum it and calculate the average of all values in the window
                    var windowSum = results.AsSpan(left, right - left + 1).ToArray().Sum();
                    var windowResult = windowSum / 3.00;
                    if (windowResult < result)
                    {
                        result = windowResult;
                    }
                }

                // advance the left pointer
                left++;

                // reset the current window length for the next iteration
                windowLength = 0;
            }

            return result;
        }
    }

    [MemoryDiagnoser]
    [Orderer(SummaryOrderPolicy.FastestToSlowest)]
    [RankColumn]
    public class SpottingMetricsBenchmarks
    {
        private const int Iterations = 1000;
        private const int ArraySize = 10;
        private Random rand = new Random();

        private const int TargetWindowSize = 3;

        [Benchmark(Baseline = true)]
        public void StripZeroes()
        {
            // generate the array
            var values = new int[ArraySize];

            for (var x = 0; x < ArraySize; x++)
            {
                values[x] = rand.Next(0, 9);
            }

            for (var i = 0; i < Iterations; i++)
            {
                SpottingMetrics.GetSpottingMetric_StripZeros(values);
            }
        }

        [Benchmark]
        public void TwoPointers()
        {
            // generate the array
            var values = new int[ArraySize];

            for (var x = 0; x < ArraySize; x++)
            {
                values[x] = rand.Next(0, 9);
            }

            for (var i = 0; i < Iterations; i++)
            {
                SpottingMetrics.GetSpottingMetric_TwoPointers(values, TargetWindowSize);
            }
        }
    }
}

Oddly enough, when n is sufficiently large (either in terms of iterations or the size of the input array), the TwoPointers method falls behind and the naive approach takes the lead.

Update. I knew there was even a better way with two pointers. I had used a span earlier, but decided to just convert the array to a span and perform all operations there.

New method:

        public static double GetSpottingMetric_TwoPointers_Alt(int[] results, int targetWindowSize)
        {
            // seems to be a two-pointer situation
            // need all recorded "3 successful measurements" (i.e. non-zero)

            var result = double.MaxValue;

            var left = 0;
            var right = 1;
            var windowLength = 0;

            ReadOnlySpan<int> resultsSpan = results.AsSpan();

            var max = resultsSpan.Length - targetWindowSize;

            while (left < max)
            {
                // if array value at left is non-zero, begin moving right pointer
                if (resultsSpan[left] != 0)
                {
                    // begin creating windows of length = targetWindowSize with non-zero elements
                    while (windowLength < targetWindowSize && right < resultsSpan.Length - 1)
                    {
                        right++;
                        if (resultsSpan[right] != 0)
                        {
                            windowLength = right - left;
                        }
                    }

                    // we now have a window of length = targetWindowSize
                    // sum it and calculate the average of all values in the window
                    var tmpSum = 0;
                    var ttSpan = resultsSpan.Slice(left, right - left + 1);
                    foreach (var i in ttSpan)
                    {
                        tmpSum += i;
                    }

                    var windowResult = tmpSum / (double)targetWindowSize;
                    if (windowResult < result)
                    {
                        result = windowResult;
                    }
                }

                // advance the left pointer
                left++;

                // reset the current window length for the next iteration
                windowLength = 0;
            }

            return result;
        }

New benchmark for a single iteration of 100,000 elements in the array:

Last version of the code is superior in performance and memory.

No more additions will be made.

Initial scratches.

Forgot to include unit tests. Single test case for each method - would normally use [InlineData()] for a series of cases.

using FluentAssertions;

using Xunit;

namespace BackToSchool.CSharp.Tests.Misc
{
    public class SpottingMetricsTests
    {
        [Fact]
        public void GetSpottingMetric_StripZeros()
        {
            // arrange && act
            var result = SpottingMetrics.GetSpottingMetric_StripZeros([1, 3, 0, 1, 5, 0, 0, 1, 0]);

            // assert
            result.Should().BeApproximately(1.666F, 0.1F);
        }

        [Fact]
        public void GetSpottingMetric_TwoPointers()
        {
            // arrange && act
            var result = SpottingMetrics.GetSpottingMetric_TwoPointers([1, 3, 0, 1, 5, 0, 0, 1, 0], 3);

            // assert
            result.Should().BeApproximately(1.666F, 0.1F);
        }

        [Fact]
        public void GetSpottingMetric_TwoPointers_Alt()
        {
            // arrange && act
            var result = SpottingMetrics.GetSpottingMetric_TwoPointers_Alt([1, 3, 0, 1, 5, 0, 0, 1, 0], 3);

            // assert
            result.Should().BeApproximately(1.666F, 0.1F);
        }
    }
}