CodeKata: Find all the runs in the set

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 may does not fit in memory. Also you may be able to query fast in any moment while other items are arriving from external source.

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();             foreach (int item in initValues)             {                 manager.add(item);             }             stopwatch.Stop();              Console.WriteLine("Millisecons: " + stopwatch.ElapsedMilliseconds);             Console.ReadLine();              foreach (Run run in manager.runList())             {                 Console.WriteLine(run.ToString());             }             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. Input set could be very large (10 Millions). Any idea of how can I reduce memory footprint?
  3. For ordered output I could use SortedDictionary<TKey, TValue> but it is like x5 slower than Dictionary<TKey, TValue>. Any other idea?
  4. I can not find speed differences if I initialize Dictionary capacity when I try with 10M and set capacity at 500000 to prevent (or minimize) runtime growth.

Replay

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

Category: c# Time: 2016-07-28 Views: 0
Tags: .net

Related post

  • Find all solutions which satisfy the given conditions 2015-11-30

    Let $$ m=9n^3+30n^2-9n $$ where $n \in \mathbb{Q^{+}}$ and $m \in \mathbb{Z} $ . Find all solutions which satisfy the given conditions. So I've tried to solve this manually and I was able to receive help but how would I solve this in mathematica. I w

  • How can I find all connected objects of the same type recursively? 2014-01-25

    In my game, when a user selects an object of some type, I'd like to search for all other objects of the same type that are connected to that first one. For example, if the user selects a object of type 2, I want to check the object next to that one t

  • "paths must precede expression" error when trying to find all jpg files in the current directory 2011-03-14

    while running find command to find all the jpg files in the current directory as find . -maxdepth 1 -type f -name *.jpg i am getting the error as : find: paths must precede expression: pic1 (1).jpg Usage: find [-H] [-L] [-P] [-Olevel] [-Dhelp|tree|se

  • How do you compare multiple folders with same files to find all different versions of the same file? 2010-06-17

    I've got 700+ folders with the same set of 200+ classic asp files (basically text files) in each folder. Over the years various people have made minor changes inside these asp files. I need an utility (for Windows) which can compare all the folders a

  • Find all points that have the same minimum? 2012-09-16

    Possible Duplicate: How to find all the local minima/maxima in a range Sin[x] have two points ($3\pi/2,7\pi/2$) where the same minimum ($-1$) is achieved at the range from $0$ to 4 $\pi$. I don't know how to get two points at once, if using Minimize,

  • View/Find all compressed files on the server? 2012-11-27

    I need to find all compressed files/folders regardless of file format on a Windows Server 2003 machine. Search options do not provide this capability. Is there a way to list/view all compressed files? Perhaps, this can be done by PowerShell using fil

  • Find all web servers in the repository 2014-01-03

    I need to find all the web servers available from the repository for an ARM-based Debian appliance. I ran the following, but it returns too many hits (including libraries, etc.): apt-get update apt-cache search http server Is there a better command t

  • Finding all .cpp files in the users home directory 2014-10-01

    How we will find more accurately all .cpp files in the users home directory that were modified no more than 5 minutes ago? --------------Solutions------------- find can select files on various time conditions: find ~ -type f -name '*.cpp' -mmin -5 -l

  • How to find all JPG files on the file system when .jpg extension is not obligatory ? 2015-03-25

    This question already has an answer here: How to list only JPEG files from root below using the command line? 2 answers First thing I noticed when switched from Windows to Linux was, that Linux has no strict naming convention and no obligatory file n

  • Finding all employees that have the first name of James in sqlite? 2016-01-14

    I'm still learning sqlite. How do I find all employees in a table that has the first name of James? SELECT * FROM employees WHERE name ? --------------Solutions------------- SELECT * FROM employees WHERE name like 'James %'

  • Finding all other workstations on the network 2012-05-22

    at my home I have both workstations directly use Ethernet cables to connect to router, and also a few laptops/mobile devices that connect to wifi. Is there a command in linux to see list of all devices accessing wifi/network? Thanks in advance, sorry

  • Find all files that occupy the sector range on NTFS 2015-11-09

    How can all files that occupy the sector range (not particular sector) be found on NTFS? The solution I'm using now is to process the sectors in batch with Micrisoft nfi. And it doesn't suit me, the estimated duration is 10 days for quite small range

  • Find all unambiguous prefixes of a set of strings 2014-05-20

    For this challenge, you must implement Ruby's Abbrev module in as little code as possible. Challenge The input will be whatever your language has as an array (array, list, sequence, etc.) of strings. You may write a function, or you may accept comma-

  • Finding all possible combinations of data set 2015-02-21

    I know I have seen other variations of this question, however I do not think any of them seem to handle my unique case. I have a database table that will be queried monthly, currently at 88,000 rows (approx.), this table needs to find all possible co

  • How to find all jpeg images of the same camera model 2013-03-16

    Recently during a installation messup , I lost all my files from my windows NTFS drives. I installed on testdata on Ubuntu 12.10 Desktop edition and with the help of photorec could recover a lot of jpeg images. Now the problem is they are all named w

  • Finding all large files in the root filesystem 2014-07-02

    I have a linux server, which currently has below space usage: /dev/sda3 20G 15G 4.2G 78% / /dev/sda6 68G 42G 23G 65% /u01 /dev/sda2 30G 7.4G 21G 27% /opt /dev/sda1 99M 19M 76M 20% /boot tmpfs 48G 8.2G 39G 18% /dev/shm As you can see. / is at 78%. I w

  • How to find what processes run by the user right now? 2015-11-26

    Once again, I'm a beginner and I can't find the right command. I want to view the processes that I'm currently running. --------------Solutions------------- ps has -U and -u options for that. From man ps: -U userlist Select by real user ID (RUID) or

  • Calculating the mode of a set of ints 2012-09-06

    I have to read in a file full of ints, print them in reverse order, and then calculate the median and the mode of the set. At first I struggled with figure out a way to calculate the mode. It seemed so simple but I just couldn't translate the steps i

  • sniff mobile application to find whether packages sent to the third person 2015-01-10

    I suspect that my messages via Viber are being sent to another person - because to my mobile have access a lot of people and it could be possible that somebody installed there some software or configured it somehow to send my messages to another pers

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 6.758 (s). 13 q(s)