CodeKata: Find all the runs in the set

Question

Given a finite set of unique numbers, find all the runs in the set. Runs are 1 or more consecutive numbers.

That is, given {1,59,12,43,4,58,5,13,46,3,6}, the output should be: {1}, {3,4,5,6}, {12,13}, {43}, {46},{58,59}.

Note that the size of the set may be very large and comes form external source at any time (is not fully in memory). Also you may be able to query in any moment while other items are arriving.

So the chalenge is:

1. Can not full set sorting items because comes from external source in any time and need to keep partiar result for quering it in any moment.
2. Avoid binary search, sort again or shift the set on inserts every time a new item is added to speed up the add operation because when set is hurge will kill performance.

This implementation seems to work pretty fast:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;


namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            Stopwatch stopwatch = new Stopwatch();

            Random rand = new Random();
            //int[] initValues = Enumerable.Range(1, 20000000).OrderBy(s => Guid.NewGuid()).Where(x => (rand.Next() % 2) == 0).ToArray();
            int[] initValues = { 1, 59, 12, 43, 4, 58, 5, 13, 46, 3, 6, 2, 8, 9, 54, 37, 22, 105, 44, 7 };

            Console.WriteLine("Number of input items: " + initValues.Length);

            RunManager manager = new RunManager();

        stopwatch.Start(); //measure adding and query 
        foreach (int item in initValues)
        {
            manager.addToIndex(item);
            foreach (var run in manager.runListFromIndex())
            {
                // Console.WriteLine(run.ToString());
            }
        }

        stopwatch.Stop();;

            Console.WriteLine("Millisecons: " + stopwatch.ElapsedMilliseconds);
            Console.ReadLine();

        }
    }

    public class RunManager
    {
        Dictionary<int, Run> upperBoundIndex = new Dictionary<int, Run>(); //index of upperBoud run (9)->{2...9}
        Dictionary<int, Run> lowerBoundIndex = new Dictionary<int, Run>(); //index of lowerBoud run (2)->{2...9}

        public IEnumerable<Run> runList()
        {
            return upperBoundIndex.Values;
        }
        public void add(int item)
        {
            Run upperRun;
            Run lowerRun;

            Run newRun = new Run(item); //create Run with item (3)-> {3..3}

            //find if new item belongs to any existing run

            // found {2..9} if item is (10), delete index entry because it should be updated
            if (upperBoundIndex.TryGetValue(item - 1, out upperRun)) upperBoundIndex.Remove(upperRun.upperBound);

            //found {2..9} if item is (1), delete index entry because it should be updated
            if (lowerBoundIndex.TryGetValue(item + 1, out lowerRun)) lowerBoundIndex.Remove(lowerRun.lowerBound);

            if ((upperRun != null) && (lowerRun != null)) newRun = lowerRun.merge(upperRun);//item is betwen 2 existing runs {1..4} (5) {6..9}, merge existing runs {1..9} 
            else if (upperRun != null) newRun = upperRun.merge(newRun);//item belongs to top of existing run {10} {6..9}, merge runs {6..10}
            else if (lowerRun != null) newRun = lowerRun.merge(newRun); //items belongs to bottom of existing run {5} {6..9}, merge runs {5..9}

            //just update index with new run
            upperBoundIndex[newRun.upperBound] = newRun;
            lowerBoundIndex[newRun.lowerBound] = newRun;
        }

        public RunManager() { }

    }

    public class Run
    {

        public Run(int simpleBound)
        {
            this.upperBound = simpleBound;
            this.lowerBound = simpleBound;
        }

        public Run(int lowerBound, int upperBound)
        {
            this.upperBound = upperBound;
            this.lowerBound = lowerBound;
        }

        private Run() { }

        public int upperBound { get; set; }
        public int lowerBound { get; set; }

        public override string ToString()
        {
            StringBuilder outPut = new StringBuilder("{");
            outPut.Append(lowerBound.ToString());

            for (int i = lowerBound + 1; i <= upperBound; i++)
            {
                outPut.Append("," + i.ToString());
            }

            return outPut.Append("}").ToString();
        }

        public Run merge(Run run)
        {
            Run newRun = new Run();
            newRun.upperBound = run.upperBound > this.upperBound ? run.upperBound : this.upperBound;
            newRun.lowerBound = run.lowerBound < this.lowerBound ? run.lowerBound : this.lowerBound;
            return newRun;

        }
    }
}

But still I have some questions that a peer review could resolve:

1. Is Dictionary<TKey, TValue> the best collection for my indexes in regards of speed? And what about memory footprint?
2. Extreme fragmentation in input set could cause indexes having high memory footprint. How solve that?
3. I can not find speed differences if I initialize Dictionary capacity when I try with 10M items and set capacity at 500000 to prevent (or minimize) runtime growth.

Answer 1

I didn't think about something advanced but even the following straight solution works much faster then your

var orderedValues = initValues.AsParallel().OrderBy(e => e).ToList();
var runs = new List<Run>();
var lastValue = orderedValues.First();
Run lastRun = new Run(lastValue);
foreach (var currentValue in orderedValues)
{
    if (lastValue + 1 == currentValue)
    {
        lastRun.upperBound++;
    }
    else
    {
        runs.Add(lastRun);
        lastRun = new Run(currentValue);
    }

    lastValue = currentValue;
}

Before - 23776 miliseconds
After - 4669 miliseconds

I tested with this
int[] initValues = Enumerable.Range(1, 20000000).OrderBy(s => Guid.NewGuid()).Where(x => (rand.Next() % 2) == 0).ToArray();