algorithm - 알고리즘 - weighted hamming distance




두 데이터 목록의 차이점을 확인하는 방법 (4)

이것은 CS 사람들이 이론을 비추는 운동입니다.

요소가있는 컨테이너가 2 개 있다고 가정 해 보겠습니다. 폴더, URL, 파일, 문자열, 정말 중요하지 않습니다.

추가 및 제거 된 알고리즘을 계산하는 알고리즘은 무엇입니까?

알림 :이 문제를 해결할 수있는 방법이 여러 가지라면 답변 당 하나를 게시하여 분석하고 투표 할 수 있도록하십시오.

편집 : 모든 답변은 4 개의 컨테이너로 문제를 해결합니다. 초기 2 개만 사용할 수 있습니까?


고유 항목에 대한 두 개의 목록이 있고 순서가 중요하지 않다고 가정하면 두 가지를 모두 목록이 아닌 집합으로 생각할 수 있습니다

하나의 원으로리스트 A가 있고 다른 하나가리스트 B 인 벤 다이어그램을 생각하면,이 둘의 교차점은 상수 풀입니다.

이 교차로에있는 모든 요소를 ​​A와 B에서 모두 제거하고 A에 남아있는 것이 모두 삭제되고 B에 남아있는 것이 모두 추가됩니다.

따라서 A를 반복하면서 B의 각 항목을 찾습니다. 찾으면 A와 B에서 모두 제거합니다.

그러면 A는 삭제 된 항목 목록이고 B는 추가 된 항목 목록입니다.

내 생각 엔 ..

[편집] 새로운 "유일한 2 컨테이너"제한으로, 여전히 동일하게 유지됩니다 :

foreach( A ) { 
  if( eleA NOT IN B ) {
    DELETED
  }
}
foreach( B ) {
  if( eleB NOT IN A ) {
    ADDED
  }
}

그런 다음 새 목록을 작성하거나 이전 목록을 파기하지는 않지만 이전 예제처럼 더 짧은 목록을 반복하고 더 오래 요소를 제거 할 수 있습니다. 여기에서는 두 목록을 모두 수행해야합니다.

내 첫 번째 솔루션은 4 개의 컨테이너를 사용하지 않았다고 주장하지만, 2 개의 컨테이너를 파괴했습니다.


나는 이것을 잠시 동안하지는 않았지만, 알고리즘이 이렇게 될 것이라고 믿습니다 ...

sort left-list and right-list
adds = {}
deletes = {}
get first right-item from right-list
get first left-item from left-list
while (either list has items)
  if left-item < right-item or right-list is empty
    add left-item to deletes
    get new left-item from left-list
  else if left-item > right-item or left-list is empty
    add right-item to adds
    get new right-item from right-list
  else
    get new right-item from right-list
    get new left-item from left-list

오른쪽 목록과 왼쪽 목록과의 관계에서 삭제 항목에는 제거 된 항목이 포함되고 추가에는 이제 새 항목이 포함됩니다.


목록의 객체가 "고유"합니까? 이 경우 먼저 두 개의 맵 (해시 맵)을 작성한 다음 목록을 스캔하고 맵의 모든 오브젝트를 검색합니다.

map1
map2
removedElements
addedElements

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}
list2.each |item|
{
    addedElements.add(item) unless map1.contains?(item)
}

Ruby와 Java : 끔찍한 메타 언어 혼합에 대해 유감스럽게 생각합니다.

결국 removeElements 는 list1에 속한 요소를 포함하지만 list2는 포함하지 않으며 addedElements 는 list2에 속한 요소를 포함합니다.

지도 / 사전의 검색이 일정하다고 생각되기 때문에 전체 연산의 비용은 O (4 * N)입니다. 반면에 목록의 각 요소를 선형 / 이진 검색하면 O (N ^ 2)가됩니다.

편집 : 두 번째 루프에 마지막 체크를 이동 생각 두 번째 루프 중 하나를 제거 할 수 있습니다 ...하지만 그건 못생긴 ... :)

list1.each |item|
{
    map1.add(item)
}
list2.each |item|
{
    map2.add(item)
    addedElements.add(item) unless map1.contains?(item)
}
list1.each |item|
{
    removedElements.add(item) unless map2.contains?(item)
}

조가 말했던 것. 목록이 너무 커서 메모리에 맞지 않는 경우 외부 파일 정렬 유틸리티 또는 병합 정렬을 사용하십시오.







edit-distance