Faster Way of Comparing Generic Sets

Question

The following extension method is the limiting factor in the performance of an application I am developing, according to Visual Studio 2012 Performance Analysis profiler.

Is there a faster way to compare two collections for set equality?

public static bool SetEqual<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    if (source == null) {
        throw new ArgumentNullException("source");
    }

    if (other == null) {
        throw new ArgumentNullException("other");
    }

    ICollection<T> sourceCollection = source as ICollection<T> ?? source.ToArray();
    ICollection<T> otherCollection = other as ICollection<T> ?? other.ToArray();

    if (sourceCollection.Count != otherCollection.Count) {
        return false;
    }

    if (sourceCollection.Except(otherCollection, comparer).Any()) {
        return false;
    }

    if (otherCollection.Except(sourceCollection, comparer).Any()) {
        return false;
    }

    return true;
}

Answer 1

It seems you are iterating the sets a lot with the Except method and possibly the ToArray.

Consider iterating the sets at most once:

public static bool SetEqual<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    if (source == null)
        throw new ArgumentNullException("source");

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

    if (source is ICollection &&
        other is ICollection &&
        ((ICollection)source).Count != ((ICollection)other).Count)
        return false;

    HashSet<T> set;
    if (comparer == null)
        set = new HashSet<T>(source);
    else
        set = new HashSet<T>(source, comparer);

    return set.SetEquals(other);
}

Source IEnumerable implementation.

Answer 2

I believe the most efficient collection type for this task is a Dictionary. And there are several solutions which are based on the convertion of input enumerations to the dictionaries.
But I came up with an idea that we don't need to create two or more dictionaries for this task, we could use the only dictionary.

The algorithm includes 2 steps:

1. The dictionary is filled with the source elements and with their number of occurences.
2. Number of occurences is decreased for each item in the other collection.

The code:

public static bool SetEqual<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    if (source == null)
    {
        return other == null;
    }

    if (other == null)
    {
        return false;
    }

    int sourceLength = source.Count();
    int otherLength = other.Count();

    if (sourceLength != otherLength)
    {
        return false;
    }

    // Create our dictionary.
    // Keys - 'source' elements.
    // Values - their counts in the 'source'.
    // We could also set the initial capacity
    Dictionary<T, int> counts = comparer == null
        ? new Dictionary<T, int>(sourceLength)
        : new Dictionary<T, int>(sourceLength, comparer);

    // Fill the dictionary with 'source' items and their counts:
    foreach(T item in source)
    {
        int value;
        if (counts.TryGetValue(item, out value))
            counts[item] = value + 1;  // Item already exists? Add 1 to counts.
        else
            counts.Add(item, 1); // Add new item with count = 1.
    }

    // Remove `other` items from the dictionary:
    foreach (T item in other)
    {
        int value;
        if (counts.TryGetValue(item, out value))
        {
            // If the item exists, decrease its count or remove it:
            if (value == 1)  // If the count == 1, remove the item from the dictionary
                counts.Remove(item);
            else  // Decrease its count:
                counts[item] = value - 1;
        }
        else
        {
            // No such item? Collections are not equal.
            return false;
        }
    }

    // Is there any items left in the dictionary?
    // If no, collections are equal.
    return counts.Count == 0;
}

Execution time:

1000 / 1000: 00:00:02.2077380 (Original solution)
1000 / 1000: 00:00:01.7815650 (My solution)

EDIT
Performance optimization of removing.

Execution time for array size = 10000 (link):

