두 목록을 조정하십시오.

Question

그래서 서로 다른 형식과 구조로 조정해야하는 두 가지 목록이 있습니다. 기본적으로 집합 B는 집합 A에있는 내용과 일치해야하지만 집합 B에있는 기존 항목의 상태를 보존하고 집합 A에있는 항목으로 덮어 쓰지는 않습니다.

참고로 목록은 실제로 목록을 의미하지 않습니다 . "목록"은 직선 배열에서지도에 이르는 두 가지 형태로 제공됩니다. 모두 표준 요소 반복자를 사용하여 요소에 액세스합니다. 나는 일반적으로 처리

방법이 작동하고 내가 그것을 수행하는 생각할 수있는 유일한 방법입니다

for item in listA 
    if listB contains item 
    mark item in list B as visited 
    else 
    add item to list b 

for item in listB 
    if visited is true 
     continue 
    else 
     add item to removeList 

for item in removeList 
    remove item from list B 

...과 같이합니다. 나는 반복해야 할 반복을 얼마나 많이 반복하는지에 대해 싫어한다. 그러나 반복자를 사용하고 있기 때문에 목록을 검사하는 동안 목록에서 아무 것도 제거 할 수 없으며 목록에서 세 번째 제거 목록에 추가해야합니다.

잠정적 인 답은 속도와 메모리 사용 공간이 코드를 작성하는 것이 얼마나 쉬운지를 명심하십시오.

내 질문은 정말이까지 내려 간다. 내가 생각할 수없는 더 좋은 방법이 있는가?

나는 어떤 해결책이 아마도 언어 불가 지론이 될 것이라고 생각하지만, 나는 C++/C FWIW에있다.

감사합니다.

Answer 1

여기보다 효율적으로 할 수 그것을 할 수있는 또 다른 방법 :

removeList = listB 

for item in listA 
    if listB contains item 
    remove item from removeList 
    else 
    add item to listB 

for item in removeList 
    remove item from listB 

그래서 그 대신 아무것도에서 removeList을 구축, 그것은 모든 것을 시작합니다 후 제거 항목이 있습니다.

또한 실제 항목이 아닌 removeList가 색인을 저장함으로써 더 효율적으로 만들 수 있습니다. 항목이 초기 루프에서 listB의 끝에 추가되고 항목이 역순으로 제거되는 한, 색인은 여전히 ​​유효해야합니다.

removeList을 유지할 부울 배열로 대체하면 사실 더 간단합니다.

initialise all itemsToKeep to false 
savedListLength = length of listB 

for item in listA 
    offset = find item in listB 
    if found 
    mark itemsToKeep[offset] as true 
    else 
    add item to listB 

for offset from savedListLength-1 down to 0 
    if itemsToKeep[offset] is false 
    remove the offset from listB 

이 처음 removeList에 아무것도 복사 할 필요가 피할 수 : 그래서 알고리즘은 다음과 같이된다. itemsToKeep 배열의 비용은 분명히 알고리즘의 특정 항목을 추적하는 데 사용하는 것보다 나쁘지 않습니다.

어느 정도까지는 가장 적합한 알고리즘이 목록 (즉, 벡터 또는 링크 된 목록 등)의 형태에 따라 다를 수 있습니다.하지만 내 접근 방식이 어느 쪽이든 더 효과적 일 수 있다고 생각합니다.