10
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I think you can easily adapt @JanDotNet grouping for this too, which will reduce it to just a couple of line ;-) \$\endgroup\$ – t3chb0t Jul 28 '16 at 13:38
  • \$\begingroup\$ I don't really understand limitation 1. Even if it's not in memory, what stops it from reading it all into memory as a first step? \$\endgroup\$ – Ben Aaronson Jul 29 '16 at 11:49
  • \$\begingroup\$ Generated in runtime by the application that use RunManager. \$\endgroup\$ – jlvaquero Jul 29 '16 at 12:09
6
\$\begingroup\$

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();

\$\endgroup\$
  • \$\begingroup\$ Your code is always hard to test because you don't place it in a method and one has to write it for himself ;-P I'd like to ask you to do it in future. \$\endgroup\$ – t3chb0t Jul 29 '16 at 7:17
  • \$\begingroup\$ This is a really nice solution. If you add .Skip(1) to the orderedValues in the foreach you'll get rid of the the 1-1 run at the beginning. \$\endgroup\$ – t3chb0t Jul 29 '16 at 8:15
  • \$\begingroup\$ @Disappointed My question was incomplete due to I copy/paste original code kata. Once I reached to similar solution (stright sort) I was asked abot solve it with nuances that makes stright sort unaviable and the new implementation was the origin of my question. Please read the question again. \$\endgroup\$ – jlvaquero Jul 29 '16 at 8:41
  • \$\begingroup\$ @jlvaquero I haven't time today to make changes ... Maybe tomorrow ... \$\endgroup\$ – Disappointed Jul 29 '16 at 8:44
  • \$\begingroup\$ @Disappointed. Don't worry I am not in a hurry. I just want to make sure you understand why I didn't accept your answer. \$\endgroup\$ – jlvaquero Jul 29 '16 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.