我有一组对象,我想使用如下所示的方法比较它们的相等性:

bool AreEqual(MyObject O1, MyObject O2);

对所有相同对象进行分组的最性能友好的方式是什么?显而易见的答案是将每个对象与集合中的所有其他对象进行比较,但这反而会损害性能(N ^ N,我相信)。

LINQ group by operator 能否提供解决方案?

编辑:

我也许应该将 MyObject 命名为 YourObject,因为我无法修改它的实现(并且它没有实现 IComparable)。这意味着我可能会使用 ICR 的解决方案。

最佳答案

您不需要将每个对象与每个其他对象进行比较,您需要将每个对象与每个组(例如组中的第一个项目)进行比较,如果不匹配任何对象(或者如果它是第一个),则创建一个新组物品)。

可能看起来像:

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 中为您完成,人们在上面概述了如何使用。我只是想证明该算法可以比将每个项目与每个项目进行比较要好一点。

注意该算法依赖于相等关系是可传递的假设——即如果 a 等于 b,并且 b 等于 c,则 a 等于 c。尽管我不太确定您将如何对非传递项进行分组。

关于c# - 按相等分组对象,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/1855462/

10-17 02:44