UPDATE
Вы можете сделать простой трюк - сгруппировать префиксы по их первым цифрам в словаре и сопоставлять числа только с правильным подмножеством. Я проверил это с помощью следующих двух операторов LINQ, предполагая, что каждый префикс имеет по крайней мере три цифры.
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();
Так как быстро это? 15.000 префиксов и 50.000 номеров заняли менее 250 миллисекунд. Достаточно ли быстро для двух строк кода?
Обратите внимание, что производительность сильно зависит от минимальной длины префикса (MPL), следовательно, от количества групп префиксов, которые вы можете построить.
MPL Runtime
-----------------
1 10.198 ms
2 1.179 ms
3 205 ms
4 130 ms
5 107 ms
Просто чтобы дать общее представление - я сделал всего один прогон, и у меня много других вещей.
Оригинальный ответ
Я бы не заботился о производительности - обычный настольный ПК может спокойно работать с таблицами базы данных со 100 миллионами строк. Возможно, это займет пять минут, но я предполагаю, что вы не хотите выполнять задачу каждую секунду.
Я только что сделал тест. Я создал список с 15.000 уникальных префиксов с 5-10 цифрами. Из этих префиксов я сгенерировал 50.000 номеров с префиксом и дополнительными 5-10 цифрами.
List<String> prefixes = GeneratePrefixes();
List<String> numbers = GenerateNumbers(prefixes);
Затем я использовал следующий запрос LINQ to Object, чтобы найти префикс каждого числа.
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
Ну, это заняло около минуты на моем ноутбуке Core 2 Duo с 2,0 ГГц. Поэтому, если приемлемо время обработки в одну минуту, может быть, две или три, если вы включите агрегацию, я бы не стал ничего оптимизировать. Конечно, было бы очень хорошо, если бы программа могла выполнить задачу за секунду или две, но это добавит немного сложности и многих вещей, которые могут ошибиться. И на разработку, написание и тестирование уходит время. Оператор LINQ занял у меня всего несколько секунд.
Тестовое приложение
Обратите внимание, что генерация многих префиксов очень медленная и может занять минуту или две.
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; }
}
}
}