高效的C#对象相等比较

Question

高效的C#对象相等比较

5

我正在尝试提高以下（示例）代码的性能。

Object[] inputKeys = new Object[10];
inputKeys[0] = "4021";
inputKeys[1] = "3011";
inputKeys[2] = "1010";
inputKeys[3] = "1020";
inputKeys[4] = "1030";

然后将输入的键进行比较。

for (int i = 0; i < 5; i++)
{
    for (int j = 0; j < 5; j++)
    {
        bool result = inputKeys[i].Equals(inputKeys[j]);
    }
}

可以是 string、int32 或 DateTime 类型。

当 .Equals 行执行数百万次时，性能会急剧下降。 有什么建议可以改进此行的性能（相等检查）吗？ 我已经尝试过这样做：使用下面的类数组而不是对象数组来保存键。在那里，我保留了键类型和键值。

public class CustomKey : IEquatable<CustomKey>{
    internal int KeyType { get; private set; }

    internal string ValueString { get; private set; }
    internal int ValueInteger { get; private set; }
    internal DateTime ValueDateTime { get; private set; }

    internal CustomKey(string keyValue)
    {
        this.KeyType = 0;
        this.ValueString = (string)keyValue;
    }

    internal CustomKey(int keyValue)
    {
        this.KeyType = 1;
        this.ValueInteger = (int)keyValue;
    }

    internal CustomKey(DateTime keyValue)
    {
        this.KeyType = 2;
        this.ValueDateTime = (DateTime)keyValue;
    }

    public bool Equals(CustomKey other)
    {
        if (this.KeyType != other.KeyType)
        {
            return false;
        }
        else
        {
            if (this.KeyType == 0)
            {
                return this.ValueString.Equals(other.ValueString);
            }
            else if (this.KeyType == 1)
            {
                return this.ValueInteger.Equals(other.ValueInteger);
            }
            else if (this.KeyType == 2)
            {
                return this.ValueDateTime.Equals(other.ValueDateTime);
            }
            else
            {
                return false;
            }
        }
    }
}

但性能更差了。

- Gayan Dasanayake

3

你的问题在于算法本身。你正在将每个项目与其他所有项目进行比较，这需要二次时间。如果你需要比较数百万个项目，那么你应该找到更好的方法来实现。一种选项（不一定是最佳的）是按类型划分数据，然后对其进行排序；这将使比较变得简单，并且只需要n log n的时间。 - Thom Smith

你预计会有多少个不同的值？如果您预计有数百万个项目，但只有数万个不同的值，则简单的哈希表可能已经足够。 - Thom Smith

3

无法回答。最好的方法是尽量减少等号的使用频率。当它更频繁地出现时，它绝对不会变慢 - 我相信等号调用需要相同的时间。基本用法似乎选择不当（例如：首先检查哈希码，或者对列表进行排序以减少等价调用等等）。这些是50多年来“广为人知”的技术（索引、数据库）。最后，问题不在于equals的时间，而在于你调用它的次数非常多 - 算法效率低下。 - TomTom

@TomTom是正确的。不要浪费时间重写Equals。.Net Equals已经处理了不同类型的比较。你的版本只是多做了一次这个工作。相反，集中精力于Equals周围的代码。 - hatchet - done with SOverflow

5个回答

2

作为算法效率的一个例子，您的第一段代码可以重写。

for (int i = 0; i < 5; i++)
{
    for (int j = i; j < 5; j++)
    {
        bool result = inputKeys[i].Equals(inputKeys[j]);
    }
}

因为 x.Equals(y) 和 y.Equals(x) 的结果相同，所以你不需要检查两种方式。

新的 Equals 实现应该遵循以下保证：

x.Equals(y) 返回的值应该和 y.Equals(x) 相同。 http://msdn.microsoft.com/en-us/library/ms173147(v=vs.80).aspx

- hatchet - done with SOverflow

不错的观察，值得注意的是将j初始化为i+1将节省O(n)个查询。 - Thom Smith

1

如评论所述，您的算法的主要负担是必须将所有内容与所有内容进行比较，这会降低性能。对于100K个元素，这意味着100k ^ 2 ...或约10K万个组合...您可以看到问题出在哪里。最好的选择是修改算法，但是如果您仍然决心不改变或没有其他选择，请考虑以下方法：

首先分割您的对象，然后再进行比较：

例如：如果您有100K个等量分布的对象，则会有33K个整数、33K个字符串和33K个日期时间，您可以将它们彼此比较并忽略它们之间的组合。

100K ^ 2 = 10K万

（30K ^ 2）* 3 = 27亿组合+ 100K以将每个元素排序在其列表中

扩展您的组

如果您不太关心内存，可以将结果哈希以进一步细化您的组。基本上构建一个网格...这非常具体，取决于您的问题。

这背后的想法是隔离那些实际上不能相等的东西，这是前一个想法的扩展，但使用更多的组，组越小，性能越快。

这样你就可以有10个组：

长度小于5个字符的字符串
长度在5到50个字符之间的字符串
长度超过50个字符的字符串

等等...

如果您重新计算一下（同样是为了均匀分布的样本）

总迭代次数= 10K ^ 2 * 10 + 100K〜1亿次迭代（10个组+组成这些组的价格）

实际复杂度=（n / m）^ 2 * m + n（其中n =元素数量，m =组数量，假设分布均匀。

- Jorge Córdoba

0

尝试获取每个对象的哈希码并使用object.GetHashCode()进行比较。不确定调用GetHashCode()数百万次的开销，但是比较两个整数可能比Equals(object)方法快得多。

- Robert Rouhani

0

使用哈希表（或更好的字典）来存储你的项目。你的方法的时间复杂度为O(N^2)，但是通过使用哈希表，可以将运行时间复杂度降低到O(N)，其中N是数量。

为了实现这一点，使用哈希键创建哈希表，如果发生冲突，则将项目添加到链接列表中。只需要检查同一桶中的对象是否相等即可，这不应该太多。

我希望这很清楚并且有帮助。

- Khalefa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- e_ne · Accepted Answer

您的比较循环效率较低。我建议您尝试使用以下方法：

Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)

为该类型定义您的IEqualityComparer，并将其传递给该方法。您不会得到一个bool值，但是您将获得一个包含该列表且无重复项的IEnumerable。