한 목록을 다른 목록과 동일하게 만드는 효율적인 알고리즘은 무엇입니까?

Question

목록 A가 목록 B와 완전히 똑같이 필요하다고 가정 해 봅시다. B가 가지고 있지만 A에 추가 할 필요가없는 모든 객체는 A가 ​​있지만 B가 아닌 모든 객체는 있어야합니다. A에서 제거했습니다.

내가 이것을 필요로하는 이유는 파일에 저장하는 플레이어의 ArrayList가 있기 때문입니다. Player의 속성을 업데이트 할 때마다 Players의 ArrayList를보고 저장하는 메서드를 호출하여 변경 내용을 파일에 저장합니다. 이 작업은 ArrayList에 Players에 대한 참조가 있기 때문에 가능합니다.

그러나 목록에서 플레이어를 검색 할 때마다 먼저 저장된 파일을 읽음으로써 목록을 업데이트합니다. 이렇게하면 모든 참조가 완전히 새로운 객체로 바뀝니다. 이렇게 한 후에 이전에 가져온 사용자를 변경하고 저장하려고하면 플레이어의 새 인스턴스가 변경된 인스턴스 대신 저장됩니다.

리스트를 다른 솔루션과 동일하게 만드는 좋은 알고리즘이 생길까요? 또는 거기에 참조를 유지하면서 전체 목록을 업데이트하는 더 좋은 방법이 있습니까?

업데이트 : 업데이트 된 솔루션은 O (nlogm) 시간으로 실행됩니다. 대상의 각 요소를 반복하고 소스에서 해당 요소를 검색합니다. 발견되면 소스에서 제거됩니다. 그렇지 않은 경우 대상에서 제거됩니다. 그런 다음 소스의 나머지 요소를 목적지에 추가하십시오. 목록을 물론 정렬해야하지만 파일에서 가져온 목록은 내가 추가 할 때 정렬되기 때문에 이미 정렬됩니다.

import java.util.Collections; 
import java.util.Comparator; 
import java.util.List; 

public class CopyList { 
    public static void copyList(List dest, List src) { 
     copy(dest, src); 

     // the remaining elements in src list will be those that were originally 
     // in src but not in dest and so they need to be added 
     dest.addAll(src); 
    } 

    public static void copyList(List dest, List src, Verify v) { 
     copy(dest, src); 

     // the remaining elements in src list will be those that were originally 
     // in src but not in dest and so they need to be added 
     addAll(dest, src, v); 
    } 

    public static void copyList(List dest, List src, Comparator c) { 
     copy(dest, src, c); 

     // the remaining elements in src list will be those that were originally 
     // in src but not in dest and so they need to be added 
     dest.addAll(src); 
    } 

    public static void copyList(List dest, List src, Comparator c, Verify v) { 
     copy(dest, src, c); 

     // the remaining elements in src list will be those that were originally 
     // in src but not in dest and so they need to be added 
     addAll(dest, src, v); 
    } 

    private static void copy(List dest, List src) { 
     // go through dest list to search if every element is in the new list 
     // travel backwards through dest because we will be removing elements from it 
     for(int i = dest.size()-1; i >= 0 ; i--) { 
      int src_i = Collections.binarySearch(src, dest.get(i)); 
      if(src_i >= 0) 
       // if element is found in src list, remove it from src list 
       src.remove(src_i); 
      else 
       // if element is NOT found in src list, remove it from dest list 
       dest.remove(i); 
     } 
    } 

    private static void copy(List dest, List src, Comparator c) { 
     // go through dest list to search if every element is in the new list 
     // travel backwards through dest because elements might be removed 
     for(int i = dest.size()-1; i >= 0 ; i--) { 
      int src_i = Collections.binarySearch(src, dest.get(i), c); 
      if(src_i >= 0) 
       // if element is found in src list, remove it from src list 
       src.remove(src_i); 
      else 
       // if element is NOT found in src list, remove it from dest list 
       dest.remove(i); 
     } 
    } 

    private static void addAll(List dest, List src, Verify v) { 
     // verify each element in src list before adding it to dest list 
     for(Object o: src) 
      if(v.verify(o)) 
       dest.add(o); 
    } 
} 

Answer 1

가장 쉬운 해결책은 목록 B의 복사본을 만드는 것이 아니겠습니까? 이것은 복잡한 알고리즘보다 훨씬 적은 시간과 노력을 필요로하는 기본 배열의 복사본을 생성하는 것만을 포함합니다.

Answer 2

그러나 목록에서 플레이어를 검색 할 때마다 먼저 저장된 파일을 읽음으로써 목록을 업데이트합니다.

왜이 작업을 수행하고 있습니까? 메모리 내 사본을 검색하는 것이 훨씬 더 합리적입니다.

아, 그리고 a가 b과 같은 것들을 포함 만들 수있는 정말 쉬운 방법이 :

a = b; 

Answer 3

내가 돌아 단계 및 프로그램의 디자인에 대해 생각하는 것입니다. 모든 플레이어를 관리하고 클래스를 업데이트하고 업데이트하여 참조를 전달하는 것이 더 합리적 일 것 같습니다. 그렇다면 을 다른 곳에서는 플레이어에 대한 참조를 보유하지 말고 PlayerManager (또는 호출 할 내용)에 대한 참조를 보유하고 쿼리하여 Players를 얻으십시오.

이것은 하나의 정식 목록을 제공 할 것이므로 오래된 참조에 대해 걱정할 필요가 없습니다.

Answer 4

여기에 다른 제출에 동의하는 것은 귀하의 어플리케이션에서는 불필요한 것으로 보이지만, n^2 시간보다 나은 것으로 기술하는 알고리즘을 원한다면 관심이 없습니다. (또한 n * 로그 N 시간)

sort list users (n log n) 
sort list new_users (n log n) 
iterate through users and new_users in parallel, adding or removing items from users as necessary (n) 

Answer 5

당신이 당신의 목록에 대한 HashSet 사용을 고려 했습니까? 이렇게하면 addAll()을 수행하고 이러한 목록을 통합 할 수 있습니다. 원래 순서를 유지하려면 LinkedHashSet을 사용하십시오. 훨씬 빨라 졌을거야.플레이어 이름에 해시를 반환하려면 Player 클래스에서 hashCode()을 재정의해야합니다.

Answer 6

목록 대신 집합을 사용하면 해시 충돌이 없다고 가정하고 O (1) 시간 복잡도가 높아집니다.

for(User u : new_users) { 
    if (!users.contains(u)) { 
     users.add(u); 
    } 
} 
for(User u : users) { 
    if (!new_users.contains(u)) { 
     users.remove(u); 
    } 
}