Огромные два списка <string>данных должны сравниваться с использованием c # и должны обеспечивать повышение производительности

Question

У меня есть два списка, которые содержат огромные данные и имеют следующий код, который я использовал до сих пор.Но есть некоторые сомнения по этому поводу, потому что много путаницы по поводу данных сравниваются или нет в элементах списка.Здесь я использую последовательность Equal для сравнения данных У меня есть два вопроса, где-то я обнаружил, что sequenceEqual будет сравнивать данные в списках.Так использовал это.1. Будет последовательность Equal сравнивает данные в списках 2. лучший способ кода для повышения производительности.В соответствии с пониманием, я сохранил только три элемента в обоих списках, но наше требование содержит огромные элементы данных в списках.поэтому нужно улучшить производительность

bool value = false;
        List<string> list1 = new List<string>();
        list1.Add("one");
        list1.Add("two");
        list1.Add( "three" );

        List<string> list2 = new List<string>();
        list2.Add("one");
        list2.Add("two");
        list2.Add("three");
        list1.Sort();
        list2.Sort();
        if (list1.SequenceEqual(list2))
        {
            value = true;
        }
        else
        {
            value = false;
        }
        return value;

Answer 1

Вот реализация SequenceEqual:

public static bool SequenceEqual<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    if (comparer == null)
    {
        comparer = EqualityComparer<TSource>.Default;
    }
    if (first == null)
    {
        throw Error.ArgumentNull("first");
    }
    if (second == null)
    {
        throw Error.ArgumentNull("second");
    }
    using (IEnumerator<TSource> enumerator = first.GetEnumerator())
    {
        using (IEnumerator<TSource> enumerator2 = second.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                if (!enumerator2.MoveNext() || !comparer.Equals(enumerator.Current, enumerator2.Current))
                {
                    return false;
                }
            }
            if (enumerator2.MoveNext())
            {
                return false;
            }
        }
    }
    return true;
}

Он не проверяет длину и просто просматривает оба списка, чтобы подтвердить, равны ли они.

Если вы проверяете два списка длиной 1_000_000 и 1_000_001, это ужасно неэффективно.

Итак, сначала проверьте длины, затем вызывайте SequenceEqual, только если они одинаковы.

Если вы проверяете равенство по множеству, а не по положению, тогда сделайте из каждого HashSet<string>, а затем проверьте его.

Answer 2

Ваш метод сравнения двух списков по сути такой:

private static bool SequenceUnorderedEqual<T>(IEnumerable<T> source1,
    IEnumerable<T> source2)
{
    var list1 = source1.ToList();
    var list2 = source2.ToList();
    list1.Sort();
    list2.Sort();
    return list1.SequenceEqual(list2);
}

Использование словаря по крайней мере в десять раз быстрее, за счет того, что он немного сложнее.

private static bool SequenceUnorderedEqual<T>(IEnumerable<T> source1,
    IEnumerable<T> source2)
{
    var occurences = new Dictionary<T, int>();
    // Populating the dictionary using source1
    foreach (var item in source1)
    {
        int value;
        if (!occurences.TryGetValue(item, out value))
        {
            value = 0;
        }
        occurences[item] = value + 1;
    }
    // Depopulating the dictionary using source2
    foreach (var item in source2)
    {
        int value;
        if (!occurences.TryGetValue(item, out value))
        {
            value = 0;
        }
        if (value <= 0) return false;
        occurences[item] = value - 1;
    }
    // Now all counters should be reduced to zero
    return occurences.Values.All(c => c == 0);
}

---

Обновление: ниже - еще более быстрая версия, использующая параллелизм.

private static bool SequenceUnorderedEqual<T>(IEnumerable<T> source1,
    IEnumerable<T> source2)
{
    var task1 = Task.Run(() => GetOccurences(source1));
    var task2 = Task.Run(() => GetOccurences(source2));
    Task.WaitAll(task1, task2);
    var occurences1 = task1.Result;
    var occurences2 = task2.Result;
    if (occurences1.Count != occurences2.Count) return false;
    var result = Parallel.ForEach(occurences1, (entry1, loopState) =>
    {
        var found2 = occurences2.TryGetValue(entry1.Key, out var value2);
        if (!found2 || entry1.Value != value2) loopState.Stop();
    });
    return result.IsCompleted;

    Dictionary<T, int> GetOccurences(IEnumerable<T> source)
    {
        var dic = new Dictionary<T, int>();
        foreach (var item in source)
        {
            dic[item] = dic.TryGetValue(item, out int c) ? c + 1 : 1;
        }
        return dic;
    }
}

Answer 3

Насколько я понимаю, использование метода SequenceEqual от Linq будет очень эффективным. Он эффективно возвращает true, если, заключив в кавычки, «две исходные последовательности имеют одинаковую длину, а их соответствующие элементы равны в соответствии с компаратором равенства по умолчанию для их типа», в противном случае - false. Там действительно не будет гораздо более быстрый способ сделать это сравнение.