Comparing two collections for equality irrespective of the order of items in them

I would like to compare two collections (in C#), but I'm not sure of the best way to implement this efficiently.

I've read the other thread about Enumerable.SequenceEqual, but it's not exactly what I'm looking for.

In my case, two collections would be equal if they both contain the same items (no matter the order).

Example:

collection1 = {1, 2, 3, 4}; collection2 = {2, 4, 1, 3}; collection1 == collection2; // true

What I usually do is to loop through each item of one collection and see if it exists in the other collection, then loop through each item of the other collection and see if it exists in the first collection. (I start by comparing the lengths).

if (collection1.Count != collection2.Count) return false; // the collections are not equal foreach (Item item in collection1) { if (!collection2.Contains(item)) return false; // the collections are not equal } foreach (Item item in collection2) { if (!collection1.Contains(item)) return false; // the collections are not equal } return true; // the collections are equal

However, this is not entirely correct, and it's probably not the most efficient way to do compare two collections for equality.

An example I can think of that would be wrong is:

collection1 = {1, 2, 3, 3, 4} collection2 = {1, 2, 2, 3, 4}

Which would be equal with my implementation. Should I just count the number of times each item is found and make sure the counts are equal in both collections?



The examples are in some sort of C# (let's call it pseudo-C#), but give your answer in whatever language you wish, it does not matter.

Note: I used integers in the examples for simplicity, but I want to be able to use reference-type objects too (they do not behave correctly as keys because only the reference of the object is compared, not the content).

-------------Problems Reply------------

It turns out Microsoft already has this covered in its testing framework: CollectionAssert.AreEquivalent

Remarks

Two collections are equivalent if they have the same elements in the same quantity, but in any order. Elements are equal if their values are equal, not if they refer to the same object.

Using reflector, I modified the code behind AreEquivalent() to create a corresponding equality comparer. It is more complete than existing answers, since it takes nulls into account, implements IEqualityComparer and has some efficiency and edge case checks. plus, it's Microsoft :)

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == null)
return second == null;

if (second == null)
return false;

if (ReferenceEquals(first, second))
return true;

var firstCollection = first as ICollection<T>;
var secondCollection = second as ICollection<T>;
if (firstCollection != null && secondCollection != null)
{
if (firstCollection.Count != secondCollection.Count)
return false;

if (firstCollection.Count == 0)
return true;
}

return !HaveMismatchedElement(first, second);
}

private static bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
{
int firstNullCount;
int secondNullCount;

var firstElementCounts = GetElementCounts(first, out firstNullCount);
var secondElementCounts = GetElementCounts(second, out secondNullCount);

if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
return true;

foreach (var kvp in firstElementCounts)
{
var firstElementCount = kvp.Value;
int secondElementCount;
secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);

if (firstElementCount != secondElementCount)
return true;
}

return false;
}

private static Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>();
nullCount = 0;

foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}

return dictionary;
}

public int GetHashCode(IEnumerable<T> enumerable)
{
int hash = 17;

foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();

return hash;
}
}

A simple and fairly efficient solution is to sort both collections and then compare them for equality:

bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));

This algorithm is O(N*logN), while your solution above is O(N^2).

If the collections have certain properties, you may be able to implement a faster solution. For example, if both of your collections are hash sets, they cannot contain duplicates. Also, checking whether a hash set contains some element is very fast. In that case an algorithm similar to yours would likely be fastest.

Create a Dictionary "dict" and then for each member in the first collection, do dict[member]++;

Then, loop over the second collection in the same way, but for each member do dict[member]--.

At the end, loop over all of the members in the dictionary:

private bool SetEqual (List<int> left, List<int> right) {

if (left.Count != right.Count)
return false;

Dictionary<int, int> dict = new Dictionary<int, int>();

foreach (int member in left) {
if (dict.ContainsKey(member) == false)
dict[member] = 1;
else
dict[member]++;
}

foreach (int member in right) {
if (dict.ContainsKey(member) == false)
return false;
else
dict[member]--;
}

foreach (KeyValuePair<int, int> kvp in dict) {
if (kvp.Value != 0)
return false;
}

return true;

}

