测试两个IEnumerable <T>是否具有相同频率的相同值

Question

我有两个多字节,都是IEnumerables,我想比较它们.

string[] names1 = { "tom", "dick", "harry" };
string[] names2 = { "tom", "dick", "harry", "harry"};
string[] names3 = { "tom", "dick", "harry", "sally" };
string[] names4 = { "dick", "harry", "tom" };

希望names1 == names4返回true(并且self == self显然返回true)
但是所有其他组合都返回false.

什么是最有效的方式？这些可以是大量复杂对象.

我看着做:
var a = name1.orderby<MyCustomType, string>(v => v.Name);
var b = name4.orderby<MyCustomType, string>(v => v.Name);

return a == b;

Answer 1

首先按照您已经完成的排序,然后使用Enumerable.SequenceEqual.如果您的类型实现IEquatable<MyCustomType>或覆盖Equals,您可以使用第一个重载; 否则你将不得不使用第二个表格并提供自己的表格IEqualityComparer<MyCustomType>.

因此,如果您的类型确实实现了相等,那么只需:

return a.SequenceEqual(b);

这是另一个更快,更安全,无需排序的选项:

public static bool UnsortedSequencesEqual<T>(
    this IEnumerable<T> first,
    IEnumerable<T> second)
{
    return UnsortedSequencesEqual(first, second, null);
}

public static bool UnsortedSequencesEqual<T>(
    this IEnumerable<T> first,
    IEnumerable<T> second,
    IEqualityComparer<T> comparer)
{
    if (first == null)
        throw new ArgumentNullException("first");

    if (second == null)
        throw new ArgumentNullException("second");

    var counts = new Dictionary<T, int>(comparer);

    foreach (var i in first) {
        int c;
        if (counts.TryGetValue(i, out c))
            counts[i] = c + 1;
        else
            counts[i] = 1;
    }

    foreach (var i in second) {
        int c;
        if (!counts.TryGetValue(i, out c))
            return false;

        if (c == 1)
            counts.Remove(i);
        else
            counts[i] = c - 1;
    }

    return counts.Count == 0;
}

Answer 2

最有效的方法取决于数据类型.一个非常短的合理有效的O(N)解决方案如下:

var list1Groups=list1.ToLookup(i=>i);
var list2Groups=list2.ToLookup(i=>i);
return list1Groups.Count == list2Groups.Count 
   && list1Groups.All(g => g.Count() == list2Groups[g.Key].Count());

这些项目必须具有有效Equals和GetHashcode实施.

如果你想要一个更快的解决方案,下面的cdhowie的解决方案是相对快的@ 10000元素,并且对于大型简单对象集合而言提前5倍 - 可能是由于更好的内存效率.

最后,如果你真的对性能感兴趣,我肯定会尝试 Sort-then-SequenceEqual方法.虽然它的复杂性更差,但这只是一个log N因素,并且绝对可以通过所有实际数据集大小的常量差异来淹没 - 并且您可能能够就地排序,使用数组甚至递增排序(可以是线性的).即使是40亿个元素,log-base-2也只有32个; 这是一个相关的性能差异,但恒定因子的差异可以想象得更大.例如,如果你正在处理整数数组并且不介意修改集合顺序,那么即使对于10000000个项目,这两个选项的速度也比任何一个选项快(两倍,我在32位上得到一个OutOfMemory):

Array.Sort(list1);
Array.Sort(list2);
return list1.SequenceEqual(list2);

YMMV取决于机器,数据类型,月球周期以及影响微基准测试的其他常见因素.