20 / 20: 00:00:00.1015607 (Original solution)
20 / 20: 00:00:00.0620284 (My solution)
20 / 20: 00:00:03.7846245 (Heslacher's IList<T> solution)

All tests were passed.

Answer 3

I'm mostly with Heslacher's solution but in don't let to any of the collections to be null and i'm preparing to have null values in the collections. To spare some time i don't bother to create arrays from the input sources too.

I also renamed the extensions method to EquivalentWith because SetEqual means a different thing.

Tests

I have used the provided unit test as base to write my ones so here are they:

[TestClass]
public class EquivalentWithTests
{
    [TestMethod]
    [ExpectedException(typeof(ArgumentNullException))]
    public void BothEnumerableNullWillNotPass()
    {
        IEnumerable<int> source = null;
        IEnumerable<int> other = null;
        source.EquivalentWith(other);
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentNullException))]
    public void SourceEnumerableNullWillNotPass()
    {
        IEnumerable<int> source = null;
        IEnumerable<int> other = new[] { 1, 2, 3, 4, 5, 6 };
        source.EquivalentWith(other);
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentNullException))]
    public void OtherEnumerableNullWillNotPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 3, 4, 5, 6 };
        IEnumerable<int> other = null;
        source.EquivalentWith(other);
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentNullException))]
    public void SameEnumerableNullWillPass()
    {
        IEnumerable<int> source = null;
        source.EquivalentWith(source);
    }

    [TestMethod]
    public void SameEnumerableWillPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 3, 4, 5, 6 };
        Assert.IsTrue(source.EquivalentWith(source));
    }

    [TestMethod]
    public void BothEnumerableSameWillPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 3, 4, 5, 6 };
        IEnumerable<int> other = new[] { 1, 2, 3, 4, 5, 6 };
        Assert.IsTrue(source.EquivalentWith(other));
    }

    [TestMethod]
    public void EnumerableDifferentSizeWillNotPass()
    {
        IEnumerable<int> source = Enumerable.Range(0, 5000);
        IEnumerable<int> other = Enumerable.Range(0, 500);
        Assert.IsFalse(source.EquivalentWith(other));
    }
    [TestMethod]
    public void CollectionsDifferentSizeWillNotPass()
    {
        var source = new List<int>(Enumerable.Range(0, 50));
        var other = new List<int>(Enumerable.Range(0, 40));
        Assert.IsFalse(source.EquivalentWith(other));
    }

    [TestMethod]
    public void BothEnumerableDifferentWillNotPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 3, 4, 5, 6 };
        IEnumerable<int> other = new[] { 3, 4, 5, 6, 7, 8 };
        Assert.IsFalse(source.EquivalentWith(other));
    }

    [TestMethod]
    public void OtherEnumerableReversedWillPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 3, 4, 5, 6 };
        IEnumerable<int> other = new[] { 6, 5, 4, 3, 2, 1 };
        Assert.IsTrue(source.EquivalentWith(other));
    }

    [TestMethod]
    public void OtherEnumerableReversedBothContainingNonUniqueAndUniqueWillPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 2, 4, 5, 6 };
        IEnumerable<int> other = new[] { 6, 5, 4, 2, 2, 1 };
        Assert.IsTrue(source.EquivalentWith(other));
    }

    [TestMethod]
    public void OtherEnumerableReversedBothContainingNonUniqueAndUniqueButDifferentWillPass()
    {
        IEnumerable<int> source = new[] { 1, 2, 2, 4, 5, 6 };
        IEnumerable<int> other = new[] { 6, 5, 4, 4, 2, 1 };

        Assert.IsFalse(source.EquivalentWith(other));
    }


    [TestMethod]
    public void OtherEnumerableReversedBothContainingUniqueAndNullButDifferentWillPass()
    {
        var source = new int?[] { 1, 2, 3, 4, 5, 6, null };
        var other = new int?[] { 6, 5, 4, 3, 2, 1, null };

        Assert.IsTrue(source.EquivalentWith(other));
    }

    [TestMethod]
    public void OtherEnumerableReversedBothContainingUniqueAndNotUniqueAndNullButDifferentWillPass()
    {
        var source = new int?[] { 1, 2, 3, 2, 5, 6, null };
        var other = new int?[] { 6, 5, 2, 3, 2, 1, null };

        Assert.IsTrue(source.EquivalentWith(other));
    }
}

