Comment filtrer 2 énormes listes contenant des millions d’éléments avec le même identifiant [dupliquer]
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
Vous pouvez essayer de le convertir en un HashMap
premier, 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 IDs
premier 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 complexity
de la "HashMap"
solution sera O(N + M)
, où N
et M
commencer le nombre d'éléments dans les listes ArchivedTransactions
et foundTransactions
, respectivement. Néanmoins, space-wise
vous paierez le prix d'avoir cette structure supplémentaire.
Votre solution space-wise
est meilleure, mais avec la pire complexité temporelle. Si N = M
la complexité temporelle de votre solution est O(N^2)
, alors que la solution avec le HashSet
serait 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())
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é LinkedHashSet
pour conserver l'ordre d'insertion. Si l'ordre d'insertion n'a pas d'importance pour vous, vous pouvez utiliser HashSet
.