I have two arrays of objects which are likely to have the same values, but in a different order, e.g.
{ "cat", "dog", "mouse", "pangolin" }
{ "dog", "pangolin", "cat", "mouse" }
I wish to treat these two arrays as equal. What's the fastest way to test this?
I can't guarantee that this is the fastest, but it's certainly quite efficient:
bool areEquivalent = array1.Length == array2.Length
&& new HashSet<string>(array1).SetEquals(array2);
EDIT: SaeedAlg and Sandris raise valid points about different frequencies of duplicates causing problems with this approach. I can see two workarounds if this is important (haven't given much thought to their respective efficiencies):
1.Sort the arrays and then compare them sequentially. This approach, in theory, should have quadratic complexity in the worst case. E.g.:
return array1.Length == array2.Length
&& array1.OrderBy(s => s).SequenceEqual(array2.OrderBy(s => s));
2.Build up a frequency-table of strings in each array and then compare them. E.g.:
if(array1.Length != array2.Length)
return false;
var f1 = array1.GroupBy(s => s)
.Select(group => new {group.Key, Count = group.Count() });
var f2 = array2.GroupBy(s => s)
.Select(group => new {group.Key, Count = group.Count() });
return !f1.Except(f2).Any();
I think the only reasonable way is to sort them and then compare.
Sorting requires O(n logn)
and comparing O(n)
, so that's still a total of O(n logn)
Have you tried something like
string[] arr1 = {"cat", "dog", "mouse", "pangolin"};
string[] arr2 = {"dog", "pangolin", "cat", "mouse"};
bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0;
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With