c# - 识别字符串集合中对的最快算法

Question

我正在寻找最快的算法:

目标:输出一行中出现的对的总数。各个元素可以在任何给定行上以任何顺序排列。

输入:

a;b;c;d
a;e;f;g
a;b;f;h

输出

a;b = 2
a;c = 1
a;d = 1
a;e = 1
a;f = 2
a;g = 1
b;c = 1
b;d = 1

我在 C# 中编程，我有一个嵌套的 for 循环添加做一个常见类型的字典，其中字符串类似于 a;b，当发现一个事件时，它添加到现有的 int tally 或添加一个新的计数 = 0。

注意这点:

a;b = 1
b;a = 1

应该简化为:

a;b = 1

我愿意使用其他语言，输出是一个纯文本文件，我将其输入 Gephi 可视化工具。

奖励:非常有兴趣知道这个特定算法的名称(如果有的话)。很确定是的。

String[] data = File.ReadAllLines(@"C:\input.txt");
Dictionary<string, int> ress = new Dictionary<string, int>();

foreach (var line in data)
{
    string[] outStrings = line.Split(';');

    for (int i = 0; i < outStrings.Count(); i++)
    {
        for (int y = 0; y < outStrings.Count(); y++)
        {
            if (outStrings[i] != outStrings[y])
            {
                try
                {
                    if (ress.Any(x => x.Key == outStrings[i] + ";" + outStrings[y]))
                    {
                        ress[outStrings[i] + ";" + outStrings[y]] += 1;
                    }
                    else
                    {
                        ress.Add(outStrings[i] + ";" + outStrings[y], 0);
                    }
                }
                catch (Exception)
                {

                }
            }
        }
    }
}

foreach (var val in ress)
{
    Console.WriteLine(val.Key + "----" + val.Value);
}

Answer 1

我认为你的内部循环应该从 i + 1 开始，而不是再次从 0 开始，并且外部循环应该只运行到 Length - 1 ，因为最后一项将在内循环中进行比较。此外，当您添加新项目时，您应该添加值 1，而不是 0(因为我们添加它的全部原因是因为我们找到了一个)。

您还可以只将键存储到字符串中一次，而不是在比较和分配期间进行多次连接，并且您可以使用 ContainsKey 方法来确定键是否已经存在。

此外，您可能需要考虑避免使用空的 catch block ，除非您真的确定您不关心是否出了问题或出了什么问题。如果我预期会出现异常并且知道如何处理它，那么我会捕获该异常，否则我只会让它在堆栈中冒泡。

这是一种修改代码以查找所有对及其计数的方法:

更新

我添加了一个检查以确保“pair”键始终排序，以便“b;a”变为“a;b”。这在您的示例数据中不是问题，但我扩展了数据以包含像 b;a;a;b;a;b;a; 这样的行。我还向 Split 方法添加了 StringSplitOptions.RemoveEmptyEntries 来处理行以 ; 开头或结尾的情况(否则空值导致一对像 ";a").

private static void Main()
{
    var data = File.ReadAllLines(@"f:\public\temp\temp.txt");
    var pairCount = new Dictionary<string, int>();

    foreach (var line in data)
    {
        var lineItems = line.Split(new[] {';'}, StringSplitOptions.RemoveEmptyEntries);

        for (var outer = 0; outer < lineItems.Length - 1; outer++)
        {
            for (var inner = outer + 1; inner < lineItems.Length; inner++)
            {
                var outerComparedToInner = string.Compare(lineItems[outer], 
                    lineItems[inner], StringComparison.Ordinal);

                // If both items are the same character, ignore them and keep looping
                if (outerComparedToInner == 0) continue;

                // Create the pair such that the lower of the two 
                // values is first, so that "b;a" becomes "a;b"
                var thisPair = outerComparedToInner < 0
                    ? $"{lineItems[outer]};{lineItems[inner]}"
                    : $"{lineItems[inner]};{lineItems[outer]}";

                if (pairCount.ContainsKey(thisPair))
                {
                    pairCount[thisPair]++;
                }
                else
                {
                    pairCount.Add(thisPair, 1);
                }
            }
        }
    }

    Console.WriteLine("Pair\tCount\n----\t-----");

    foreach (var val in pairCount.OrderBy(i => i.Key))
    {
        Console.WriteLine($"{val.Key}\t{val.Value}");
    }

    Console.Write("\nDone!\nPress any key to exit...");
    Console.ReadKey();

}

输出

给定一个包含样本数据的文件，输出为: