[C#] 차이점에 대해 두 개의 일반 목록을 비교하는 가장 빠른 방법

두 개의 대규모 (> 50.000 개 항목)를 비교하는 가장 빠르며 (최소한 자원 집약적) 결과적으로 아래 목록과 같은 두 개의 목록이 있습니다.

첫 번째 목록에는 나타나지만 두 번째 목록에는 나타나지 않는 항목
두 번째 목록에는 나타나지만 첫 번째 목록에는 나타나지 않는 항목

현재 List 또는 IReadOnlyCollection으로 작업하고 있으며 linq 쿼리 에서이 문제를 해결합니다.

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();

그러나 이것은 내가 원하는만큼 성능이 좋지 않습니다. 많은 목록을 처리해야 할 때이 작업을 더 빠르고 덜 집중적으로 수행 할 생각이 있습니까?

답변

사용 Except:

var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();

나는 이것보다 실제로 조금 더 빠른 접근법이 있다고 생각하지만, 이것조차도 O (N * M) 접근법보다 훨씬 빠를 것입니다.

이들을 결합하려면 위와 함께 return 문을 사용하여 메서드를 만들 수 있습니다.

return !firstNotSecond.Any() && !secondNotFirst.Any();

주목해야 할 점은 문제의 원래 코드와 여기의 솔루션 사이에 결과에 차이 가 있다는 것 입니다 . 한 목록에있는 중복 요소는 내 코드로 한 번만보고되지만 많은 수로보고됩니다 원래 코드에서 발생하는 시간.

예를 들어 [1, 2, 2, 2, 3]및의 목록을 사용 [1]하면 “list1의 요소이지만 list2가 아닌 요소”는 원래 코드의 결과가 [2, 2, 2, 3]됩니다. 내 코드로는 그냥 있습니다 [2, 3]. 많은 경우에 문제가되지는 않지만 알아 둘 가치가 있습니다.

답변

더 효율적인 방법은 다음과 Enumerable.Except같습니다.

var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);

이 방법은 지연된 실행을 사용하여 구현됩니다. 예를 들어 다음과 같이 쓸 수 있습니다.

var first10 = inListButNotInList2.Take(10);

내부적으로 Set<T>객체를 비교하기 위해 a 를 사용하기 때문에 효율적 입니다. 먼저 두 번째 시퀀스에서 고유 한 모든 값을 수집 한 다음 첫 번째 결과를 스트리밍하여 이전에 보지 않았는지 확인합니다.

답변

Enumerable.SequenceEqual 메서드

등식 비교기에 따라 두 시퀀스가 같은지 여부를 결정합니다.
MS.Docs

Enumerable.SequenceEqual(list1, list2);

이것은 모든 기본 데이터 유형에 적용됩니다. 사용자 정의 객체에서 사용해야하는 경우 구현해야합니다.IEqualityComparer

동등성에 대한 객체 비교를 지원하는 방법을 정의합니다.

IEqualityComparer 인터페이스

동등성에 대한 객체 비교를 지원하는 방법을 정의합니다.
IEqualityComparer를위한 MS.Docs

답변

결과를 대소 문자를 구분하지 않으려면 다음이 작동합니다.

List<string> list1 = new List<string> { "a.dll", "b1.dll" };
List<string> list2 = new List<string> { "A.dll", "b2.dll" };

var firstNotSecond = list1.Except(list2, StringComparer.OrdinalIgnoreCase).ToList();
var secondNotFirst = list2.Except(list1, StringComparer.OrdinalIgnoreCase).ToList();

firstNotSecondb1.dll 이 포함 됩니다

secondNotFirstb2.dll 이 포함 됩니다

답변

이 문제는 아니지만 목록을 동등하고 그렇지 않은 비교하는 코드가 있습니다! 동일한 객체 :

public class EquatableList<T> : List<T>, IEquatable<EquatableList<T>> where    T : IEquatable<T>

/// <summary>
/// True, if this contains element with equal property-values
/// </summary>
/// <param name="element">element of Type T</param>
/// <returns>True, if this contains element</returns>
public new Boolean Contains(T element)
{
    return this.Any(t => t.Equals(element));
}

/// <summary>
/// True, if list is equal to this
/// </summary>
/// <param name="list">list</param>
/// <returns>True, if instance equals list</returns>
public Boolean Equals(EquatableList<T> list)
{
    if (list == null) return false;
    return this.All(list.Contains) && list.All(this.Contains);
}

답변

이 방법으로 시도하십시오 :

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));

답변

using System.Collections.Generic;
using System.Linq;

namespace YourProject.Extensions
{
    public static class ListExtensions
    {
        public static bool SetwiseEquivalentTo<T>(this List<T> list, List<T> other)
            where T: IEquatable<T>
        {
            if (list.Except(other).Any())
                return false;
            if (other.Except(list).Any())
                return false;
            return true;
        }
    }
}

때로는 두 목록이 다른지 여부 만 알고 그 차이점이 무엇인지 알아야 합니다 . 이 경우이 확장 방법을 프로젝트에 추가하십시오. 나열된 객체는 IEquatable을 구현해야합니다!

용법:

public sealed class Car : IEquatable<Car>
{
    public Price Price { get; }
    public List<Component> Components { get; }

    ...
    public override bool Equals(object obj)
        => obj is Car other && Equals(other);

    public bool Equals(Car other)
        => Price == other.Price
            && Components.SetwiseEquivalentTo(other.Components);

    public override int GetHashCode()
        => Components.Aggregate(
            Price.GetHashCode(),
            (code, next) => code ^ next.GetHashCode()); // Bitwise XOR
}

Component클래스가 무엇이든 여기에 표시된 메소드 Car는 거의 동일하게 구현되어야합니다.

GetHashCode를 어떻게 작성했는지 주목하는 것이 매우 중요합니다. 순서가 제대로 구현하기에 IEquatable, Equals그리고 GetHashCode 해야한다 논리적으로 호환 방식으로 인스턴스의 속성에서 작동합니다.

내용이 같은 두 목록은 여전히 다른 객체이며 다른 해시 코드를 생성합니다. 이 두 목록이 동일하게 취급되기를 원하므로 각 목록에 GetHashCode대해 동일한 값을 생성 해야 합니다. 해시 코드를 목록의 모든 요소에 위임하고 표준 비트 XOR을 사용하여 해시 코드를 모두 결합하여이를 수행 할 수 있습니다. XOR은 순서에 구애받지 않으므로 목록이 다르게 정렬되는지는 중요하지 않습니다. 그것들은 동등한 멤버만을 포함하고 있다는 것만 중요합니다.

참고 : 이상한 이름은 메서드가 목록의 요소 순서를 고려하지 않는다는 것을 의미합니다. 목록의 요소 순서를 신경 쓰면이 방법이 적합하지 않습니다!