Meilleur pour la liste structure de données d'objets fréquemment sollicités

Question

J'ai une liste d'objets dire, Liste. La classe Entity a une méthode equals, sur quelques attributs (règle métier) pour différencier un objet Entity de l'autre.

La tâche que nous portons habituellement sur cette liste est de supprimer tous les doublons quelque chose comme ceci:

List<Entity> noDuplicates = new ArrayList<Entity>(); 
for(Entity entity: lstEntities) 
{ 
    int indexOf = noDuplicates.indexOf(entity); 
    if(indexOf >= 0) 
    { 
      noDuplicates.get(indexOf).merge(entity); 
    } 
    else 
    { 
      noDuplicates.add(entity); 
    } 
} 

Maintenant, le problème que j'ai observé est que cette partie du code, ralentit vers le bas considérablement dès que la liste a des objets plus de 10000.Je comprends arraylist fait une recherche (N).

Y at-il une alternative plus rapide, utiliser HashMap n'est pas une option, parce que l'unicité de l'entité est construite sur 4 de ses attributs ensemble, il serait fastidieux de mettre la clé elle-même dans la carte? va trier définir l'aide dans l'interrogation plus rapide?

Merci

Answer 1

Maintenant, le problème que j'ai observé est que cette partie du code, ralentit considérablement dès que la liste a des objets plus 10000.I comprendre arraylist fait une recherche o (N).

L'algorithme que vous avez publié est en fait pire que O (N)

• Itère la liste d'entrée lstEntities - O (N)
• au sein de cette boucle, vous appelez ArrayList.indexOf(T) qui doit scanner la liste - O (N) à nouveau

vous algorithme est en fait O (N^2) puisque vous êtes potentiellement numérisez la liste deux fois dans une boucle.

On dirait que vous ce que vous voulez faire est en fait deux opérations:

1. De l'entrée List, supprimer les doublons
2. Lorsque vous trouvez les doublons, les entités « fusion ».

Vous pouvez le faire en analysant la liste une seule fois, plutôt que dans des boucles imbriquées. Je recommande de diviser votre Entity pour déplacer les champs qui "identifient" une entité dans un autre type, comme ID, ou tout au moins d'ajouter une méthode getID() qui peut retourner ces champs groupés dans un seul type. De cette façon, vous pouvez facilement créer une carte entre les deux types pour pouvoir fusionner des entités avec des identités «en double». Cela pourrait ressembler à ceci:

Map<ID, Entity> map = new HashMap<ID, Entity>(inputList.size()); 
for (Entity e : inputList) { 
    Entity existing = map.get(e.getID()); 
    if (existing == null) { 
     //not in map, add it 
     map.put(e.getID(), e); 
    } 
    else { 
     existing.merge(e); 
    } 
} 

la liste Itération est O (n) tandis que HashMap.get(K) est une opération constante de temps.

Answer 2

Une idée est d'utiliser un Set au lieu d'un List, il n'y a pas de doublons dans un Set. Pour supprimer les doublons dans une liste, vous pouvez ajouter simplement le List à une nouvelle Set

List<Entity> list = //your list. 
Set<Entity> set = new HashSet<Entitiy>(); 
set.addAll(list); 

Mais là encore, peut-être il y a une raison pour utiliser un List en premier lieu? Sinon, vous pouvez utiliser un Set à la place, et ne pas avoir à vous soucier des doublons.

EDIT

Il n'y a pas de référence d'index des éléments dans un Set (par rapport à un List, où vous pouvez faire get(int index)). Les éléments d'un Set flottent sans point de référence spécifique.

Si vous avez besoin de trouver un particulier, vous devez itérer tous. Si ce n'est pas correct et/ou vous ne pouvez pas être sans référence indexé - qui permet de get(int index) et remove(int index) - Je suppose que Set est pas une option pour vous.

Answer 3

Au lieu d'une structure de liste, vous pouvez utiliser un ensemble (plus approprié si vous êtes préoccupé par le caractère unique entité), comme Lars a suggéré. De plus, si la performance est un problème, je regarderais en utilisant un TreeSet et implémenterais un Comparator pour comparer des instances d'entité basées sur leurs attributs. La structure arborescente permettra des opérations d'insertion, de suppression et de récupération rapides (complexité logarithmique).

Answer 4

Tout dépend de ce que le fonctionnement merge fait. Est-ce que merge change l'un des attributs qui sont comparés lorsque vous faites equals? Sinon, vous serez étonné de voir combien plus vite il sera si vous faites ceci:

D'abord, définir un hashCode pour votre classe Entity qui est compatible avec votre définition de equals.Une façon courante de le faire est:

public int hashCode() { 
    // assuming the four attributes that determine equality are called 
    // attrFoo, attrBar, attrBaz, and attrQux 
    int hash = 1; 
    hash += attrFoo == null ? 0 : attrFoo.hashCode(); 
    hash *= 37; 
    hash += attrBar == null ? 0 : attrBar.hashCode(); 
    hash *= 37; 
    hash += attrBaz == null ? 0 : attrBaz.hashCode(); 
    hash *= 37; 
    hash += attrQux == null ? 0 : attrQux.hashCode(); 

    return hash; 
} 

Ensuite, utilisez un HashMap afin que vous puissiez trouver ces choses:

Map<Entity, Entity> map = new HashMap<Entity, Entity>(); 
for(Entity entity: lstEntities) { 
    if (map.containsKey(entity)) { 
    map.get(entity).merge(entity); 
    } else { 
    map.put(entity, entity); 
    } 
} 
return map.values(); // or keys(). Whichever. 

Je dois souligner que je me sens un peu sale écrire le code ci-dessus, parce que vous ne devriez vraiment pas faire des clés qui ne sont pas immuables, mais cela fonctionnera beaucoup plus vite que ce que vous faites maintenant.

Answer 5

À moins que vous n'ayez une raison d'avoir besoin de la commande d'une liste, vous seriez probablement mieux avec un ensemble - spécifiquement, un HashSet.

Je vois votre souci d'utiliser une collection hachée parce que "l'unicité de l'entité est construite sur 4 de ses attributs ensemble", mais cela est facilement surmonté. Il vous suffit de définir une méthode hashcode() compatible avec votre méthode equals() existante, puis vous pouvez insérer vos entités dans un Set et, comme effet secondaire magique, ne plus jamais avoir à supprimer les doublons.

Answer 6

Deux étapes simples pour un O (N * Log (N)) algorithme:

1. Trier la liste en utilisant un comparateur basé sur les quatre domaines importants
2. itérer sur la liste la comparaison de chaque élément à la Dans la liste suivante, s'ils sont égaux, fusionnez-les et supprimez-en un.