Comment filtrer 2 énormes listes contenant des millions d’éléments avec le même identifiant [dupliquer]

Dec 04 2020

Voici ma 2 liste avec plus de millions d'articles. Les deux ont les mêmes éléments avec le même identifiant. L'ID est en chaîne. Je n'ai besoin que de l'article qui n'est pas la même pièce d'identité. Mais je suis sûr qu'il doit y avoir une meilleure solution et avec une grande permanence: -

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

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

J'ai essayé d'utiliser stream mais je n'ai pas pu le faire. Je suppose qu'avec l'API de flux devrait être mieux. Veuillez me suggérer des améliorations.

Réponses

4 dreamcrash Dec 04 2020 at 19:34

Vous pouvez essayer de le convertir en un HashMappremier, quelque chose comme:

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

Les Collectors.toSet()retours a HashSet. Vous pouvez simplifier le code pour:

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

L'ajout du IDspremier dans une HashSetétape intermédiaire vous fournira un temps de complexité global bien meilleur puisque ( source ):

Complexité temporelle des opérations HashSet: La structure de données sous-jacente pour HashSet est hashtable. Donc, amortir la complexité du temps (cas moyen ou habituel) pour ajouter , supprimer et rechercher (méthode contient) l'opération de HashSet prend du temps O (1) .

Par conséquent, l'ensemble time complexityde la "HashMap"solution sera O(N + M), où Net Mcommencer le nombre d'éléments dans les listes ArchivedTransactionset foundTransactions, respectivement. Néanmoins, space-wisevous paierez le prix d'avoir cette structure supplémentaire.

Votre solution space-wiseest meilleure, mais avec la pire complexité temporelle. Si N = Mla complexité temporelle de votre solution est O(N^2), alors que la solution avec le HashSetserait O(2N), par conséquent O(N). C'est une grande différence.

Faire juste

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

seul ne fonctionnera pas, car vous avez explicitement demandé:

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

La solution la plus simple qui me vient à l'esprit consiste à utiliser un Setqui supprime automatiquement les éléments en double.

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

Remarque: j'ai utilisé LinkedHashSetpour conserver l'ordre d'insertion. Si l'ordre d'insertion n'a pas d'importance pour vous, vous pouvez utiliser HashSet.