アップデート
簡単なトリックを行うことができます-プレフィックスを最初の数字で辞書にグループ化し、正しいサブセットに対してのみ番号を照合します。すべてのプレフィックスに少なくとも3つのデジがあると仮定して、次の2つの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ミリ秒未満かかりました。2行のコードに十分な速さですか？
パフォーマンスは最小プレフィックス長（MPL）に大きく依存するため、作成できるプレフィックスグループの数に大きく依存することに注意してください。
MPLランタイム
-----------------
110.198ミリ秒
21.179ミリ秒
3205ミリ秒
4130ミリ秒
5107ミリ秒
大まかなアイデアを与えるために-私はたった1回の実行を行い、他の多くのことを行っています。
元の回答
パフォーマンスについてはあまり気にしません。平均的なデスクトップPCは、1億行のデータベーステーブルを簡単に処理できます。たぶん5分かかりますが、1秒おきにタスクを実行したくないと思います。
テストをしました。5〜10桁の15.000の一意のプレフィックスを持つリストを生成しました。この接頭辞から、接頭辞と追加の5〜10桁の50.000の数字を生成しました。
List<String> prefixes = GeneratePrefixes();
List<String> numbers = GenerateNumbers(prefixes);
次に、次のLINQ to Objectクエリを使用して、各番号のプレフィックスを見つけました。
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
ええと、2.0GHzのCore2Duoラップトップでは約1分かかりました。したがって、1分の処理時間が許容できる場合、集約を含める場合は2、3分程度である場合、私は何も最適化しようとはしません。もちろん、プログラムが1、2秒でタスクを実行できれば本当に素晴らしいのですが、これによりかなり複雑になり、多くの間違いが発生します。また、設計、作成、テストには時間がかかります。LINQステートメントは私のほんの数秒しかかかりませんでした。
テストアプリケーション
多くのプレフィックスの生成は非常に遅く、1〜2分かかる場合があることに注意してください。
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; }
}
}
}