[RESOLVED] Set Equals, does it exist?

[Shaggy Hiker]

I seem to occasionally find myself trying to compare two List(of T) to see whether or not they contain the same elements. A quick check of the documentation shows the SequenceEquals method, but that appears to check whether the two lists have the same length, and have the same elements in the same order. I don't care about the order. I want to know whether two collections have the same elements. Doing this is not terribly difficult, and seems common enough, so I was expecting that there would be some function that handles it. I'm not seeing one, though. Does such a thing exist?

[Megalith]

hmm not seen it, course you could sort both lists and compare that way but your not saving anything and are consuming more momory

[boops boops]

I was expecting that there would be some function that handles it. I'm not seeing one, though. Does such a thing exist?

It does now. I just made one:

Public Function ElementsEqual(Set1 As IEnumerable(Of Object), Set2 As IEnumerable(Of Object)) As Boolean
	Return (Set1.Count = Set2.Count) AndAlso Set1.All(Function(t) Set2.Contains(t))
End Function

Any good? BB

[Shaggy Hiker]

Yeah, it's almost there, but I have one already built that does the same thing for the specific case that I am currently dealing with. What would be good would be a general extension. There should be two improvements on that. The first, as you mentioned, would be that there should be a quick check for the situation where the length isn't the same between the two, as that would be a fast comparison, and it is essential or else you are just looking at whether one set is a subset of the other.

The other improvement is that it should be (Of T) rather than using objects. After all, as written, Contains seems likely to work ok as long as your objects are actually value types. It seems like there would be boxing and unboxing going on in that case, too, but I'm not sufficiently familiar with that part. For reference types, Contains might not be all that good. Now that I think about it, I'm not so sure what would happen. By default, it should just be seeing whether a certain object is in both lists. However, if you had implemented something like IEquatable for the objects in the list, does Contains look for an equal object or only the same object? Not sure.

In any case, it seems like a generic would make sense. I might get around to that, but for now I posted this question then immediately wandered down another path, so if somebody else implements a complete solution....I might not even get to use it.

[boops boops]

Ok, FWIW here's a generic extension method based on the same function. And Contains does work for reference types.

Public Module CollectionExtensions
   <System.Runtime.CompilerServices.Extension()> _
   Public Function ElementsEqual(Of T)(Set1 As IEnumerable(Of T), set2 As IEnumerable(Of T)) As Boolean
      Return (Set1.Count = set2.Count) AndAlso Set1.All(Function(E) set2.Contains(E))
   End Function
End Module

Here's a test:

Dim Set1 As New List(Of Control)({Button1, Button2})
Dim Set2 As New List(Of Control)({Button2, Button1})
Console.WriteLine(ElementsEqual(Of Control)(Set1, Set2)) 'returns True
Set2(0) = Button1
Console.WriteLine(ElementsEqual(Of Control)(Set1, Set2)) 'returns False

EDIT: It doesn't seem to work as an extension method after all. But you can call it as a non-extension Generic function as in my test above.

BB

[penagate]

You could sort the two lists first and then use SequenceEqual.

[Shaggy Hiker]

Yes, you could sort first, but I would expect that it would decrease performance.

[penagate]

Perhaps, perhaps not.

After all, this:

Set1.All(Function(t) Set2.Contains(t))

enumerates Set2 for every item in Set1.

[i00]

It does now. I just made one:

Public Function ElementsEqual(Set1 As IEnumerable(Of Object), Set2 As IEnumerable(Of Object)) As Boolean
	Return (Set1.Count = Set2.Count) AndAlso Set1.All(Function(t) Set2.Contains(t))
End Function

Any good? BB

Don't think this would be accurate.. if set1 has 100 of the same item and set two has just one occurance of the same item and 99 other items this would give a false positive match?

Kris

[boops boops]

Don't think this would be accurate.. if set1 has 100 of the same item and set two has just one occurance of the same item and 99 other items this would give a false positive match?
Kris

That's a good point. A mathematical Set is a collection of distinct objects, so I assumed unique items in each set. The function checks if at least one of each item in Set1 occurs in Set2.

If the collections contain repeat items but the repeats don't matter then:
1. there is no point in comparing the counts.
2. it is necessary to check the reverse as well: does each item in Set2 also occur in Set1.

If the number of repeat occurrences matters it is a different problem: comparing sorted lists is clearly the way to go. BB

[boops boops]

Hold the press! After editing my previous post several times, it came back to me: I suggest you look at the SortedSet(T) class. You can initialize it from any IEnumerable collection, and it has a SetEquals method (as well as Intersects, IsSubsetOf, Is SupersetOf and much else). I stumbled across SortedSet in msdn a few weeks ago, and it was at the back of my mind when I first replied but I couldn't remember what it was called.

By the way, if the items in the collection don't have to be unique, you might find the HashSet(T).SetEquals method useful.

p.s. I just searched msdn for SetEquals. Why didn't anyone think of that?
BB

[Shaggy Hiker]

Hold the press! After editing my previous post several times, it came back to me: I suggest you look at the SortedSet(T) class. You can initialize it from any IEnumerable collection, and it has a SetEquals method (as well as Intersects, IsSubsetOf, Is SupersetOf and much else). I stumbled across SortedSet in msdn a few weeks ago, and it was at the back of my mind when I first replied but I couldn't remember what it was called.

That's a good find. I was trying to avoid the sorted set, so I didn't bother looking at SortedSet. There isn't a fundamental reason to avoid the sorted set other than a kind of esoteric one: The program that uses this has certain tasks that have to be as fast as I can make them for no other reason than that I am going to lard them up with an unknown amount of overhead. Therefore, I only wanted to sort as a last resort rather than as a matter of course. I recognized that this problem becomes considerably easier when both lists are sorted; I just thought that it would probably exist anyways. However, I think that i00 got the right of it. Instead of this being a simple, general, function, it really isn't UNLESS the sets are sorted or unique. Since uniqueness is not required for a List, only sorting makes the problem manageable.

There is a further issue with reference types. Consider this trivial example:

Public Class Foo
 Public Value As Integer = 5
End Class

Dim A As New Foo
Dim B As New Foo
Dim myList as New List(of T)

myList.Add(A)

If myList.Contains(B) Then 'This will be False

The final line evaluates to False, as it should, since B is not in the collection. However, a more practical example, which would take too long to set up, would expect this line to return True. A person might reasonable be wanting to know whether List1 contains elements that equal the elements in List2. The question is not whether myList contains the actual object, but whether myList contains an object that would be equal to the object. When I was looking (in the wrong place) yesterday, I found that many of the aggregates that worked with set intersections included an overload that had a comparison function. I figured that was so that people could supply a custom comparator. I think the same should be available for this....except that, as noted previously, the whole thing only works well for unique or sorted sets.

p.s. I just searched msdn for SetEquals. Why didn't anyone think of that?
BB

There is always a problem with searches: If you have your mind fixed on the solution appearing in one guise, and that fixation is wrong, you will not find what you don't know to be looking for.


This has been an excellent discussion. My thanks to all of you.