koobas.hobune.stream
How do I compare two lists for equality (not caring about order) C#
I have two lists and I want them to be checked to see if they have the same elements. I also want to ignore the order of the two lists. I just want it to check if they contain the same values.
Since we have now many implementations that have a complexity of O(n²), i'll post the one i mentioned in the comment above.
public static bool CompareLists<T>(List<T> aListA, List<T> aListB)
{
if (aListA == null || aListB == null || aListA.Count != aListB.Count)
return false;
if (aListA.Count == 0)
return true;
Dictionary<T, int> lookUp = new Dictionary<T, int>();
// create index for the first list
for(int i = 0; i < aListA.Count; i++)
{
int count = 0;
if (!lookUp.TryGetValue(aListA[i], out count))
{
lookUp.Add(aListA[i], 1);
continue;
}
lookUp[aListA[i]] = count + 1;
}
for (int i = 0; i < aListB.Count; i++)
{
int count = 0;
if (!lookUp.TryGetValue(aListB[i], out count))
{
// early exit as the current value in B doesn't exist in the lookUp (and not in ListA)
return false;
}
count--;
if (count <= 0)
lookUp.Remove(aListB[i]);
else
lookUp[aListB[i]] = count;
}
// if there are remaining elements in the lookUp, that means ListA contains elements that do not exist in ListB
return lookUp.Count == 0;
}
This has a linear complexity (O(n) or if you prefer O(2n) but that's actually pointless). A dictionary lookup has a constant complexity (O(1)). So the overall performance of this method should grow linearly with the number of elements.
"List.Contains" has a complexity of O(n). In most of the other solutions here you would execute List.Contains "n"-times so you get a quadratic complexity (O(n²))
If you have trouble understanding what's happening, here are some explanations:
First we do an early exit if one (or both) of the lists is null or if they have a different element count. In this case the lists can't be "equal". We don't consider the case when both lists are null as "equal".
The second early exit is a special case when both lists exist, but are empty. This is considered "equal".
The first loop will iterate through all elements in ListA and check if that element is already in the dictionary. If it is, we simply increase the value that is stored in the dictionary and update the value in the dictionary. If it isn't yet in the dictionary, we add it with a count of 1
After the first loop we have a dictionary of all elements of ListA without duplicates.
The second loop iterates over all elements in ListB. It again checks if the element exists in the dictionary. However this time if it doesn't exist, we just found an element in ListB that doesn't exist in ListA. If the element is found in the dictionary we decrease the counter for that element by 1. If the counter hits "0" we "used up" all elements of that type and we remove it from the dictionary. Otherwise we simply update the counter for that element.
If all items in ListA exist in ListB we should have matched all elements properly and the counter for each element type should have reached "0". Since we removed elements that have reached "0" the Dictionary should be empty at the end. If it is empty then ListA and ListB contains the same elements. If there are elements remaining, some elements from ListA are missing in ListB
As an example
List<int> A = new List<int>(new int[] { 1, 5, 6, 7, 3, 1 });
List<int> B = new List<int>(new int[] { 6, 3, 5, 1, 1, 7 });
if (CompareLists(A, B))
Debug.Log("Equal");
else
Debug.Log("Not equal");
This prints "Equal". If we add another "1" at the end of ListA and another "5" to ListB
List<int> A = new List<int>(new int[] { 1, 5, 6, 7, 3, 1, 1 });
List<int> B = new List<int>(new int[] { 6, 3, 5, 1, 1, 7, 5 });
It will print "Not equal" as ListA has three times a "1"s and only one "5" while ListB has two "1"s and two "5"s
If you have to deal with large lists it might be a good idea to initialize the lookUp "capacity" with the element count of ListA. It never needs more than that. It actually needs less if there are duplicates, but initializing the capacity large enough prevents unnecessary reallocations.
Thanks, this seems to work. I was having troubles understanding it at first, but I managed to get it to work. Thank you.
First, are they the same length? Second, is every element of list A to be found in list B?
You can write this easily in LINQ using .Contains().
You can make it go faster by doing a pass through list A to build an index, then a pass through list B to check against the index.
It's slightly more complex if the lists may contain duplicates.
Well, if you use a Dictionary<YourListItem, int> as index, duplicates wouldn't be a problem. You just increase the int for each element you found in A and decrease every matching element. When the counter hits 0 you can delete it from the dictionary. At the end the dictionary should be empty. If B contains an element that isn't in the dictionary you could early exit with "false".
I'm having troubles figuring out how to write that.
Thanks for replying. They would have to be the same length in order to be equal, right? The lists could contain duplicates.
This is what I have so far.
public List<string> lst1;
public List<string> lst2;
public bool match;
void Update (){
if (lst1.Count == lst2.Count) {
foreach (string item in lst1){
if (lst2.Contains (item)){
match = true;
}
}
} else {
match = false;
}
Debug.Log (match);
}
The only thing that doesn't work is that match = true; when there is only one correct item in each list.
No, the code is wrong. The match variable is not initialised and the loop should ter$$anonymous$$ate early.
@Bunny83: this will work.
You can improve the code by using foreach loops. If you do this and omit the length check this will work on IEnumerable<T>. If you do the length check the final if is not needed.
You might also benchmark it to see whether deleting keys is a hit on performance.
You can use the Intersect method. Here is a simple console application :
using System;
using System.Linq;
class Program
{
static void Main()
{
var nums1 = new int[] { 2, 4, 6, 8, 10, 9 };
var nums2 = new int[] { 1, 3, 6, 9, 12, 2 };
if (nums1.Intersect(nums2).Any()) // check if there is equal items
{
var equalItems = nums1.Intersect(nums2); // get list of equal items (2, 6, 9)
foreach (var item in equalItems)
{
Console.WriteLine(item);
}
}
}
}
No, this is not a test for equality and in any case it won't work with lists that contain duplicates.
Are you kidding me? I have used it like a 100 times!
For anyone coming across this,
It's easier if you just sort the two lists/arrays. Then json serialize them and compare the two strings.
using System;
using Newtonsoft.Json;
public class Program
{
public static void Main()
{
string[] list1 = new string[] {"a", "b", "c", "d"};
string[] list2 = new string[] {"d", "b", "c", "a"};
Array.Sort(list1);
Array.Sort(list2);
Console.WriteLine(JsonConvert.SerializeObject(list1) == JsonConvert.SerializeObject(list2));
}
}
You can obviously convert that to a function pretty easily. Probably return false if they are different sizes to save on some processing. Not necessarily computationally the most efficient, but it works and it's easy to understand.
Here you go, it has a Generic type of elements so it's portable everywhere for you
that's the code:
using System.Collections.Generic;
using UnityEngine;
public class ListComparing : MonoBehaviour {
List<string> names1 = new List<string>(new string[] {"Jordan", "Jake", "Mike", "John", "Sandra"});
List<string> names2 = new List<string>(new string[] {"Mike", "John", "Jake", "Sandra", "Jordan"});
List<int> ages1 = new List<int>(new int[] {3, 15, 7, 10});
List<int> ages2 = new List<int>(new int[] {7, 15, 10, 3});
void Start ()
{
//Here we give the generic value a type of string parameter to compare the lists by a string value
print(
"The list of names1 and names2 equality is: " +
CompareLists<string> (names1, names2)
);
//Here we give the generic value a type of int parameter to compare the lists by an int value
print(
"The list of ages1 and ages2 equality is: " +
CompareLists<int> (ages1, ages2)
);
}
//A method of type bool to give you the result of equality between two lists
bool CompareLists<T> (List<T> list1, List<T> list2)
{
//here we check the count of list elements if they match, it can work also if the list count doesn't meet, to do it just comment out this if statement
if (list1.Count != list2.Count)
return false;
//here we check and find every element from the list1 in the list2
foreach (var item in list1)
if (list2.Find(i => i.Equals(item)) == null)
return false;
//here we check and find every element from the list2 in the list1 to make sure they don't have repeated and mismatched elements
foreach (var item in list2)
if (list1.Find(i => i.Equals(item)) == null)
return false;
//return true because we didn't find any missing element
return true;
}
}
This is actually not going to work out if you consider duplicate (OP said there will be duplicate). If you have collection A with (1, 1, 2, 3) and collection B with (1, 2, 3, 3), your code will return true since all items from A can be found in B and vice-versa, though they are not the same.
Why search twice? It doesn't handle duplicates either time. Try comparing a,b,b,c to a,b,c,c. You need a better method.
And did you test this properly with value types? It can fail, because the comparison to null is incorrect. Better to use FindIndex() or Contains().
