How Can I Efficiently Compare Two Lists for Equality, Ignoring Order and Allowing Duplicates?

Compare List objects for equality

This article explores how to compare two List objects to see if they contain the same elements, regardless of the order of the elements. It is worth noting that objects of type MyType may appear multiple times in any list.

Initial plan

To ensure exact equality, i.e. both lists contain the same elements and their frequencies, it is recommended to sort the lists before comparing:

Enumerable.SequenceEqual(list1.OrderBy(t => t), list2.OrderBy(t => t))

Optimization plan

However, in order to improve performance, someone has proposed another solution:

public static bool ScrambledEquals<T>(IEnumerable<T> list1, IEnumerable<T> list2) {
  var cnt = new Dictionary<T, int>();
  foreach (T s in list1) {
    if (cnt.ContainsKey(s)) {
      cnt[s]++;
    } else {
      cnt.Add(s, 1);
    }
  }
  foreach (T s in list2) {
    if (cnt.ContainsKey(s)) {
      cnt[s]--;
    } else {
      return false;
    }
  }
  return cnt.Values.All(c => c == 0);
}

The performance of this method is significantly better than the initial solution. It only requires the IEquatable interface and not the IComparable interface.

Handling various data types

In order to adapt to the situation of containing different data types (including nullable types) as keys, an improved solution can be used:

public static bool ScrambledEquals<T>(IEnumerable<T> list1, IEnumerable<T> list2, IEqualityComparer<T> comparer) {
  var cnt = new Dictionary<T, int>(comparer);
  ...
}

The above is the detailed content of How Can I Efficiently Compare Two Lists for Equality, Ignoring Order and Allowing Duplicates?. For more information, please follow other related articles on the PHP Chinese website!