Edit: As far as I can tell this is on the same order as the most efficient algorithm. This algorithm is O(N), assuming that the Dictionary uses O(1) lookups.

This is my (heavily influenced by D.Jennings) generic implementation of the comparison method (in C#):

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
/// <summary>
/// Compares the content of two collections for equality.
/// </summary>
/// <param name="foo">The first collection.</param>
/// <param name="bar">The second collection.</param>
/// <returns>True if both collections have the same content, false otherwise.</returns>
public bool Execute(ICollection<T> foo, ICollection<T> bar)
{
// Declare a dictionary to count the occurence of the items in the collection
Dictionary<T, int> itemCounts = new Dictionary<T,int>();

// Increase the count for each occurence of the item in the first collection
foreach (T item in foo)
{
if (itemCounts.ContainsKey(item))
{
itemCounts[item]++;
}
else
{
itemCounts[item] = 1;
}
}

// Wrap the keys in a searchable list
List<T> keys = new List<T>(itemCounts.Keys);

// Decrease the count for each occurence of the item in the second collection
foreach (T item in bar)
{
// Try to find a key for the item
// The keys of a dictionary are compared by reference, so we have to
// find the original key that is equivalent to the "item"
// You may want to override ".Equals" to define what it means for
// two "T" objects to be equal
T key = keys.Find(
delegate(T listKey)
{
return listKey.Equals(item);
});

// Check if a key was found
if(key != null)
{
itemCounts[key]--;
}
else
{
// There was no occurence of this item in the first collection, thus the collections are not equal
return false;
}
}

// The count of each item should be 0 if the contents of the collections are equal
foreach (int value in itemCounts.Values)
{
if (value != 0)
{
return false;
}
}

// The collections are equal
return true;
}
}

You could use a Hashset. Look at the SetEquals method.

EDIT: I realized as soon as I posed that this really only works for sets -- it will not properly deal with collections that have duplicate items. For example { 1, 1, 2 } and { 2, 2, 1 } will be considered equal from this algorithm's perspective. If your collections are sets (or their equality can be measured that way), however, I hope you find the below useful.

The solution I use is:

return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

Linq does the dictionary thing under the covers, so this is also O(N). (Note, it's O(1) if the collections aren't the same size).

I did a sanity check using the "SetEqual" method suggested by Daniel, the OrderBy/SequenceEquals method suggested by Igor, and my suggestion. The results are below, showing O(N*LogN) for Igor and O(N) for mine and Daniel's.

I think the simplicity of the Linq intersect code makes it the preferable solution.

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect
1024, 0, 0, 0
2048, 0, 0, 0
4096, 31.2468, 0, 0
8192, 62.4936, 0, 0
16384, 156.234, 15.6234, 0
32768, 312.468, 15.6234, 46.8702
65536, 640.5594, 46.8702, 31.2468
131072, 1312.3656, 93.7404, 203.1042
262144, 3765.2394, 187.4808, 187.4808
524288, 5718.1644, 374.9616, 406.2084
1048576, 11420.7054, 734.2998, 718.6764
2097152, 35090.1564, 1515.4698, 1484.223

Why not use .Except()

// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery = names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
Console.WriteLine(s);

http://msdn.microsoft.com/en-us/library/bb397894.aspx

erickson is almost right: since you want to match on counts of duplicates, you want a Bag. In Java, this looks something like:

(new HashBag(collection1)).equals(new HashBag(collection2))

I'm sure C# has a built-in Set implementation. I would use that first; if performance is a problem, you could always use a different Set implementation, but use the same Set interface.

A duplicate post of sorts, but check out my solution for comparing collections. It's pretty simple:

This will perform an equality comparison regardless of order:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

This will check to see if items were added / removed:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added; //Sally
var inbothlists = diff.Equal; //Bob

This will see what items in the dictionary changed:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Original post here.

