UPDATE
You can do a simple trick - group the prefixes with your first digits in the dictionary and match numbers only with the correct subset. I tested it with the following two LINQ operations, assuming that each prefix has at least three digis.
const Int32 minimumPrefixLength = 3; var groupedPefixes = prefixes .GroupBy(p => p.Substring(0, minimumPrefixLength)) .ToDictionary(g => g.Key, g => g); var numberPrefixes = numbers .Select(n => groupedPefixes[n.Substring(0, minimumPrefixLength)] .First(n.StartsWith)) .ToList();
So how fast does this happen? 15,000 prefixes and 50,000 numbers took less than 250 milliseconds. fast enough for two lines of code?
Note that performance is highly dependent on the minimum prefix length (MPL), therefore, on the number of prefix groups that you can create.
MPL Runtime
-----------------
1 10.198 ms
2 1.179 ms
3 205 ms
4 130 ms
5 107 ms
Just to give a rough idea - I did just one race and did a lot of things.
Original answer
I would not really like the performance - a regular desktop PC can easily cope with database tables with 100 million rows. It may take five minutes, but I suppose you do not want to complete this task every second.
I just did a test. I created a list with 15,000 unique prefixes with 5-10 digits. From these prefixes, I generated 50,000 numbers with a prefix and another 5 to 10 digits.
List<String> prefixes = GeneratePrefixes(); List<String> numbers = GenerateNumbers(prefixes);
Then I used the following LINQ to Object query to find the prefix of each number.
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
Well, it took about a minute on my 2.0 GHz Core 2 Duo laptop. Therefore, if a one-minute processing time is acceptable, perhaps two or three, if you turn on aggregation, I would not optimize anything. Of course, it would be nice if the program could complete the task in a second or two, but this will add a bit of complexity and a lot to make a mistake. And it takes time to develop, write, and test. The LINQ statement took only my seconds.
test application
Note that generating many prefixes is very slow and can take a minute or two.
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; namespace Test { static class Program { static void Main() { // Set number of prefixes and calls to not more than 50 to get results // printed to the console. Console.Write("Generating prefixes"); List<String> prefixes = Program.GeneratePrefixes(5, 10, 15); Console.WriteLine(); Console.Write("Generating calls"); List<Call> calls = Program.GenerateCalls(prefixes, 5, 10, 50); Console.WriteLine(); Console.WriteLine("Processing started."); Stopwatch stopwatch = new Stopwatch(); const Int32 minimumPrefixLength = 5; stopwatch.Start(); var groupedPefixes = prefixes .GroupBy(p => p.Substring(0, minimumPrefixLength)) .ToDictionary(g => g.Key, g => g); var result = calls .GroupBy(c => groupedPefixes[c.Number.Substring(0, minimumPrefixLength)] .First(c.Number.StartsWith)) .Select(g => new Call(g.Key, g.Sum(i => i.Duration))) .ToList(); stopwatch.Stop(); Console.WriteLine("Processing finished."); Console.WriteLine(stopwatch.Elapsed); if ((prefixes.Count <= 50) && (calls.Count <= 50)) { Console.WriteLine("Prefixes"); foreach (String prefix in prefixes.OrderBy(p => p)) { Console.WriteLine(String.Format(" prefix={0}", prefix)); } Console.WriteLine("Calls"); foreach (Call call in calls.OrderBy(c => c.Number).ThenBy(c => c.Duration)) { Console.WriteLine(String.Format(" number={0} duration={1}", call.Number, call.Duration)); } Console.WriteLine("Result"); foreach (Call call in result.OrderBy(c => c.Number)) { Console.WriteLine(String.Format(" prefix={0} accumulated duration={1}", call.Number, call.Duration)); } } Console.ReadLine(); } private static List<String> GeneratePrefixes(Int32 minimumLength, Int32 maximumLength, Int32 count) { Random random = new Random(); List<String> prefixes = new List<String>(count); StringBuilder stringBuilder = new StringBuilder(maximumLength); while (prefixes.Count < count) { stringBuilder.Length = 0; for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++) { stringBuilder.Append(random.Next(10)); } String prefix = stringBuilder.ToString(); if (prefixes.Count % 1000 == 0) { Console.Write("."); } if (prefixes.All(p => !p.StartsWith(prefix) && !prefix.StartsWith(p))) { prefixes.Add(stringBuilder.ToString()); } } return prefixes; } private static List<Call> GenerateCalls(List<String> prefixes, Int32 minimumLength, Int32 maximumLength, Int32 count) { Random random = new Random(); List<Call> calls = new List<Call>(count); StringBuilder stringBuilder = new StringBuilder(); while (calls.Count < count) { stringBuilder.Length = 0; stringBuilder.Append(prefixes[random.Next(prefixes.Count)]); for (int i = 0; i < random.Next(minimumLength, maximumLength + 1); i++) { stringBuilder.Append(random.Next(10)); } if (calls.Count % 1000 == 0) { Console.Write("."); } calls.Add(new Call(stringBuilder.ToString(), random.Next(1000))); } return calls; } private class Call { public Call (String number, Decimal duration) { this.Number = number; this.Duration = duration; } public String Number { get; private set; } public Decimal Duration { get; private set; } } } }