Bisect Insertion Container for Calculating Running Median

Question

I'm looking for general feedback on this implementation. What issues might it have? How could it be improved?

public class FindRunningMedian
{
    public void Run(string[] args)
    {
        var bound = 100000;
        var rando = new Random();
        var values = new[] { bound.ToString() }.Concat((from i in Enumerable.Range(0, bound)
                                                        select rando.Next(int.MaxValue / 2).ToString())).ToArray();

        RunBiSect(values);
    }

    public void RunBiSect(string[] args)
    {
        var count = Convert.ToInt32(args.First());
        var valus = args.Skip(1).Select(s => Convert.ToInt32(s)).ToArray();
        var sortd = new MedianList(count);

        foreach (var value in valus)
        {
            Console.WriteLine($"{sortd.InsertForMedian(value):F1} ");
        }
    }

    public class MedianList
    {
        private int _count;
        private float _iters;
        private int[] _values;

        public MedianList(int capacity)
        {
            _values = new int[capacity];
        }

        public int Count { get { return _count; } }

        public float Iterations { get { return _iters; } }

        public float IterationsPer { get { return _iters / Math.Max(1, _count); } }

        public int[] GetValues()
        {
            var copy = new int[_values.Length];
            _values.CopyTo(copy, 0);
            return copy;
        }

        public float InsertForMedian(int value)
        {
            Insert(value);
            var median = 0.0f;
            var middle = _count / 2;

            if (_count == 1) { median = _values[0]; }
            else if (_count % 2 == 0) { median = (_values[middle] + _values[middle - 1]) / 2.0f; }
            else { median = _values[middle]; }

            return median;
        }

        public void Insert(int value)
        {
            if (_count == 0) { _values[0] = value; }
            else
            {
                var index = FindDestinationIndex(value);
                Array.Copy(_values, index, _values, index + 1, _count - index);
                _values[index] = value;
            }
            _count++;
        }

        public int FindDestinationIndex(int value)
        {
            var max = _count - 1;
            int mid = 0, cmp = 0, min = 0;

            if (value.CompareTo(_values[0]) <= 0) { return 0; }
            else if (value.CompareTo(_values[_count - 1]) >= 0) { return _count; }

            while (max > (min + 1))
            {
                mid = Convert.ToInt32(Math.Min(Math.Ceiling((max - min) / 2.0f) + min, _count - 1));
                cmp = value.CompareTo(_values[mid]);

                if (cmp == 0) { return mid; }
                else if (cmp > 0) { min = Math.Max(mid, min + 1); }
                else if (cmp < 0) { max = Math.Min(mid, max - 1); }

                _iters++;
            }

            mid = value.CompareTo(_values[min]) > 0 && value.CompareTo(_values[max]) <= 0 ? max : min;

            cmp = value.CompareTo(_values[mid]);

            var index = cmp > 0 ? mid + 1 : mid;
            return index;
        }
    }
}

Answer 1

This

var values = new[] { bound.ToString() }.Concat(..).ToArray();
RunBiSect(values);

plus this

public void RunBiSect(string[] args)

plus this

var count = Convert.ToInt32(args.First());
var valus = args.Skip(1).Select(s => Convert.ToInt32(s)).ToArray();

is a super weird way of passing arguments from method to another. I'm not sure if you know it but methods can take more then one parameter ;-)

---

var valus = ..;
var sortd = ..;

Where is the e? Don't you like it? You should not use abbreviations unless they are well known like html or xml etc.

---

public class MedianList

Nested classes should not be public. Then this class is not a list and should be called like that. MedialCalculator sounds much better. Shouldn't the InsertForMedian API be named CalcMedian?

---

public float IterationsPer { get { return _iters / Math.Max(1, _count); } }

Here is something missing: IterationsPer what?

Answer 2

The main my concern is about function FindDestinationIndex, specifically how you organized the while cycle. I would like to suggest this implementation instead of the original one

private int FindDestinationIndex(int value) {
    int min = 0;
    int max = _count - 1;
    if (value.CompareTo(_values[0]) <= 0) {
        return 0;
    }
    if (value.CompareTo(_values[_count - 1]) >= 0) {
        return _count;
    }
    while (min < max) {
        int mid = ((max - min) >> 1) + min;
        if (value <= _values[mid]) {
            max = mid;
        } else {
            min = mid + 1;
        }
        _iters++;
    }
    return min;
}

because

1. There is no expensive float operations.
2. The code is much more cleaner and easy to debug.

In your implementation there is Iterations variable, which was used, I guess, to evaluate the while cycle efficiency. So my implementations is showing pretty similar results.

---

But I think more important that for every Insert event you are using Array.Copy and this is way too much. I would recommend to use more appropriate data structure - heap. Sadly there is no heap implementation in the standard library, so you can find a few NuGet packages. For this implementation I used The C5 Generic Collection Library

public float InsertForMedian(int value) {
    _count++;
    if (_count == 1) {
        _leftHeap.Add(value);
        return _leftHeap.FindMax();
    }
    if (_count % 2 == 0) {
        if (value < _leftHeap.FindMax()) {
            //_count is odd and value < max of left heap
            _rightHeap.Add(_leftHeap.DeleteMax());
            _leftHeap.Add(value);
        } else {
            //_count is odd and value >= max of left heap
            _rightHeap.Add(value);
        }
        return (_leftHeap.FindMax() + _rightHeap.FindMin()) / 2.0f;
    }
    if (value < _leftHeap.FindMax()) {
        //_count is even and value < max of left heap
        _leftHeap.Add(value);
    } else {
        //_count is even and value >= max of left heap
        _leftHeap.Add(_rightHeap.DeleteMin());
        _rightHeap.Add(value);
    }
    return _leftHeap.FindMax();
}