There are many solutions to this problem. If you don't care about duplicates, you don't have to sort both. First make sure that they have the same number of items. After that sort one of the collections. Then binsearch each item from the second collection in the sorted collection. If you don't find a given item stop and return false. The complexity of this: - sorting the first collection: N*Log(N) - searching each item from second into the first: N*LOG(N) so you end up with 2*N*LOG(N) assuming that they match and you look up everything. This is similar to the complexity of sorting both. Also this gives you the benefit to stop earlier if there's a difference. However, keep in mind that if both are sorted before you step into this comparison and you try sorting by use something like a qsort, the sorting will be more expensive. There are optimizations for this. Another alternative, which is great for small collections where you know the range of the elements is to use a bitmask index. This will give you a O(n) performance. Another alternative is to use a hash and look it up. For small collections it is usually a lot better to do the sorting or the bitmask index. Hashtable have the disadvantage of worse locality so keep that in mind. Again, that's only if you don't care about duplicates. If you want to account for duplicates go with sorting both.

In the case of no repeats and no order, the following EqualityComparer can be used to allow collections as dictionary keys:

[Serializable]
public class SetComparer<T> : IEqualityComparer<IEnumerable<T>>
where T:IComparable<T>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == second)
return true;
if ((first == null) || (second == null))
return false;
return first.ToHashSet().SetEquals(second);
}

public int GetHashCode(IEnumerable<T> enumerable)
{
int hash = 17;

foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();

return hash;
}
}

Here is the ToHashSet() implementation I used. The hash code algorithm comes from Effective Java (by way of Jon Skeet).

Here's my extension method variant of ohadsc's answer, in case it's useful to someone

static public class EnumerableExtensions
{
static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
if ((first == null) != (second == null))
return false;

if (!object.ReferenceEquals(first, second) && (first != null))
{
if (first.Count() != second.Count())
return false;

if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
return false;
}

return true;
}

private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
{
int firstCount;
int secondCount;

var firstElementCounts = GetElementCounts<T>(first, out firstCount);
var secondElementCounts = GetElementCounts<T>(second, out secondCount);

if (firstCount != secondCount)
return true;

foreach (var kvp in firstElementCounts)
{
firstCount = kvp.Value;
secondElementCounts.TryGetValue(kvp.Key, out secondCount);

if (firstCount != secondCount)
return true;
}

return false;
}

private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>();
nullCount = 0;

foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}

return dictionary;
}

static private int GetHashCode<T>(IEnumerable<T> enumerable)
{
int hash = 17;

foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();

return hash;
}
}

In many cases the only suitable answer is the one of Igor Ostrovsky , other answers are based on objects hash code. But when you generate an hash code for an object you do so only based on his IMMUTABLE fields - such as object Id field (in case of a database entity) - Why is it important to override GetHashCode when Equals method is overridden?

This means , that if you compare two collections , the result might be true of the compare method even though the fields of the different items are non-equal . To deep compare collections , you need to use Igor's method and implement IEqualirity .

Please read the comments of me and mr.Schnider's on his most voted post.

James

Category:.net Views:1 Time:2008-09-08