Implementation

public static class CollectionExtensions
{
    public static bool EquivalentWith<T>(this IEnumerable<T> source, IEnumerable<T> other)
    {
        return EquivalentWith(source, other, EqualityComparer<T>.Default);
    }

    public static bool EquivalentWith<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (other == null) throw new ArgumentNullException("other");
        if (comparer == null) throw new ArgumentNullException("comparer");

        if (ReferenceEquals(source, other))
        {
            return true;
        }

        if (CollectionsButNotSameCount(source, other))
        {
            return false;
        }

        int sourceNullCount;
        var sourceDict = GetElementCounts(source, comparer, out sourceNullCount);
        int otherNullCount;
        var otherDict = GetElementCounts(other, comparer, out otherNullCount);

        if (otherNullCount != sourceNullCount || sourceDict.Count != otherDict.Count)
        {
            return false;
        }

        foreach (var s in sourceDict)
        {
            int otherCount;
            if (!otherDict.TryGetValue(s.Key, out otherCount) || s.Value != otherCount)
            {
                return false;
            }
        }

        return true;
    }

    private static bool CollectionsButNotSameCount<T>(IEnumerable<T> source, IEnumerable<T> other)
    {
        var sourceColl = source as ICollection<T>;
        var otherColl = other as ICollection<T>;

        return sourceColl != null && otherColl != null && sourceColl.Count != otherColl.Count;
    }

    private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> source, IEqualityComparer<T> comparer, out int nullCount)
    {
        var asCollection = source as ICollection<T>;

        var dictionary = new Dictionary<T, int>(asCollection == null ? 0 : asCollection.Count, comparer);
        nullCount = 0;
        foreach (var key in source)
        {
            if (key == null)
            {
                ++nullCount;
            }
            else
            {
                int num;
                dictionary.TryGetValue(key, out num);
                ++num;
                dictionary[key] = num;
            }
        }
        return dictionary;
    }
}

First i have provided az overload to avoid unnecessary passinf if the IEqualityComparer and in the method i'm checking against null values.

Then checking their references because if they are the same there is nothing to do. After this i'm using the as operator to check if the input collections are real ICollections and if they are are their Count equal. The casting is fast no need to iterate throught the IEnumerables to get a fixed size collection to get the item counts.

Next step is to get the item counts it is using a Dictionary (as Hashlacher did it) with another casting to try get the initial size of the dictionary (not good idea when we have a list with 5 million items but every item is the same).

If we have the counts we can make another checks against them: if the item counts or the null counts aren't equal then the collections aren't equals.

If the counts are OK then we try to check every item from the source collection whether it is in the other or not. If not the collections aren't equal.

Answer 4

General

If both,source and other, are null they should be equal.

As already stated the implementation did not sucessfully evaluate if two IEnumerable like [1, 1, 2] and [1, 2, 2] will be SetEqual.

So let us start with some tests

[TestMethod()]
public void BothEnumerableNullWillPass()
{
    IEnumerable<int> source = null;
    IEnumerable<int> other = null;
    Assert.IsTrue(source.SetEqual(other));
}

[TestMethod()]
public void SourceEnumerableNullWillPass()
{
    IEnumerable<int> source = null;
    IEnumerable<int> other = new int[] { 1, 2, 3, 4, 5, 6 };
    Assert.IsFalse(source.SetEqual(other));
}

[TestMethod()]
public void OtherEnumerableNullWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 3, 4, 5, 6 };
    IEnumerable<int> other = null;
    Assert.IsFalse(source.SetEqual(other));
}

[TestMethod()]
public void SameEnumerableNullWillPass()
{
    IEnumerable<int> source = null;
    Assert.IsTrue(source.SetEqual(source));
}

[TestMethod()]
public void SameEnumerableWillPass()
{
    IEnumerable<int> source =new int[] { 1, 2, 3, 4, 5, 6 };
    Assert.IsTrue(source.SetEqual(source));
}

