Jak odfiltrować 2 ogromne listy z milionami pozycji o tym samym identyfikatorze [duplikat]

Dec 04 2020

Oto moja lista 2 z ponad milionami pozycji. Oba mają te same elementy z tym samym identyfikatorem. Identyfikator jest w ciągu. Potrzebuję tylko przedmiotu, który nie jest tym samym ID. Tak zrobiłem. Ale jestem pewien, że musi istnieć lepsze rozwiązanie o dużej trwałości: -

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

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

Próbowałem użyć strumienia, ale nie mogłem tego zrobić. Myślę, że ze strumieniowym API powinno być lepiej. Proszę o propozycje ulepszeń.

Odpowiedzi

4 dreamcrash Dec 04 2020 at 19:34

Możesz spróbować przekonwertować go na HashMappierwszy, na przykład:

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()Zwraca HashSet. Możesz uprościć kod, aby:

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())

Dodanie IDspierwszego do a HashSetjako kroku pośredniego zapewni znacznie lepszy ogólny czas złożoności, ponieważ ( źródło ):

Złożoność czasowa operacji HashSet: Podstawowa struktura danych dla HashSet jest hashtable. Więc zamortyzuj (średni lub zwykły przypadek) złożoność czasową dla dodawania , usuwania i wyszukiwania (metoda zawiera) działanie HashSet zajmuje O (1) czasu.

W związku z tym, ogólna time complexityz "HashMap"rozwiązania będzie O(N + M), gdzie Ni Mrozpocząć liczbę elementów w listach ArchivedTransactionsi foundTransactionsodpowiednio. Niemniej jednak space-wisezapłacisz cenę posiadania tej dodatkowej struktury.

Twoje rozwiązanie space-wisejest lepsze, ale z największą złożonością czasową. Jeśli N = Mzłożoność czas rozwiązania jest O(N^2), natomiast rozwiązanie z HashSetbyłoby O(2N)stąd O(N). To ogromna różnica.

Robić sprawiedliwie

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

sam nie zadziała, ponieważ wyraźnie zażądałeś:

!tx.getId().equalsIgnoreCase(aTx.getId())
3 LiveandLetLive Dec 04 2020 at 19:33

Najprostszym rozwiązaniem, jakie przychodzi mi do głowy, jest użycie narzędzia, Setktóre automatycznie odrzuca zduplikowane elementy.

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);

Uwaga: wcześniej LinkedHashSetzachowałem zamówienie reklamowe. Jeśli kolejność reklamowa nie ma dla Ciebie znaczenia, możesz użyć HashSet.