Le moyen le plus efficace de voir si ArrayList contient un objet en Java

Question

J'ai une ArrayList d'objets en Java. Les objets ont quatre domaines, dont deux que j'avais utiliser pour examiner l'objet est égale à une autre. Je suis à la recherche de la manière la plus efficace, compte tenu de ces deux champs, pour voir si le tableau contient l'objet.

La clé est que ces classes sont générés sur la base d'XSD objets, donc je ne peux pas modifier les classes elles-mêmes pour remplacer l' .equals.

Est-il mieux que simplement en parcourant manuellement et en comparant les deux champs pour chaque objet et à la rupture quand on les trouve? Qui semble tellement en désordre, à la recherche d'une meilleure façon.

Edit: la liste de tableaux vient d'une réponse SOAP qui est unmarshalled dans les objets.

Answer 1

Il dépend de la façon dont efficace, vous avez besoin que les choses soient. Simplement de parcourir la liste à la recherche de l'élément qui satisfait une certaine condition est O(n), mais c'est la liste de tableaux.Contient si vous pouviez mettre en œuvre la méthode Equals. Si vous ne faites pas ceci dans des boucles ou boucles internes de cette approche est probablement très bien.

Si vous avez vraiment besoin très efficace de recherche de vitesse à tout prix, vous aurez besoin de faire deux choses:

1. Contourner le fait que la classe généré: Écrire un adaptateur classe qui peut envelopper la classe générée et qui implémenter equals()basé sur ces deux champs (en supposant qu'ils sont publiques). N'oubliez pas également mettre en œuvre hashCode() (*)
2. Envelopper chaque objet avec cette carte et mettre dans un HashSet. HashSet.contains() est constante le temps d'accès, i.e. O(1) au lieu de O(n).

Bien sûr, la construction de ce HashSet a encore un O(n) le coût. Vous allez seulement à gagner quoi que ce soit si le coût de construction de HashSet est négligeable par rapport au coût total de tous les contient() vérifie que vous devez faire. Essayer de construire une liste sans doublons est un tel cas.

---

* () La mise en œuvre de hashCode() est mieux fait par utilise XOR (opérateur^) les hashCodes de la même champs que vous utilisez pour le équivaut à la mise en œuvre (mais multiplier par 31 pour réduire le risque de la XOR rendement de 0)

Answer 2

Vous pouvez utiliser un comparateur avec les méthodes intégrées de Java pour le tri et la recherche binaire. Supposons que vous ayez une classe comme celle-ci, où a et b sont les champs que vous voulez utiliser pour le tri:

 class Thing { String a, b, c, d; }
 

Vous définiriez votre comparateur:

 Comparator<Thing> comparator = new Comparator<Thing>() {
  public int compare(Thing o1, Thing o2) {
    if (o1.a.equals(o2.a)) {
      return o1.b.compareTo(o2.b);
    }
    return o1.a.compareTo(o2.a);
  }
};
 

Puis triez votre liste:

 Collections.sort(list, comparator);
 

Et enfin faire la recherche binaire:

 int i = Collections.binarySearch(list, thingToFind, comparator);
 

Answer 3

Compte tenu de vos contraintes, vous êtes coincé avec la force brute de recherche (ou de la création d'un index si la recherche doit être répété). Pouvez-vous élaborer sur la façon dont l' ArrayList est généré--peut-être il ya une certaine marge de manœuvre.

Si tout ce que vous cherchez est plus joli code, pensez à utiliser le Apache Commons Collections de classes, en particulier CollectionUtils.find(), pour prêt-à-sucre syntaxique:

ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...

Object found = CollectionUtils.find(haystack, new Predicate() {
   public boolean evaluate(Object input) {
      return needleField1.equals(input.field1) && 
             needleField2.equals(input.field2);
   }
});

Answer 4

Si la liste est triée, vous pouvez utiliser une recherche binaire. Si non, alors il n'y a pas de meilleure façon.

Si vous êtes en train de faire beaucoup cela, il serait presque certainement être utile de votre temps pour trier la liste de la première fois. Puisque vous ne pouvez pas modifier les classes, vous devez utiliser un Comparator de faire le tri et de recherche.

Answer 5

Même si la méthode equals comparaient ces deux champs, logiquement, il serait juste le même code que vous le faire manuellement. OK, ça pourrait être "en désordre", mais c'est toujours la bonne réponse