Проверьте, имеют ли два IEnumerable <T> одинаковые значения с одинаковыми частотами

Ответ 1

Самый эффективный способ будет зависеть от типов данных. Достаточно эффективное решение O (N), которое очень короткое:

var list1Groups=list1.ToLookup(i=>i);
var list2Groups=list2.ToLookup(i=>i);
return list1Groups.Count == list2Groups.Count 
   && list1Groups.All(g => g.Count() == list2Groups[g.Key].Count());

Элементы должны иметь действительную реализацию Equals и GetHashcode.

Если вам требуется более быстрое решение, cdhowie ниже приведено сравнительно быстрое 10000 элементов, и он продвигается в 5 раз для больших коллекций простых объектов - вероятно, из-за лучшей эффективности памяти.

Наконец, если вы действительно заинтересованы в производительности, я бы определенно попробовал подход Sort-then-SequenceEqual. Хотя это имеет худшую сложность, это всего лишь фактор log N, и это может быть определенно утоплено различиями в константе для всех практических размеров набора данных - и вы можете сортировать на месте, использовать массивы или даже постепенно сортировать (который может быть линейным). Даже при 4 миллиардах элементов, log-base-2 составляет всего 32; что соответствующая разница в производительности, но разница в постоянном коэффициенте может быть, вероятно, больше. Например, если вы имеете дело с массивами ints и не возражаете изменить порядок сбора, следующее быстрее, чем любая опция даже для 10000000 элементов (в два раза это, и я получаю OutOfMemory на 32-битной основе):

Array.Sort(list1);
Array.Sort(list2);
return list1.SequenceEqual(list2);

YMMV в зависимости от машины, типа данных, лунного цикла и других обычных факторов, влияющих на микрообъекты.

Ответ 2

Сначала соберите, как вы уже сделали, а затем используйте Enumerable.SequenceEqual. Вы можете использовать первую перегрузку, если ваш тип реализует IEquatable<MyCustomType> или переопределяет Equals; в противном случае вам придется использовать вторую форму и предоставить свой собственный IEqualityComparer<MyCustomType>.

Итак, если ваш тип реализует равенство, просто выполните:

return a.SequenceEqual(b);

Здесь еще один вариант, который быстрее, безопаснее и не требует сортировки:

public static bool UnsortedSequencesEqual<T>(
    this IEnumerable<T> first,
    IEnumerable<T> second)
{
    return UnsortedSequencesEqual(first, second, null);
}

public static bool UnsortedSequencesEqual<T>(
    this IEnumerable<T> first,
    IEnumerable<T> second,
    IEqualityComparer<T> comparer)
{
    if (first == null)
        throw new ArgumentNullException("first");

    if (second == null)
        throw new ArgumentNullException("second");

    var counts = new Dictionary<T, int>(comparer);

    foreach (var i in first) {
        int c;
        if (counts.TryGetValue(i, out c))
            counts[i] = c + 1;
        else
            counts[i] = 1;
    }

    foreach (var i in second) {
        int c;
        if (!counts.TryGetValue(i, out c))
            return false;

        if (c == 1)
            counts.Remove(i);
        else
            counts[i] = c - 1;
    }

    return counts.Count == 0;
}

Ответ 3

Вы можете использовать двоичное дерево поиска, чтобы обеспечить сортировку данных. Это сделает операцию O (log N). Затем вы можете запускать каждое дерево по одному элементу за раз и прерывать, как только вы найдете не равным условию. Это также даст вам дополнительное преимущество: сначала можно сравнить размер двух деревьев, так как дубликаты будут отфильтрованы. Я предполагаю, что они рассматриваются как множества, в которых { "harry" , "harry" } == { "harry" ).

Если вы подсчитываете дубликаты, сначала выполняйте quicksort или mergesort, чтобы затем выполнить операцию сравнения O (N). Вы могли бы, конечно, сначала сравнить размер, так как две перечисления не могут быть равны, если размеры разные. Поскольку данные сортируются, первое неравное условие, с которым вы столкнулись, сделает всю операцию "не равной".

Ответ 4

@cdhowie ответ велик, но вот хороший трюк, который делает его еще лучше для типов, объявляющих .Count, сравнивая это значение перед декомпозицией параметров до IEnumerable. Просто добавьте это в свой код в дополнение к его решению:

    public static bool UnsortedSequencesEqual<T>(this IReadOnlyList<T> first, IReadOnlyList<T> second, IEqualityComparer<T> comparer = null)
    {
        if (first.Count != second.Count)
        {
            return false;
        }

        return UnsortedSequencesEqual((IEnumerable<T>)first, (IEnumerable<T>)second, comparer);
    }