Related post

  • Check if two collections are equal 2011-10-10

    Possible Duplicate: Is there a built-in method to compare collections in C#? Comparing two collections for equality I have tow collections that i want to check to see if the values contained within are not eqaul. SearchResultCollection Users1 = ds1.F

  • How to equate the elements of two array irrespective of the order of entries 2009-06-15

    I am trying to tally two arrays like myArray{a,b,c} and urArray{a,b,c,c} I wanted to check if both the elements have same elements ,for example in above condition the second array that is urArray has an extra 'c' . And the code should be able to equa

  • Comparing two Collections in Java 2010-11-03

    I have two Collections in a Java class.The first collection contains previous data, the second contains updated data from the previous collection. I would like to compare the two collections but I'm not sure of the best way to implement this efficien

  • Java Set collection - override equals method 2011-05-31

    Is there any way to override the the equals method used by a Set datatype? I wrote a custom equals method for a class called Fee. Now I have a LnkedList of Fee and I want to ensure that there are no duplicated entries. Thus I am considering using a S

  • C# more efficient way of comparing two collections 2011-07-13

    I have two collections List<Car> currentCars = GetCurrentCars(); List<Car> newCars = GetNewCars(); I don't want to use foreach loop or something because i think there should be much better way of doing this. I am looking for more efficien

  • What is the best way to compare floats for almost-equality in Python? 2011-04-08

    It's well known that comparing floats for equality is a little fiddly due to rounding and precision issues. For example: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm What is the recommended way to deal with this in Python

  • Compare two vectors in clojure no matter the order of the items 2011-12-05

    I want to compare two vectors and find out if the items they have are the same no matter the order the items are in. So.. right now in clojure: (= [1 2 3] [3 2 1]) ;=> false I want: (other_fun [1 2 3] [3 2 1]) ;=> true (other_fun [1 2 3 4] [3 2

  • Why does enumerating through a collection throw an exception but looping through its items does not 2009-04-11

    I was testing out some synchronization constructs and I noticed something that confused me. When I was enumerating through a collection while writing to it at the same time, it threw an exception (this was expected), but when I looped through the col

  • Roughly how much faster is int compared to bigint when indexing and used in ORDER BY? 2012-01-27

    First I know there are many variables, but I just need something to base my decision to use int or bigint. I have a rank field that is something like 9 to 10 digits long so I either have to decrease the precision to ensure it's never bigger than 9 di

  • Compare all the columns and then list out the common items. 2014-08-06

    How to compare multiple (more than 50) columns and make a list of commons. All cells contains both number and character. I want to compare all the columns and then list out the common items. What is the best way to do this? Thank you in advance for y

  • How Best to Compare Two Collections in Java and Act on Them? 2008-08-22

    I have two collections of the same object, Collection<Foo> oldSet and Collection<Foo> newSet. The required logic is as follow: if foo is in(*) oldSet but not newSet, call doRemove(foo) else if foo is not in oldSet but in newSet, call doAd

  • Comparing two List for equality 2009-10-10

    Other than stepping through the elements one by one, how do I compare two lists of strings for equality (in .NET 3.0): This fails: // Expected result. List<string> expected = new List<string>(); expected.Add( "a" ); expected.Add( "b" ); e

  • Problem with synchronized collections of Java when doing equals() in the reverse order from multiple threads 2009-10-12

    Example scenario: Create two SynchronizedSets (s1 and s2) Pass them to two threads (T1 and T2) Start the threads T1's run() : while (forever) s1.equals(s2) T2's run() : while (forever) s2.equals(s1) What happens? - SynchronizedSet's equals acquires l

  • What is the better approach to compare a collection with another (architecturely speaking)? 2010-02-15

    Here's an example of the architecture approach I favorited as for now: public abstract class CollectionComparer { public virtual SetEqual(IEnumerable enum1, IEnumerable enum2) { if(enum1== null && enum2== null) return true; if(enum1== null

  • Do Delphi generic collections override equals? 2010-07-30

    This is a question for the generic collection gurus. I'm shocked to find that TList does not override equals. Take a look at this example: list1:=TList<String>.Create; list2:=TList<String>.Create; list1.Add('Test'); list2.Add('Test'); Res

  • Split C# collection into equal parts, maintaining sort 2010-10-08

    I am trying to split a collection into multiple collections while maintaining a sort I have on the collection. I have tried using the following extension method, but it breaks them incorrectly. Basically, if I was to look at the items in the collecti

  • Should mutable collections override equals and hashCode? 2011-03-09

    I was just wondering if it was a good idea to override equals and hashCode for mutable collections. This would imply that if I insert such a collection into a HashSet and then modify the collection, the HashSet would no longer be able to find the col

  • Compare generic Collection? 2011-03-25

    I have a ObservableCollection<BasicClass> allCollection; ObservableCollection<BasicClass> selectedCollection; where BasicClass { public Name {get;set;} public Age {get;set;} } Now I added many BasicClass items to allCollection and only se

  • comparing two collections for comparing two text files for additions, deletions, modifications 2012-03-19

    I have two collections as below which hold IDs for Students. The ids are Strings in the format 111-1111. e.g. of ids 221-2534, 215-6365, etc. Collection<String> newKeys = new ArrayList<String>(); Collection<String> oldKeys = new Arr

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.114 (s). 11 q(s)