Intersection et union des ArrayLists en Java
Existe-il des méthodes pour le faire? J'étais à la recherche, mais ne pouvais pas trouver toutes.
Une autre question: j'ai besoin de ces méthodes pour pouvoir filtrer les fichiers.
Certains sont des filtres AND
et d'autres sont des filtres OR
(comme dans la théorie des ensembles), donc j'ai besoin de filtrer en fonction de tous les fichiers et des ArrayLists unite/intersects qui contiennent ces fichiers.
Dois-je utiliser une structure de données différente pour contenir les fichiers? Y at-il autre chose qui offrirait un meilleur temps d'exécution?
19 réponses
Voici une implémentation simple sans utiliser de bibliothèque tierce. Principal avantage sur retainAll
, removeAll
et addAll
est que ces méthodes ne modifient pas les listes d'origine entrées dans les méthodes.
public class Test {
public static void main(String... args) throws Exception {
List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));
System.out.println(new Test().intersection(list1, list2));
System.out.println(new Test().union(list1, list2));
}
public <T> List<T> union(List<T> list1, List<T> list2) {
Set<T> set = new HashSet<T>();
set.addAll(list1);
set.addAll(list2);
return new ArrayList<T>(set);
}
public <T> List<T> intersection(List<T> list1, List<T> list2) {
List<T> list = new ArrayList<T>();
for (T t : list1) {
if(list2.contains(t)) {
list.add(t);
}
}
return list;
}
}
Collection (donc ArrayList aussi) ont:
col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union
Utilisez une implémentation de liste si vous acceptez les répétitions, une implémentation de Set si vous ne le faites pas:
Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");
Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");
col1.addAll(col2);
System.out.println(col1);
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]
Ce post est assez vieux, mais néanmoins c'était le premier à apparaître sur google lors de la recherche de ce sujet.
Je veux donner une mise à jour en utilisant les flux Java 8 en faisant (fondamentalement) la même chose en une seule ligne:
List<T> intersect = list1.stream()
.filter(list2::contains)
.collect(Collectors.toList());
List<T> union = Stream.concat(list1.stream(), list2.stream())
.distinct()
.collect(Collectors.toList());
Si quelqu'un a une solution meilleure/plus rapide, faites-le moi savoir, mais cette solution est une bonne doublure qui peut être facilement incluse dans une méthode sans ajouter une classe/méthode d'aide inutile et garder la lisibilité.
list1.retainAll(list2) - is intersection
Union removeAll
, puis addAll
.
Trouver plus dans la documentation de collection (ArrayList est une collection) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html
Unions et intersections définies uniquement pour les ensembles, pas pour les listes. Comme vous l'avez mentionné.
Vérifiez la bibliothèqueguava pour les filtres. La goyave fournit également des intersections et des unions réelles
static <E> Sets.SetView<E >union(Set<? extends E> set1, Set<? extends E> set2)
static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)
Vous pouvez utiliser CollectionUtils
depuis Apache commons .
La solution marquée n'est pas efficace. Il a une complexité temporelle O(N^2). Ce que nous pouvons faire est de trier les deux listes, et l'exécution d'un algorithme d'intersection comme celui ci-dessous.
private static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0, j = 0;
while (i != f.size() && j != s.size()) {
if (f.get(i) < s.get(j)) {
i ++;
} else if (f.get(i) > s.get(j)) {
j ++;
} else {
res.add(f.get(i));
i ++; j ++;
}
}
return res;
}
Celui-ci a une complexité de O(N log n + n) Qui est dans O(N log n). L'union se fait de la même manière. Assurez-vous de faire les modifications appropriées sur l'if-elseif-else.
Vous pouvez également utiliser des itérateurs si vous le souhaitez (je sais qu'ils sont plus efficaces en C++, Je ne sais pas si cela est vrai en Java ainsi).
, je pense que vous devriez utiliser un Set
pour contenir les fichiers si vous voulez faire de l'intersection et l'union sur eux. Ensuite, vous pouvez utiliser la classeGuava définit à faire union
, intersection
et filtrer par un Predicate
aussi. La différence entre ces méthodes et les autres suggestions est que toutes ces méthodes créent des vues paresseuses de l'union, de l'intersection, etc. des deux ensembles. Apache Commons crée une nouvelle collection et y copie des données. retainAll
modifie une de vos collections par la suppression des éléments.
Voici un moyen de faire une intersection avec des flux (rappelez-vous que vous devez utiliser java 8 pour les flux):
List<foo> fooList1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> fooList2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
fooList1.stream().filter(f -> fooList2.contains(f)).collect(Collectors.toList());
Un exemple pour les listes avec différents types. Si vous avez une realtion entre foo et bar et que vous pouvez obtenir un bar-object de foo, vous pouvez modifier votre flux:
List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));
fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());
- retainAll modifiera votre liste
- Guava n'a pas D'API pour List (uniquement pour set)
J'ai trouvé ListUtils très utile pour ce cas d'utilisation.
Utilisez ListUtils depuis org.Apache.commun.collections si vous ne souhaitez pas modifier la liste existante.
ListUtils.intersection(list1, list2)
En Java 8, j'utilise des méthodes d'aide simples comme ceci:
public static <T> Collection<T> getIntersection(Collection<T> coll1, Collection<T> coll2){
return Stream.concat(coll1.stream(), coll2.stream())
.filter(coll1::contains)
.filter(coll2::contains)
.collect(Collectors.toSet());
}
public static <T> Collection<T> getMinus(Collection<T> coll1, Collection<T> coll2){
return coll1.stream().filter(not(coll2::contains)).collect(Collectors.toSet());
}
public static <T> Predicate<T> not(Predicate<T> t) {
return t.negate();
}
Si les objets de la liste sont hashable (c'est-à-dire ont un hashCode décent et une fonction égale), l'approche la plus rapide entre les tables env. taille > 20 est de construire un HashSet pour la plus grande des deux listes.
public static <T> ArrayList<T> intersection(Collection<T> a, Collection<T> b) {
if (b.size() > a.size()) {
return intersection(b, a);
} else {
if (b.size() > 20 && !(a instanceof HashSet)) {
a = new HashSet(a);
}
ArrayList<T> result = new ArrayList();
for (T objb : b) {
if (a.contains(objb)) {
result.add(objb);
}
}
return result;
}
}
Je travaillais aussi sur la situation similaire et je suis arrivé ici à la recherche d'aide. Fini par trouver ma propre solution pour les Tableaux. ArrayList AbsentDates = new ArrayList (); / / stockera Array1-Array2
Remarque: poster ceci si cela peut aider quelqu'un à atteindre cette page pour obtenir de l'aide.
ArrayList<String> AbsentDates = new ArrayList<String>();//This Array will store difference
public void AbsentDays() {
findDates("April", "2017");//Array one with dates in Month April 2017
findPresentDays();//Array two carrying some dates which are subset of Dates in Month April 2017
for (int i = 0; i < Dates.size(); i++) {
for (int j = 0; j < PresentDates.size(); j++) {
if (Dates.get(i).equals(PresentDates.get(j))) {
Dates.remove(i);
}
}
AbsentDates = Dates;
}
System.out.println(AbsentDates );
}
Vous pouvez utiliser des communes-collections4 CollectionUtils
Collection<Integer> collection1 = Arrays.asList(1, 2, 4, 5, 7, 8);
Collection<Integer> collection2 = Arrays.asList(2, 3, 4, 6, 8);
Collection<Integer> intersection = CollectionUtils.intersection(collection1, collection2);
System.out.println(intersection); // [2, 4, 8]
Collection<Integer> union = CollectionUtils.union(collection1, collection2);
System.out.println(union); // [1, 2, 3, 4, 5, 6, 7, 8]
Collection<Integer> subtract = CollectionUtils.subtract(collection1, collection2);
System.out.println(subtract); // [1, 5, 7]
Solution Finale:
//all sorted items from both
public <T> List<T> getListReunion(List<T> list1, List<T> list2) {
Set<T> set = new HashSet<T>();
set.addAll(list1);
set.addAll(list2);
return new ArrayList<T>(set);
}
//common items from both
public <T> List<T> getListIntersection(List<T> list1, List<T> list2) {
list1.retainAll(list2);
return list1;
}
//common items from list1 not present in list2
public <T> List<T> getListDifference(List<T> list1, List<T> list2) {
list1.removeAll(list2);
return list1;
}
Tout d'abord, je copie toutes les valeurs des tableaux dans un seul tableau, puis je supprime les valeurs de doublons dans le tableau. Ligne 12, expliquant si le même nombre se produit plus de temps, puis mettre une valeur de poubelle supplémentaire en position "j". À la fin, traversez à partir de start-end et vérifiez si la même valeur de mémoire se produit, puis jetez.
public class Union {
public static void main(String[] args){
int arr1[]={1,3,3,2,4,2,3,3,5,2,1,99};
int arr2[]={1,3,2,1,3,2,4,6,3,4};
int arr3[]=new int[arr1.length+arr2.length];
for(int i=0;i<arr1.length;i++)
arr3[i]=arr1[i];
for(int i=0;i<arr2.length;i++)
arr3[arr1.length+i]=arr2[i];
System.out.println(Arrays.toString(arr3));
for(int i=0;i<arr3.length;i++)
{
for(int j=i+1;j<arr3.length;j++)
{
if(arr3[i]==arr3[j])
arr3[j]=99999999; //line 12
}
}
for(int i=0;i<arr3.length;i++)
{
if(arr3[i]!=99999999)
System.out.print(arr3[i]+" ");
}
}
}
Après le test, voici ma meilleure approche d'intersection.
Vitesse plus rapide par rapport à L'approche pure HashSet. HashSet et HashMap ci-dessous ont des performances similaires pour les tableaux avec plus de 1 million d'enregistrements.
Comme pour L'approche de flux Java 8, la vitesse est assez lente pour une taille de tableau plus grande que 10k.
J'Espère que cela peut aider.
public static List<String> hashMapIntersection(List<String> target, List<String> support) {
List<String> r = new ArrayList<String>();
Map<String, Integer> map = new HashMap<String, Integer>();
for (String s : support) {
map.put(s, 0);
}
for (String s : target) {
if (map.containsKey(s)) {
r.add(s);
}
}
return r;
}
public static List<String> hashSetIntersection(List<String> a, List<String> b) {
Long start = System.currentTimeMillis();
List<String> r = new ArrayList<String>();
Set<String> set = new HashSet<String>(b);
for (String s : a) {
if (set.contains(s)) {
r.add(s);
}
}
print("intersection:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
return r;
}
public static void union(List<String> a, List<String> b) {
Long start = System.currentTimeMillis();
Set<String> r= new HashSet<String>(a);
r.addAll(b);
print("union:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
}
Si le nombre correspond à ce que je vérifie, il se produit la première fois ou non avec l'aide de "indexOf()" si le nombre correspond à la première fois, puis imprimez et enregistrez dans une chaîne de sorte que lorsque la prochaine fois le même nombre correspond, il ne sera pas imprimé car en raison de la condition "indexOf()" sera false.
class Intersection
{
public static void main(String[] args)
{
String s="";
int[] array1 = {1, 2, 5, 5, 8, 9, 7,2,3512451,4,4,5 ,10};
int[] array2 = {1, 0, 6, 15, 6, 5,4, 1,7, 0,5,4,5,2,3,8,5,3512451};
for (int i = 0; i < array1.length; i++)
{
for (int j = 0; j < array2.length; j++)
{
char c=(char)(array1[i]);
if(array1[i] == (array2[j])&&s.indexOf(c)==-1)
{
System.out.println("Common element is : "+(array1[i]));
s+=c;
}
}
}
}
}