But as I understand from this manual, it is Binary variant of the heap data structure (correct me if I am wrong). You can try to use/find Fibonacci variant to speed up an insertion operation.

---

Performance measurement (by BenchmarkDotNet)

Original version

using System;

public class MedianListGio {
    private int _count;
    private float _iters;
    private int[] _values;

    public MedianListGio(int capacity) {
        _values = new int[capacity];
    }

    public int Count => _count;

    public float Iterations => _iters;

    public float IterationsPer => _iters / Math.Max(1, _count);

    public float InsertForMedian(int value) {
        Insert(value);
        float median = 0.0f;
        int middle = _count / 2;

        if (_count == 1) {
            median = _values[0];
        } else if (_count % 2 == 0) {
            median = (_values[middle] + _values[middle - 1]) / 2.0f;
        } else {
            median = _values[middle];
        }
        return median;
    }

    private void Insert(int value) {
        if (_count == 0) {
            _values[0] = value;
        } else {
            int index = FindDestinationIndex(value);
            Array.Copy(_values, index, _values, index + 1, _count - index);
            _values[index] = value;
        }
        _count++;
    }

    private int FindDestinationIndex(int value) {
        int max = _count - 1;
        int mid = 0, cmp = 0, min = 0;
        if (value <= _values[0]) {
            return 0;
        }
        if (value.CompareTo(_values[_count - 1]) >= 0) {
            return _count;
        }
        while (max > (min + 1)) {
            mid = Convert.ToInt32(Math.Min(Math.Ceiling((max - min) / 2.0f) + min, _count - 1));

            cmp = value.CompareTo(_values[mid]);
            if (cmp == 0) {
                return mid;
            }
            if (cmp > 0) {
                min = Math.Max(mid, min + 1);
            } else if (cmp < 0) {
                max = Math.Min(mid, max - 1);
            }

            _iters++;
        }

        mid = value.CompareTo(_values[min]) > 0 && value.CompareTo(_values[max]) <= 0 ? max : min;
        cmp = value.CompareTo(_values[mid]);
        var index = cmp > 0 ? mid + 1 : mid;
        return index;
    }
}

Modified original version

using System;

public class MedianListPgs {
    private int _count;
    private float _iters;
    private readonly int[] _values;

    public MedianListPgs(int capacity) {
        _values = new int[capacity];
    }

    public int Count => _count;

    public float Iterations => _iters;

    public float IterationsPer => _iters / Math.Max(1, _count);

    public float InsertForMedian(int value) {
        Insert(value);
        int middle = _count / 2;
        return _count % 2 == 0 ? (_values[middle] + _values[middle - 1]) / 2.0f : _values[middle];
    }

    private void Insert(int value) {
        if (_count == 0) {
            _values[0] = value;
        } else {
            int index = FindDestinationIndex(value);
            Array.Copy(_values, index, _values, index + 1, _count - index);
            _values[index] = value;
        }
        _count++;
    }

    private int FindDestinationIndex(int value) {
        int min = 0;
        int max = _count - 1;
        if (value.CompareTo(_values[0]) <= 0) {
            return 0;
        }
        if (value.CompareTo(_values[_count - 1]) >= 0) {
            return _count;
        }
        while (min < max) {
            int mid = ((max - min) >> 1) + min;
            if (value <= _values[mid]) {
                max = mid;
            } else {
                min = mid + 1;
            }
            _iters++;
        }
        return min;
    }
}

Heap-based version

using C5;

public class MedianListPgsHeapC5 {
    private int _count;
    /// <summary>
    /// The FindMin/Max O(1)
    /// DeleteMin/Max and Add is O(log n)
    /// </summary>
    private readonly IntervalHeap<int> _leftHeap;
    private readonly IntervalHeap<int> _rightHeap;

    public MedianListPgsHeapC5(int capacity) {
        _count = 0;
        _leftHeap = new IntervalHeap<int>(capacity / 2);
        _rightHeap = new IntervalHeap<int>(capacity / 2);
    }

    public int Count => _count;

    //invariant: size(_leftHeap)-size(_rightHeap) is 0 or 1
    public float InsertForMedian(int value) {
        _count++;
        if (_count == 1) {
            _leftHeap.Add(value);
            return _leftHeap.FindMax();
        }
        if (_count % 2 == 0) {
            if (value < _leftHeap.FindMax()) {
                //_count is odd and value < max of left heap
                _rightHeap.Add(_leftHeap.DeleteMax());
                _leftHeap.Add(value);
            } else {
                //_count is odd and value >= max of left heap
                _rightHeap.Add(value);
            }
            return (_leftHeap.FindMax() + _rightHeap.FindMin()) / 2.0f;
        }
        if (value < _leftHeap.FindMax()) {
            //_count is even and value < max of left heap
            _leftHeap.Add(value);
        } else {
            //_count is even and value >= max of left heap
            _leftHeap.Add(_rightHeap.DeleteMin());
            _rightHeap.Add(value);
        }
        return _leftHeap.FindMax();
    }
}

Running time

As you see the heap implementation outperforms all the rest solutions.

---

All code can be found here (as well as benchmark log file).