배열간에 일치하는 항목을 찾는 가장 빠른 방법은 무엇입니까?

현재 모든 정수 요소가 서로 일치하는지 테스트하여 일치하는 정수 요소를 찾습니다. 배열은 자체 세트 내에 중복을 포함하지 않습니다. 또한 배열이 항상 동일한 길이는 아닙니다. 이 속도를 높이기위한 트릭이 있습니까? 저는 수천 번하고 있습니다. 그래서 C#에있는 제 프로그램에서 병 목이되기 시작합니다.배열간에 일치하는 항목을 찾는 가장 빠른 방법은 무엇입니까?

출처

2010-04-10 John Sheares

두 배열에 존재하는 모든 정수의 고유 한 목록을 원한다고합니까? – Thomas

Thomas의 코멘트에 추가하려면 배열이 정렬되어 있습니까? –

그것은 그것을 놓는 또 다른 방법입니다. 두 세트에서 공통된 고유 한 목록입니다. 예, 그들은 명령을받습니다. –

사용하십시오 HashSet의

var set = new HashSet<int>(firstArray); 
set.IntersectWith(secondArray);

세트는 이제 두 배열에 존재하는 경우에만 값이 포함되어 있습니다.

var query = firstArray.Intersect(secondArray);

를 또는 배열이 이미 정렬하는 경우 당신은 두 개의 배열을 통해 자신을 반복 할 수 있습니다 :

출처

2010-04-10 18:51:19 Josh

당신이 원하는 것 같아요. 인터체인지보다는. 유니온 –

아 뇌의 방귀! 감사. 나는 그것을 편집했다. – Josh

IntersectWith로 HashSet을 시도한 결과, 모든 요소를 반복하는 것보다 두 배 느립니다. –

당신은 LINQ를 사용할 수

int[] a = { 1, 3, 5 }; 
int[] b = { 2, 3, 4, 5 }; 

List<int> result = new List<int>(); 
int ia = 0; 
int ib = 0; 
while (ia < a.Length && ib < b.Length) 
{ 
    if (a[ia] == b[ib]) 
    { 
     result.Add(a[ia]); 
     ib++; 
     ia++; 
    } 
    else if (a[ia] < b[ib]) 
    { 
     ia++; 
    } 
    else 
    { 
     ib++; 
    } 
}

출처

2010-04-10 19:00:35

@ 마크 : 귀하의 코드는 배열이 정렬되어 있다고 조용히 가정합니다. – Vlad

John은 배열이 위의 주석에 정렬되어 있다고 이미 선언했습니다. –

을 같은 비교 프로그램에서 병목 현상 인 경우, 아마도 부적절한 데이터 구조를 사용하고있을 것입니다. 가장 간단한 방법은 데이터를 정렬 된 상태로 유지하는 것입니다. 그런 다음 공통 항목을 찾으려면 두 배열을 한 번만 통과해야합니다. 또 다른 옵션은 데이터를 HashSet에 보관하는 것입니다.

출처

2010-04-10 19:01:57 Vlad

배열간에 일치하는 항목을 찾는 가장 빠른 방법은 무엇입니까?

답변

관련 문제