使用 C# 多次比较 2 个巨大的列表（有一些变化）
https://stackoverflow.com/questions/1046278
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
大家好，这里的社区很棒。我是一名电气工程师，兼职做一些“编程”工作以帮助支付账单。我这样说是因为我希望您考虑到我没有接受过适当的计算机科学培训，但过去 7 年我一直在编码。
我有几个包含信息（全是数字）的 Excel 表格，基本上一列是“拨打的电话号码”，另一列是每个号码的分钟数。另外，我有一个我所在国家/地区不同运营商的“运营商前缀代码号码”列表。我想要做的是将每个运营商的所有“流量”分开。这是场景：
第一个拨打的号码行: 123456789ABCD,100 <-- 这将是一个 13 位电话号码和 100 分钟。
我有一个运营商 1 的 12,000 多个前缀代码的列表，这些代码的长度各不相同，我需要检查每个代码：
前缀代码 1: 1234567 <-- 此代码长度为 7 位。
我需要检查拨打号码的前 7 位数字，并将其与拨打的号码进行比较，如果发现匹配，我会将分钟数添加到小计中以供以后使用。 请注意，并非所有前缀代码的长度都相同，有时它们会更短或更长。
其中大部分应该是小菜一碟，我应该能够做到，但我对大量数据感到有点害怕；有时，拨打的号码列表包含多达 30,000 个号码，而“运营商前缀代码”列表长度约为 13,000 行，而我通常会检查 3 个运营商，这意味着我必须进行大量“匹配”。
有谁知道如何使用 C# 有效地做到这一点？或者说实话，任何其他语言。我需要经常这样做，设计一个工具来做到这一点会更有意义。我需要来自具有“计算机科学家”背景的人的良好观点。
列表不需要位于 Excel 工作表中，我可以导出到 csv 文件并从那里工作，我不需要“MS Office”界面。
感谢您的帮助。
更新：
感谢大家抽出时间回答我的问题。我想由于我的无知，我过度夸大了“高效”这个词。我不会每隔几秒钟执行一次此任务。这是我每天必须做一次的事情，我讨厌用 Excel 和 VLOOKUP 等来做。
我从你们那里学到了新概念，我希望我可以利用你们的想法构建一个解决方案。
解决方案
<强>更新
您可以做一个简单的一招 - 按他们的第一个数字的前缀变成字典和仅针对正确的子集相匹配的数字。我具有以下两个LINQ语句假设每前缀测试它具有至少三个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();
因此，如何快速这是什么？的 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
只给一个粗略的想法 - 我只是做了一个运行，并有很多其他的东西怎么回事
<强>原始应答
我不会在意性能 - 平均桌面PC能Quiete酒店轻松应对100万行的数据库表。也许它需要5分钟，但我猜你不想执行的任务每隔一秒。
我只是做了测试。我生成具有15.000用5至10位唯一的前缀列表。从该前缀我生成50.000号码以前缀和额外的5至10位。
List<String> prefixes = GeneratePrefixes();
List<String> numbers = GenerateNumbers(prefixes);
然后我用以下LINQ到对象查询，以找到每个号码的前缀。
var numberPrefixes = numbers.Select(n => prefixes.First(n.StartsWith)).ToList();
好了，花了关于我的酷睿2笔记本电脑一分钟以2.0 GHz的。因此，如果在一分钟的处理时间是可以接受的，也许两个或三个，如果你有聚集，我不会尝试优化任何事情。当然，这将是真的很好，如果PROGRAMM可以做在一两秒钟的任务，但是这会增加相当多的复杂性，很多事情得到错误的。这需要时间来设计，编写和测试。在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; }
}
}
}
其他提示
像你需要从承运人前缀建立一个特里这听起来我。你会用一个单一的线索，其中终端节点告诉你承运人前缀结束了。
然后创建从载体字典到int或long（总）。
然后，每拨的号码排，只是你的工作方式下线索，直到找到载体。找到分钟的总数迄今为载体，并添加当前行 - 然后移动
，最简单的数据结构，将做到这相当有效地将是集列表。制定一套针对每个载波以包含所有前缀。
现在，到带有载体的呼叫相关联：
foreach (Carrier carrier in carriers)
{
bool found = false;
for (int length = 1; length <= 7; length++)
{
int prefix = ExtractDigits(callNumber, length);
if (carrier.Prefixes.Contains(prefix))
{
carrier.Calls.Add(callNumber);
found = true;
break;
}
}
if (found)
break;
}
如果你有10个运营商，都会有每次通话设置70个查找。但是，在一组查找是不是太慢（比线性搜索更快）。因此，这应该给你一个相当大的加速比强力线性搜索。
可以更进一步和组根据长度为每个载波的前缀。这样，如果一个载体具有长度为7和4的唯一前缀，你知道仅打扰提取和查找那些长度，每次在该组该长度的前缀的寻找。
谈谈你的数据卸入一对夫妇的数据库表，然后使用SQL查询呢？简单！
CREATE TABLE dbo.dialled_numbers ( number VARCHAR(100), minutes INT )
CREATE TABLE dbo.prefixes ( prefix VARCHAR(100) )
-- now populate the tables, create indexes etc
-- and then just run your query...
SELECT p.prefix,
SUM(n.minutes) AS total_minutes
FROM dbo.dialled_numbers AS n
INNER JOIN dbo.prefixes AS p
ON n.number LIKE p.prefix + '%'
GROUP BY p.prefix
（这是为SQL Server编写的，但应该是很简单的翻译为任何其他DBMS。）的
也许会更简单（不一定更有效）做在一个数据库中，而不是C＃。
您可以在数据库上插入的行和上插入件确定载体并将其包括在该记录（也许在刀片触发）。
然后您的报告将是对表和查询。
您可能想使用 哈希表 在 C# 中。
这样你就有了键值对，你的键可以是电话号码，你的值可以是总分钟数。如果在密钥集中找到匹配项，则修改总分钟数，否则添加新密钥。
然后，您只需要修改搜索算法，不要查看整个密钥，而只查看它的前 7 位数字。
