목록을 효율적으로 비교하는 방법?

Question

현재 asp.net의 웹 응용 프로그램에서 작업하고 있습니다. 특정 API 호출에서는 ListA와 ListB의 ListB를 비교하여 ListA에 ListB의 List와 동일한 요소가 있는지 판별해야합니다. 즉, ListA가 ListB에 포함되어있는 경우입니다.

두 컬렉션 모두 EF-Code-First db의 Linq로 쿼리됩니다. ListB는 List 또는 none과 일치하는 하나를 가지며 둘 이상을가집니다. 최악의 경우 ListB에는 수백만 개의 요소가 있으므로 비교가 확장 가능해야합니다.

중첩 된 foreach 루프를 수행하는 대신 db를 작업하게하는 순수 linq 쿼리를 찾고 있습니다. 구조를 설명하기 위해

(내가 멀티 컬럼 인덱스를 고려하기 전에) : 자사의 EF 데이터베이스 때문에

//In reality Lists are queried of EF 
var ListA = new List<Element>(); 
var ListB = new List<List<Element>>(); 
List<Element> solution; 
bool flag = false; 
foreach (List e1 in ListB) { 
    foreach(Element e2 in ListA) { 
     if (e1.Any(e => e.id == e2.id)) flag = true; 
     else { 
      flag = false; 
      break; 
     } 
    } 
     if(flag) { 
      solution = e1; 
      break; 
     } 
} 

업데이트 구조

을 나는 관련 개체 구조를 제공 할 수 있습니다. 실제 코드를 게시 할 수 있는지 확실하지 않으므로이 예제는 여전히 일반적인 것입니다.

//List B 
class Result { 
     ... 
     public int Id; 

     public virtual ICollection<Curve> curves; 

     ... 
} 

class Curve { 
     ... 
     public int Id; 

     public virtual Result result; 
     public int resultId; 

     public virtual ICollection<Point> points; 
     ... 
} 
public class Point{ 
    ... 
    public int Id; 
    ... 
} 

(API를 호출 용) 컨트롤러는 우측 곡선 객체를 제공하고자합니다. 올바른 오브젝트를 식별하기 위해 필터 (ListA)가 제공됩니다 (실제로는 곡선 오브젝트 임) 이제 필터 (ListA)가 결과 (ListB)의 곡선 목록과 비교되어야합니다. 곡선은 두 포인트를 비교하는 것입니다. (그래서 목록 비교) 곡선에는 약 1 - 50 포인트가 있습니다. 결과는 약 500.000.000 개입니다. 곡선

모든 객체 (필터 포함)가 db에 대해 다시 쿼리되기 때문에 여기서 Object-Identity로 비교할 수 있습니다.

이 방법을 구현하는 방법을 찾고 있는데이 상황을 피하는 방법이 아닙니다.

(설명을 위해) (멀티 컬럼 인덱스를 사용하여 예() 테이블을 변경) :

class controller { 
    ... 
    public Response serveRequest(Curve filter) { 
     foreach(Curve c in db.Result.curves) { 
       if(compare(filter.points , c.points)) return c; 

     } 
    } 
} 

Answer 1

을이 시도 : 당신이 요소

을 원하는 경우,

bool isIn = ListB.Any(x=>x.Count==ListA.Count && ListA.All(y=>x.Contains(y))); 

또는

var solution = ListB.FirstOrDefault(x=>x.Count==ListA.Count && ListA.All(y=>x.Contains(y))); 

Answer 2

사용 Except:

public static bool ContainsAllItems(IList<T> listA, IList<T> listB) 
    { 
     return !listB.Except(listA).Any(); 
    } 

위의 방법은 listA에 listB의 모든 요소가 포함되어 있는지 여부를 알려주고 복잡성은 O (n * m) 접근보다 훨씬 빠릅니다.

Answer 3

내가 당신을 위해 뭔가를 가지고 : 전직

var listALookup = listA.ToLookup(item => item.Id); 
var result = listB.FirstOrDefault(childList => childList.Count == listA.Count && childList.All(childListItem => listALookup.Contains(childListItem.Id))); 

Lookup.Contain을 비교하기 전에

var db = new MyContext(); 

var a = db.LoadList(); // or whatever 
var b = new List<IQueryable<Entities>>(db.LoadListOfLists()/*or whatever*/); 

b.Any(x => x.Count.Equals(a.Count) & x.All(y => a.Any(z => z.Id == y.Id))); 

Answer 4

성능 문제이기 때문에, 당신의 챠트를 변환 제안이/사전을 조회 할 수는 O (1) 목록 동안.O (n)

더 나은 옵션은 불필요한 데이터로드를 줄이기 위해 db 수준에서이 비교를 수행하는 것입니다.