使用 C# 多次比较 2 个巨大的列表（有一些变化）

Question

大家好，这里的社区很棒。 我是一名电气工程师，兼职做一些“编程”工作以帮助支付账单。 我这样说是因为我希望您考虑到我没有接受过适当的计算机科学培训，但过去 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 等。

我从你们那里学到了新概念，我希望我可以使用你们的想法构建一个解决方案。

Answer 1

在我看来，您需要从运营商前缀构建 trie 。 您最终将得到一个特里树，其中终止节点告诉您该前缀的运营商。

然后创建一个从载体到int或long（总计）的字典。

然后，对于每个拨打的号码行，只需沿着字典树向下查找，直到找到运营商。 查找运营商迄今为止的总分钟数，并添加当前行 - 然后继续。

Answer 2

能够相当有效地完成此操作的最简单的数据结构是集合列表。 为每个运营商创建一个集合以包含所有前缀。

现在，要将呼叫与运营商关联起来：

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 的前缀，您就会知道只需提取并查找这些长度，每次查找该长度的前缀集。

Answer 3

将数据转储到几个数据库表中，然后使用 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 应该非常简单。）

Answer 4

也许在数据库中而不是在 C# 中执行此操作会更简单（不一定更有效）。

您可以在数据库中插入行，并在插入时确定运营商并将其包含在记录中（可能在插入触发器中）。

那么你的报告将是表上的求和查询。

Answer 5

我可能只是将条目放入列表中，对其进行排序，然后使用 二进制搜索 来寻找匹配项。 定制二分搜索匹配条件以返回第一个匹配的项目，然后沿列表迭代，直到找到不匹配的项目。 二分搜索只需大约 15 次比较即可搜索包含 30,000 个项目的列表。

Answer 6

您可能需要使用 C# 中的哈希表。

这样你就有了键值对，你的键可以是电话号码，你的值可以是总分钟数。 如果在密钥集中找到匹配项，则修改总分钟数，否则添加新密钥。

然后，您只需要修改搜索算法，不要查看整个密钥，而只查看它的前 7 位数字。

Answer 7

更新

您可以使用一个简单的技巧 - 按前缀的第一个数字将前缀分组到字典中，然后仅将数字与正确的子集进行匹配。 我使用以下两个 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

只是为了提供一个粗略的想法 - 我只跑了一次，还有很多其他事情正在进行。

原始答案

我不太关心性能 - 一台普通的台式电脑可以轻松地处理具有 1 亿行的数据库表。 也许需要五分钟，但我假设您不想每隔一秒执行一次任务。

我刚刚做了一个测试。 我生成了一个包含 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();

好吧，在我的 2.0 GHz Core 2 Duo 笔记本电脑上大约需要一分钟。 因此，如果一分钟的处理时间是可以接受的，如果包括聚合，则可能是两分钟或三分钟，我不会尝试优化任何内容。 当然，如果程序能够在一两秒内完成任务，那就太好了，但这会增加相当多的复杂性，并且会导致很多错误。 设计、编写和测试需要时间。 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; }
        }
    }
}