효율적인 목록 교차 알고리즘

효율적인 목록 교차 알고리즘

---

두 개의 목록이 주어지면 (반드시 정렬되지는 않음) 해당 목록의 교차점을 찾는 데 가장 효율적인 비 재귀 알고리즘은 무엇입니까?

---

첫 번째 목록의 모든 요소를 ​​해시 세트에 넣을 수 있습니다. 그런 다음 두 번째 항목을 반복하고 각 요소에 대해 해시를 확인하여 첫 번째 목록에 있는지 확인합니다. 그렇다면 교차 요소로 출력하십시오.

---

Bloom 필터를 살펴볼 수 있습니다. 요소가 집합의 구성원인지 여부에 대한 확률 적 대답을 제공하는 비트 벡터입니다. 교차 설정은 간단한 비트 AND 연산으로 구현할 수 있습니다. 널 교차가 많은 경우 Bloom 필터를 사용하면이를 빠르게 제거 할 수 있습니다. 그러나 실제 교차를 계산하려면 여기에 언급 된 다른 알고리즘 중 하나에 의존해야합니다. http://en.wikipedia.org/wiki/Bloom_filter

---

해싱없이 두 가지 옵션이 있다고 가정합니다.

• 순진한 방법은 각 요소를 다른 모든 요소와 비교하는 것입니다. O (n ^ 2)
• 또 다른 방법은 목록을 먼저 정렬 한 다음 반복하는 것입니다. O (n lg n) * 2 + 2 * O (n)

---

로부터 EViews의 기능 목록 (이,이 교차점을 계산합니다 DB의 용어로 '가입'인 경우) 복잡한 병합을 지원하고 조인 것으로 보인다. 이제 문서를 살펴보십시오 :-)

또한 eviews에는 자체 사용자 포럼이 있습니다.

---

세트 1로 이진 검색 트리를 O(log n)만들고 set2를 반복하고 BST m X O(log n)총계를 검색합니다.O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

---

C ++에서는 STL 맵을 사용하여 다음을 시도 할 수 있습니다.

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}

---

여기에 내가 생각해 낸 또 다른 가능한 해결책이 있습니다. 시간 복잡성과 추가 스토리지없이 O (nlogn)을 취합니다. 여기에서 확인할 수 있습니다 https://gist.github.com/4455373

작동 방식은 다음과 같습니다. 세트에 반복이 포함되어 있지 않다고 가정하고 모든 세트를 하나로 병합하고 정렬합니다. 그런 다음 병합 된 집합을 반복하고 각 반복에서 현재 인덱스 i와 i + n 사이에 하위 집합을 만듭니다. 여기서 n은 유니버스에서 사용할 수있는 집합의 수입니다. 반복 할 때 우리가 찾는 것은 우주의 집합 수와 같은 크기 n의 반복되는 시퀀스입니다.

i의 하위 집합이 n의 하위 집합과 같으면 i의 요소가 총 집합 수와 동일한 n 번 반복됨을 의미합니다. 그리고 어떤 세트에도 반복이 없기 때문에 각 세트에 해당 값이 포함되어 있으므로 교차점에 추가합니다. 그런 다음 인덱스를 i + 그것과 n 사이에 남은 것만 큼 이동합니다. 그 인덱스 중 어느 것도 반복되는 시퀀스를 형성하지 않기 때문입니다.

---

먼저 quicksort : O (n * log (n)를 사용하여 두 목록을 정렬합니다. 그런 다음 가장 낮은 값을 먼저 찾아서 목록을 비교하고 공통 값을 추가합니다. 예를 들어 lua에서) :

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

어떤는 O(max(n, m))곳 n과 m목록의 크기입니다.

편집 : 퀵 정렬은 주석에서 말했듯이 재귀 적이지만 비 재귀 구현 이있는 것처럼 보입니다.

---

사용 스킵 포인터 및 SSE 명령은 목록 교차로의 효율성을 향상시킬 수 있습니다.

---

자신 만의 간단한 해시 테이블이나 해시 세트를 구현하지 않겠습니까? 당신이 말한 것처럼 목록이 큰 경우 nlogn 교차를 피하는 것이 좋습니다.

데이터에 대해 미리 알고 있으므로 좋은 해시 함수를 선택할 수 있어야합니다.

---

I second the "sets" idea. In JavaScript, you could use the first list to populate an object, using the list elements as names. Then you use the list elements from the second list and see if those properties exist.

---

If there is a support for sets (as you call them in the title) as built-in usually there is a intersection method.

Anyway, as someone said you could do it easily (I will not post code, someone already did so) if you have the lists sorted. If you can't use recursion there is no problem. There are quick sort recursion-less implementations.

---

I got some good answers from this that you may be able to apply. I haven't got a chance to try them yet, but since they also cover intersections, you may find them useful.

---

In PHP, something like

function intersect($X) { // X is an array of arrays; returns intersection of all the arrays
  $counts = Array(); $result = Array();
  foreach ($X AS $x) {
    foreach ($x AS $y) { $counts[$y]++; }
  }
  foreach ($counts AS $x => $count) {
    if ($count == count($X)) { $result[] = $x; }
  }
  return $result;
}

---

From the definition of Big-Oh notation:

T(N) = O(f(N)) if there are positive constants c and n 0 such that T(N) ≤ cf(N) when N ≥ n 0.

Which in practice means that if the two lists are relatively small in size say something less 100 elements in each two for loops works just fine. Loop the first list and look for similar object in the second. In my case it works just fine because I won't have more than 10 - 20 max elements in my lists. However, a good solution is the sort the first O(n log n), sort the second also O(n log n) and merge them, another O(n log n) roughly speeking O(3 n log n), say that the two lists are the same size.

참고URL : https://stackoverflow.com/questions/497338/efficient-list-intersection-algorithm