두 일반 목록의 차이점을 비교하는 가장 빠른 방법
두 개의 방대한 항목(50,000개 이상)을 비교하는 데 가장 빠르고 리소스 집약도가 낮은 항목은 무엇이며, 그 결과 아래와 같은 두 개의 목록이 있습니다.
- 첫 번째 목록에는 표시되지만 두 번째 목록에는 표시되지 않는 항목
- 두 번째 목록에는 표시되지만 첫 번째 목록에는 표시되지 않는 항목
현재 List 또는 IReadOnlyCollection으로 작업 중이며 linq 쿼리에서 이 문제를 해결합니다.
var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();
하지만 이것은 제가 원하는 만큼 잘 수행되지 않습니다.제가 많은 목록을 처리해야 하기 때문에 이것을 더 빠르고 리소스 집약적으로 만들 방법이 있습니까?
사용:
var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();
실제로 이보다 약간 더 빠른 접근 방식이 있을 것으로 생각되지만, 이마저도 O(N*M) 접근 방식보다 훨씬 더 빠를 것입니다.
이들을 결합하려면 위의 명령문을 사용하여 메서드를 만든 다음 반환문을 만들 수 있습니다.
return !firstNotSecond.Any() && !secondNotFirst.Any();
한 가지 주의할 점은 질문의 원본 코드와 여기에 있는 솔루션 간에 결과에 차이가 있다는 것입니다. 하나의 목록에 있는 중복 요소는 내 코드로 한 번만 보고되는 반면 원래 코드에서 발생하는 횟수만큼 보고됩니다.
를 들어, 경우에는 " " " 입니다.[1, 2, 2, 2, 3]그리고.[1]" 는 "list1" "list2" "list2" "가 될 입니다.[2, 2, 2, 3]내 코드로는 그냥[2, 3]대부분의 경우 문제가 되지는 않겠지만, 알아둘 가치가 있습니다.
열거할 수 있습니다.시퀀스 동일 방법
동일 비교에 따라 두 시퀀스가 동일한지 여부를 결정합니다.MS.Docs
Enumerable.SequenceEqual(list1, list2);
이것은 모든 기본 데이터 유형에 적용됩니다. 개체를 사용해야 .IEqualityComparer
동일성에 대한 개체 비교를 지원하는 방법을 정의합니다.
IE 품질 비교 인터페이스
동일성에 대한 개체 비교를 지원하는 방법을 정의합니다.MS.Docs for IEquality Comparer
보다 효율적인 방법은 다음과 같습니다.
var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);
이 방법은 지연 실행을 사용하여 구현됩니다.즉, 예를 들어 다음과 같이 쓸 수 있습니다.
var first10 = inListButNotInList2.Take(10);
또한 내부적으로 사용하기 때문에 효율적입니다.Set<T>개체를 비교합니다.먼저 두 번째 시퀀스에서 모든 고유한 값을 수집한 다음, 첫 번째 시퀀스의 결과를 스트리밍하여 이전에 볼 수 없었던 값을 확인함으로써 작동합니다.
대소문자를 구분하지 않고 결과를 사용하려면 다음과 같이 하십시오.
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을 포함합니다.
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은 순서에 구애받지 않으므로 목록이 다르게 정렬되어도 상관 없습니다.중요한 것은 그들이 동등한 구성원들만 포함한다는 것입니다.
참고: 이상한 이름은 메소드가 목록에 있는 요소의 순서를 고려하지 않는다는 사실을 의미합니다.목록에 있는 요소의 순서가 중요한 경우 이 방법은 사용자에게 적합하지 않습니다!
다음 방법을 사용해 보십시오.
var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
.Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));
이 문제의 경우는 아니지만, 동일한 개체와 동일하지 않은 개체의 목록을 비교할 수 있는 코드가 있습니다.
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 set1 = new HashSet<T>(list1);
var set2 = new HashSet<T>(list2);
var areEqual = set1.SetEquals(set2);
여기서 T는 목록 요소의 유형입니다.
Jon Skeet의 답변은 적은 수의 요소(최대 수백만 개)를 사용하는 일상적인 작업에 대한 훌륭한 조언이지만, 그럼에도 불구하고 가장 빠른 접근 방식은 아니며 리소스 효율성도 높지 않습니다.분명한 단점은 완전한 차이를 얻으려면 데이터에 대해 두 번의 패스가 필요하다는 것입니다(동일한 요소가 관심을 갖는 경우에도 세 번은 패스해야 함).분명히, 이것은 맞춤형 재구현을 통해 피할 수 있습니다.Except그러나 해시 집합을 만들려면 많은 메모리가 필요하고 해시 계산에는 시간이 필요합니다.
매우 큰 데이터 세트(수십억 개의 요소)의 경우 일반적으로 특정 상황을 고려하는 것이 효과적입니다.다음은 영감을 줄 수 있는 몇 가지 아이디어입니다.요소를 비교할 수 있는 경우(실제로는 거의 항상 해당됨), 목록을 정렬하고 다음 zip 접근 방식을 적용하는 것이 고려할 가치가 있습니다.
/// <returns>The elements of the specified (ascendingly) sorted enumerations that are
/// contained only in one of them, together with an indicator,
/// whether the element is contained in the reference enumeration (-1)
/// or in the difference enumeration (+1).</returns>
public static IEnumerable<Tuple<T, int>> FindDifferences<T>(IEnumerable<T> sortedReferenceObjects,
IEnumerable<T> sortedDifferenceObjects, IComparer<T> comparer)
{
var refs = sortedReferenceObjects.GetEnumerator();
var diffs = sortedDifferenceObjects.GetEnumerator();
bool hasNext = refs.MoveNext() && diffs.MoveNext();
while (hasNext)
{
int comparison = comparer.Compare(refs.Current, diffs.Current);
if (comparison == 0)
{
// insert code that emits the current element if equal elements should be kept
hasNext = refs.MoveNext() && diffs.MoveNext();
}
else if (comparison < 0)
{
yield return Tuple.Create(refs.Current, -1);
hasNext = refs.MoveNext();
}
else
{
yield return Tuple.Create(diffs.Current, 1);
hasNext = diffs.MoveNext();
}
}
}
예를 들어 다음과 같은 방식으로 사용할 수 있습니다.
const int N = <Large number>;
const int omit1 = 231567;
const int omit2 = 589932;
IEnumerable<int> numberSequence1 = Enumerable.Range(0, N).Select(i => i < omit1 ? i : i + 1);
IEnumerable<int> numberSequence2 = Enumerable.Range(0, N).Select(i => i < omit2 ? i : i + 1);
var numberDiffs = FindDifferences(numberSequence1, numberSequence2, Comparer<int>.Default);
컴퓨터에서 벤치마킹한 결과 N = 1M에 대해 다음과 같은 결과가 나왔습니다.
| 방법 | 의미하다 | 오류 | 표준 개발 | 비율 | 0세대 | 1세대 | 2세대 | 할당됨 |
|---|---|---|---|---|---|---|---|---|
| DiffLinq | 115.19ms | 0.656ms | 0.582ms | 1.00 | 2800.0000 | 2800.0000 | 2800.0000 | 67110744 B |
| DiffZip | 23.48ms | 0.018ms | 0.015ms | 0.20 | - | - | - | 720B |
N = 100M의 경우:
| 방법 | 의미하다 | 오류 | 표준 개발 | 비율 | 0세대 | 1세대 | 2세대 | 할당됨 |
|---|---|---|---|---|---|---|---|---|
| DiffLinq | 12.1987년 | 0.0427초 | 0.0379초 | 1.00 | 13000.0000 | 13000.0000 | 13000.0000 | 8589937032 B |
| DiffZip | 2.324초 | 0.0019초 | 0.0018초 | 0.19 | - | - | - | 720B |
물론 이 예제는 목록이 이미 정렬되어 있고 정수를 매우 효율적으로 비교할 수 있다는 점에서 이점을 얻을 수 있습니다.하지만 이것이 바로 요점입니다.만약 당신에게 유리한 상황이 있다면, 반드시 그것들을 이용해야 합니다.
몇 가지 추가 의견:비교 함수의 속도는 전체 성능과 분명히 관련되므로 최적화하는 것이 유리할 수 있습니다.이러한 유연성은 지퍼식 접근 방식의 이점입니다.게다가, 병렬화는 결코 쉽지 않고 노력과 간접비의 가치가 없을 수도 있지만, 저에게는 더 실현 가능한 것으로 보입니다.그럼에도 불구하고 공정 속도를 대략 2배 향상시키는 간단한 방법은 목록을 각각 두 개의 반으로 나누고(효율적으로 처리할 수 있는 경우) 부품을 병렬로 비교하는 것입니다. 하나는 앞에서 뒤로, 다른 하나는 역순으로 처리합니다.
저는 이 코드를 사용하여 백만 개의 레코드가 있는 두 개의 목록을 비교했습니다.
이 방법은 시간이 오래 걸리지 않습니다.
//Method to compare two list of string
private List<string> Contains(List<string> list1, List<string> list2)
{
List<string> result = new List<string>();
result.AddRange(list1.Except(list2, StringComparer.OrdinalIgnoreCase));
result.AddRange(list2.Except(list1, StringComparer.OrdinalIgnoreCase));
return result;
}
저는 서로 다른 데이터 세트를 비교하는 세 가지 방법을 비교했습니다.아래 테스트는 모든 숫자의 문자열 컬렉션을 만듭니다.0length - 1범위는 같지만 번호가 짝수인 다른 컬렉션입니다.그런 다음 첫 번째 컬렉션에서 홀수를 선택합니다.
제외 링크 사용
public void TestExcept()
{
WriteLine($"Except {DateTime.Now}");
int length = 20000000;
var dateTime = DateTime.Now;
var array = new string[length];
for (int i = 0; i < length; i++)
{
array[i] = i.ToString();
}
Write("Populate set processing time: ");
WriteLine(DateTime.Now - dateTime);
var newArray = new string[length/2];
int j = 0;
for (int i = 0; i < length; i+=2)
{
newArray[j++] = i.ToString();
}
dateTime = DateTime.Now;
Write("Count of items: ");
WriteLine(array.Except(newArray).Count());
Write("Count processing time: ");
WriteLine(DateTime.Now - dateTime);
}
산출량
Except 2021-08-14 11:43:03 AM
Populate set processing time: 00:00:03.7230479
2021-08-14 11:43:09 AM
Count of items: 10000000
Count processing time: 00:00:02.9720879
해시 집합 사용.더하다
public void TestHashSet()
{
WriteLine($"HashSet {DateTime.Now}");
int length = 20000000;
var dateTime = DateTime.Now;
var hashSet = new HashSet<string>();
for (int i = 0; i < length; i++)
{
hashSet.Add(i.ToString());
}
Write("Populate set processing time: ");
WriteLine(DateTime.Now - dateTime);
var newHashSet = new HashSet<string>();
for (int i = 0; i < length; i+=2)
{
newHashSet.Add(i.ToString());
}
dateTime = DateTime.Now;
Write("Count of items: ");
// HashSet Add returns true if item is added successfully (not previously existing)
WriteLine(hashSet.Where(s => newHashSet.Add(s)).Count());
Write("Count processing time: ");
WriteLine(DateTime.Now - dateTime);
}
산출량
HashSet 2021-08-14 11:42:43 AM
Populate set processing time: 00:00:05.6000625
Count of items: 10000000
Count processing time: 00:00:01.7703057
특수 해시 집합 테스트:
public void TestLoadingHashSet()
{
int length = 20000000;
var array = new string[length];
for (int i = 0; i < length; i++)
{
array[i] = i.ToString();
}
var dateTime = DateTime.Now;
var hashSet = new HashSet<string>(array);
Write("Time to load hashset: ");
WriteLine(DateTime.Now - dateTime);
}
> TestLoadingHashSet()
Time to load hashset: 00:00:01.1918160
.Contains 사용
public void TestContains()
{
WriteLine($"Contains {DateTime.Now}");
int length = 20000000;
var dateTime = DateTime.Now;
var array = new string[length];
for (int i = 0; i < length; i++)
{
array[i] = i.ToString();
}
Write("Populate set processing time: ");
WriteLine(DateTime.Now - dateTime);
var newArray = new string[length/2];
int j = 0;
for (int i = 0; i < length; i+=2)
{
newArray[j++] = i.ToString();
}
dateTime = DateTime.Now;
WriteLine(dateTime);
Write("Count of items: ");
WriteLine(array.Where(a => !newArray.Contains(a)).Count());
Write("Count processing time: ");
WriteLine(DateTime.Now - dateTime);
}
산출량
Contains 2021-08-14 11:19:44 AM
Populate set processing time: 00:00:03.1046998
2021-08-14 11:19:49 AM
Count of items: Hosting process exited with exit code 1.
(Didnt complete. Killed it after 14 minutes)
결론:
- 크린
Except되었습니다.HashSets(n=20,000,000). - 용사를 합니다.
Where그리고.Contains▁ran다▁for.
HashSets에 대한 마지막 설명:
- 고유 데이터
- 재정의해야 합니다.
GetHashCode클래스 에는 (으)로 표시됩니다. - 구현에 따라 데이터 세트를 복사할 경우 최대 2배의 메모리가 필요할 수 있습니다.
HashSet를 사용하여 다른 HashSet을 복제하도록 최적화되었습니다.IEnumerable다른 더의 특수 ). HashSet, HashSet로 변환하는 것이 더 느립니다.
첫 번째 접근 방식:
if (list1 != null && list2 != null && list1.Select(x => list2.SingleOrDefault(y => y.propertyToCompare == x.propertyToCompare && y.anotherPropertyToCompare == x.anotherPropertyToCompare) != null).All(x => true))
return true;
중복 값이 문제가 없는 경우 두 번째 접근법:
if (list1 != null && list2 != null && list1.Select(x => list2.Any(y => y.propertyToCompare == x.propertyToCompare && y.anotherPropertyToCompare == x.anotherPropertyToCompare)).All(x => true))
return true;
존 스키트와 미겔 엠프의 대답은 모두 좋습니다.목록 요소의 순서가 중요한지 여부에 따라 달라집니다.
// take order into account
bool areEqual1 = Enumerable.SequenceEqual(list1, list2);
// ignore order
bool areEqual2 = !list1.Except(list2).Any() && !list2.Except(list1).Any();
한 줄:
var list1 = new List<int> { 1, 2, 3 };
var list2 = new List<int> { 1, 2, 3, 4 };
if (list1.Except(list2).Count() + list2.Except(list1).Count() == 0)
Console.WriteLine("same sets");
저는 두 리스트를 비교하는 일반적인 기능을 했습니다.
public static class ListTools
{
public enum RecordUpdateStatus
{
Added = 1,
Updated = 2,
Deleted = 3
}
public class UpdateStatu<T>
{
public T CurrentValue { get; set; }
public RecordUpdateStatus UpdateStatus { get; set; }
}
public static List<UpdateStatu<T>> CompareList<T>(List<T> currentList, List<T> inList, string uniqPropertyName)
{
var res = new List<UpdateStatu<T>>();
res.AddRange(inList.Where(a => !currentList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
.Select(a => new UpdateStatu<T>
{
CurrentValue = a,
UpdateStatus = RecordUpdateStatus.Added,
}));
res.AddRange(currentList.Where(a => !inList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
.Select(a => new UpdateStatu<T>
{
CurrentValue = a,
UpdateStatus = RecordUpdateStatus.Deleted,
}));
res.AddRange(currentList.Where(a => inList.Any(x => x.GetType().GetProperty(uniqPropertyName).GetValue(x)?.ToString().ToLower() == a.GetType().GetProperty(uniqPropertyName).GetValue(a)?.ToString().ToLower()))
.Select(a => new UpdateStatu<T>
{
CurrentValue = a,
UpdateStatus = RecordUpdateStatus.Updated,
}));
return res;
}
}
이것은 두 목록을 요소별로 쉽고 간단하게 비교할 수 있는 방법이라고 생각합니다.
x=[1,2,3,5,4,8,7,11,12,45,96,25]
y=[2,4,5,6,8,7,88,9,6,55,44,23]
tmp = []
for i in range(len(x)) and range(len(y)):
if x[i]>y[i]:
tmp.append(1)
else:
tmp.append(0)
print(tmp)
재미있을 수도 있지만, 이것은 저에게 효과가 있습니다.
string.Join("",List1) != string.Join("", List2)
이것이 여러분이 찾을 수 있는 최고의 솔루션입니다.
var list3 = list1.Where(l => list2.ToList().Contains(l));
언급URL : https://stackoverflow.com/questions/12795882/quickest-way-to-compare-two-generic-lists-for-differences
'sourcecode' 카테고리의 다른 글
| Node.js - 플랫폼에 구애받지 않는 방법으로 홈 디렉토리 찾기 (0) | 2023.05.29 |
|---|---|
| Angular 2 + CLI 프로젝트에 폰트 어썸을 추가하는 방법 (0) | 2023.05.29 |
| 지정된 파일이 추가된 커밋을 찾는 방법은 무엇입니까? (0) | 2023.05.29 |
| 파일 잠금을 확인하는 방법은 무엇입니까? (0) | 2023.05.29 |
| postgresql의 문자열 리터럴 및 이스케이프 문자 (0) | 2023.05.29 |