동일한 ID로 수백만 개의 항목이 포함 된 2 개의 거대한 목록을 필터링하는 방법 [중복]

Question

여기에 수백만 개 이상의 항목이있는 2 개의 목록이 있습니다. 둘 다 동일한 ID를 가진 동일한 항목이 있습니다. ID는 문자열입니다. 같은 아이디가 아닌 아이템 만 필요합니다. 그러나 나는 더 나은 솔루션과 높은 영구성이 있어야한다고 확신합니다.

    List<Transaction> differentList = new ArrayList<>();

    for(Transaction tx : foundTransactions ){
        for(Transaction aTx : ArchivedTransactions) 
        {
            if(!tx.getId().equalsIgnoreCase(aTx.getId()) ){
                differentList .add(tx);
            }
        }
    }

나는 스트림을 사용하려고했지만 그렇게 할 수 없었다. 스트림 API가 더 좋을 것 같습니다. 개선 사항이 있으면 제안 해주십시오.

Answer 1

HashMap다음과 같이 첫 번째 로 변환 해 볼 수 있습니다 .

Set<String> collect = ArchivedTransactions.stream().map(i -> i.getId().toLowerCase())
                                           .collect(Collectors.toSet());

for(Transaction tx : foundTransactions )
    if(!collect.contains(tx.getId()))
       differentList.add(tx);

가 Collectors.toSet()다시 발생 HashSet. 코드를 단순화하여 다음을 수행 할 수 있습니다.

Set<String> collect = ArchivedTransactions.stream().map(i -> i.getId().toLowerCase())
                                          .collect(Collectors.toSet());

List<Transaction> differentList = foundTransactions.stream()
                                                   .filter(tx -> !collect.contains(tx.getId()))
                                                   .collect(Collectors.toList())

IDs첫 번째 HashSet단계를 중간 단계 로 추가하면 전체적으로 훨씬 더 복잡한 시간을 얻을 수 있습니다 ( 소스 ).

HashSet 작업의 시간 복잡성 : HashSet의 기본 데이터 구조는 해시 테이블입니다. 따라서 HashSet의 추가 , 제거 및 조회 (메소드 포함) 작업에 대한 시간 복잡도를 상각 (평균 또는 일반적인 경우)하는 데 O (1) 시간 이 걸립니다 .

따라서, 전체 time complexity의 "HashMap"용액 것 O(N + M), 여기서 N및 M리스트의 요소 수를 시작 ArchivedTransactions하고 foundTransactions각각. 그럼에도 불구하고 space-wise추가 구조를 갖는 대가를 지불하게됩니다.

솔루션 space-wise이 더 좋지만 시간이 가장 복잡합니다. 경우 N = M솔루션의 시간 복잡도는 O(N^2), 반면에 해결책은 HashSet될 것이다 O(2N), 따라서 O(N). 이것은 큰 차이입니다.

그냥

Set<Transaction> result = new LinkedHashSet<>();
result.addAll(foundTransactions);
result.addAll(ArchivedTransactions);

명시 적으로 요청했기 때문에 단독으로 는 작동하지 않습니다.

!tx.getId().equalsIgnoreCase(aTx.getId())

Answer 2

내 마음에 떠오르는 가장 간단한 해결책 Set은 중복 요소를 자동으로 삭제하는를 사용하는 것 입니다.

Set<Transaction> result = new LinkedHashSet<>();
result.addAll(foundTransactions);
result.addAll(ArchivedTransactions);

//If you want to get a List<Transaction>
List<Transaction> differentList = new ArrayList<>(result);

참고 : 내가 사용하고 LinkedHashSet삽입 순서를 유지 할 수 있습니다. 게재 신청서가 중요하지 않은 경우 HashSet.