[TestMethod()]
public void BothEnumerableSameWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 3, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 1, 2, 3, 4, 5, 6 };
    Assert.IsTrue(source.SetEqual(other));
}

[TestMethod()]
public void EnumerableDifferentSizeWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 3, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 1, 2, 3, 4, 5 };
    Assert.IsFalse(source.SetEqual(other));
}

[TestMethod()]
public void BothEnumerableDifferentWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 3, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 3, 4, 5, 6, 7, 8 };
    Assert.IsFalse(source.SetEqual(other));
}

[TestMethod()]
public void OtherEnumerableReversedWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 3, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 6, 5, 4, 3, 2, 1 };
    Assert.IsTrue(source.SetEqual(other));
}

[TestMethod()]
public void OtherEnumerableReversedBothContainingNonUniqueAndUniqueWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 2, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 6, 5, 4, 2, 2, 1 };
    Assert.IsTrue(source.SetEqual(other));
}

[TestMethod()]
public void OtherEnumerableReversedBothContainingNonUniqueAndUniqueButDifferentWillPass()
{
    IEnumerable<int> source = new int[] { 1, 2, 2, 4, 5, 6 };
    IEnumerable<int> other = new int[] { 6, 5, 4, 4, 2, 1 };
    Assert.IsFalse(source.SetEqual(other));
}  

now we should pass these tests.

As it is possible that both IEnumerable<T> can contain non unique items, we need to ensure that each item which is in the source is also in the other and the number of occurance is the same inside the source and the other IEnumerable<T>.

To accomplish this task, I use a Dictionary<T,int> here.

public static bool SetEqual<T>(this IEnumerable<T> source, IEnumerable<T> other, IEqualityComparer<T> comparer = null)
{
    if (source == null)
    {
        return other == null;
    }

    if (other == null)
    {
        return false;
    }

    T[] sourceArray = source.ToArray();
    T[] otherArray = other.ToArray();

    if (sourceArray.Length != otherArray.Length)
    {
        return false;
    }

    Dictionary<T, int> sourceDict = ToDictionary<T>(sourceArray);

    Dictionary<T, int> otherDict = ToDictionary<T>(otherArray);

    return sourceDict.SetEqual(otherDict);

}

private static Dictionary<T, int> ToDictionary<T>(T[] current, IEqualityComparer<T> comparer = null)
{
    Dictionary<T, int> result = new Dictionary<T, int>(comparer);
    for (int i = 0; i < current.Length; i++)
    {
        int count;
        result.TryGetValue(current[i], out count);
        result[current[i]] = count + 1;

    }
    return result;
}

private static Boolean SetEqual<T>(this Dictionary<T, int> source, Dictionary<T, int> other)
{
    if (source.Count != other.Count)
    {
        return false;
    }

    foreach (KeyValuePair<T, int> kv in source)
    {
        int currentValue;
        if (!(other.TryGetValue(kv.Key, out currentValue)
                && currentValue == kv.Value))
        {
            return false;
        }
    }
    return true;
}  

This implementation is not as fast than the original, but it passes all the tests.

Based on mjolka's test it is about 2 times slower than the original.

1000 / 1000: 00:00:00.1250604 HashSet (Timed on my computer)
1000 / 1000: 00:00:00.2211285 Original (Timed on my computer)
1000 / 1000: 00:00:00.4917692 Dictionary (Timed on my computer)

Update

After reading Dmitry's interresting and fast approach to the problem, I had the idea,why not skipping the Dictionary<T> and use a IList<T> instead.

This had been very slow, as for each call to Remove() the List has been iterated over. I initially did a timing which evaluated to beeing the fastest, but unfortunately I did my timing with an changed version of the test mjolka provided. It is the fastest, but only if both IEnumerable will contain absolutly unique items. Both for the single IEnumerable and each item to the other IEnumerable.

Thanks to @dmitry for pointing this out. If you want to see the implementation, check the edit history.