按照相等性分组对象

Question

我有一组对象，我想使用以下方法进行相等性比较：

bool AreEqual(MyObject O1, MyObject O2);

最节约性能的分组所有相等对象的方法是什么？显然，每个对象都与集合中所有其他对象进行比较是一个可行方案，但这会影响性能（我相信是N ^ N）。

LINQ的“group by”运算符是否能提供解决方案？

编辑：

由于我不能修改其实现（也没有实现IComparable），因此我可能会使用ICR的解决方案。

- Opflash

Answer 1

你不需要将每个对象与每个其他对象进行比较，你需要将每个对象与每个组（例如组中的第一个项目）进行比较，并在它不匹配任何组（或者是第一个项目）时创建新的组。

可能看起来像这样：

public static IEnumerable<IEnumerable<T>> Group<T>(IEnumerable<T> items)
    where T : IEquatable<T>
{
    IList<IList<T>> groups = new List<IList<T>>();

    foreach (T t in items)
    {
        bool foundGroup = false;

        foreach (IList<T> group in groups)
        {
            Debug.Assert(group.Count() >= 1);
            if (group[0].Equals(t))
            {
                group.Add(t);
                foundGroup = true;
                break;
            }
        }

        if (!foundGroup)
        {
            IList<T> newGroup = new List<T>() { t };
            groups.Add(newGroup);
        }
    }

    foreach (IList<T> group in groups)
    {
        yield return group;
    }
}

当然，在Linq中已经为您完成了此操作，人们已经概述了如何使用它。我只是想证明相比将每个项目与每个项目进行比较，这种算法可能会更好一些。

N.B.此算法依赖于等式关系是可传递的假设-即如果a等于b，并且b等于c，则a等于c。虽然我不太确定如何对非传递性项目进行分组。

- ICR

---

谢谢您提供的样本。在您的许可下，我想在我的项目中使用它。 最后几行尤其有趣。相比于简单的“return groups;”，最后的循环有什么好处？ - Opflash

就像我说的那样，我仍然建议使用LINQ解决方案。它基本上做的是相同的事情，但已经为您编写好了。我提供示例的原因是让您看到这样的算法可能如何工作。最后几行的目的是因为我喜欢返回最通用的适用类型--在这种情况下是IEnumerable。但是，为了构造它们，您需要使用IList来使用Add方法。C#目前无法计算出如何将IEnumerable<IList<T>>转换为IEnumerable<IEnumerable<T>>，因此您需要手动生成每个组。好处是它可以编译 :) - ICR

这个实现真的不太好，因为它是O(n^2)的。请使用现有的GroupBy Linq扩展方法。 - ErikE

Answer 2

我建议为MyObject类使用IComparable接口，然后尝试对其进行分组，例如像这里这里或这里所做的那样。

- Gacek

Answer 3

您可以使用 IEqualityComparer 如果您计划使用LINQ。这里是一个使用IComparer和IEqualityComparer的示例。

我建议使用LINQ来比较所有元素。如果您想获取不同对象的列表，我会用以下伪代码实现：

1. 实现IEqualityComparer，例如ObjectEqualityComparer 实现 IEqualityComparer
2. var result = sourceList.Distinct(一个ObjectEqualityComparer实例)

- ram