Intersecção e união de ArrayLists em Java

Existem methods para isso? Eu estava procurando, mas não consegui encontrar nenhum.

Outra questão: eu preciso desses methods para filtrar arquivos. Alguns são filtros AND e alguns são filtros OR (como na teoria dos conjuntos), então eu preciso filtrar de acordo com todos os arquivos e os ArrayLists unidos / intersectados que contém esses arquivos.

Devo usar uma estrutura de dados diferente para armazenar os arquivos? Existe mais alguma coisa que ofereça um tempo de execução melhor?

Aqui está uma implementação simples sem usar qualquer biblioteca de terceiros. A principal vantagem sobre retainAll , removeAll e addAll é que esses methods não modificam a input das listas originais para os methods.

 public class Test { public static void main(String... args) throws Exception { List list1 = new ArrayList(Arrays.asList("A", "B", "C")); List list2 = new ArrayList(Arrays.asList("B", "C", "D", "E", "F")); System.out.println(new Test().intersection(list1, list2)); System.out.println(new Test().union(list1, list2)); } public  List union(List list1, List list2) { Set set = new HashSet(); set.addAll(list1); set.addAll(list2); return new ArrayList(set); } public  List intersection(List list1, List list2) { List list = new ArrayList(); for (T t : list1) { if(list2.contains(t)) { list.add(t); } } return list; } } 

Coleção (assim ArrayList também) tem:

 col.retainAll(otherCol) // for intersection col.addAll(otherCol) // for union 

Use uma implementação de lista se você aceitar repetições, uma implementação de conjunto se você não:

 Collection col1 = new ArrayList(); // {a, b, c} // Collection col1 = new TreeSet(); col1.add("a"); col1.add("b"); col1.add("c"); Collection col2 = new ArrayList(); // {b, c, d, e} // Collection col2 = new TreeSet(); 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] 

Este post é bastante antigo, mas, no entanto, foi o primeiro a aparecer no google quando se olha para esse tópico.

Eu quero dar uma atualização usando streams Java 8 fazendo (basicamente) a mesma coisa em uma única linha:

 List intersect = list1.stream() .filter(list2::contains) .collect(Collectors.toList()); List union = Stream.concat(list1.stream(), list2.stream()) .distinct() .collect(Collectors.toList()); 

Se alguém tiver uma solução melhor / mais rápida, avise-me, mas essa solução é um bom alinhador que pode ser facilmente incluído em um método sem adicionar uma class / método auxiliar desnecessário e ainda manter a legibilidade.

 list1.retainAll(list2) - is intersection 

união será removeAll e, em seguida, addAll .

Encontre mais na documentação da coleção (ArrayList é uma coleção) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html

Uniões e intersecções definidas apenas para conjuntos, não listas. Como você mencionou.

Verifique a biblioteca de goiabas quanto a filtros. Também goiaba fornece cruzamentos reais e uniões

  static  Sets.SetViewunion(Set set1, Set set2) static  Sets.SetView intersection(Set set1, Set set2) 

Você pode usar o CollectionUtils partir do apache commons .

A solução marcada não é eficiente. Tem uma complexidade de tempo O (n ^ 2). O que podemos fazer é classificar as duas listas e executar um algoritmo de interseção como o abaixo.

 private static ArrayList interesect(ArrayList f, ArrayList s) { ArrayList res = new ArrayList(); 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; } 

Este tem uma complexidade de O (n log n + n) que está em O (n log n). A união é feita de maneira semelhante. Apenas certifique-se de fazer as modificações adequadas nas instruções if-elseif-else.

Você também pode usar iteradores se quiser (eu sei que eles são mais eficientes em C ++, eu não sei se isso é verdade em Java também).

Eu acho que você deve usar um Set para manter os arquivos se você quiser fazer interseção e união sobre eles. Então você pode usar a class Sets de Guava para fazer union , intersection e filtragem por um Predicate também. A diferença entre esses methods e as outras sugestões é que todos esses methods criam visualizações preguiçosas da união, interseção etc. dos dois conjuntos. O Apache Commons cria uma nova coleção e copia dados para ela. retainAll altera uma das suas collections, removendo elementos dela.

Aqui está uma maneira como você pode fazer uma interseção com streams (lembre-se que você tem que usar o java 8 para streams):

 List fooList1 = new ArrayList<>(Arrays.asList(new foo(), new foo())); List fooList2 = new ArrayList<>(Arrays.asList(new foo(), new foo())); fooList1.stream().filter(f -> fooList2.contains(f)).collect(Collectors.toList()); 

Um exemplo de listas com diferentes tipos. Se você tem uma realção entre foo e bar e você pode obter um object bar de foo do que você pode modificar seu stream:

 List fooList = new ArrayList<>(Arrays.asList(new foo(), new foo())); List barList = new ArrayList<>(Arrays.asList(new bar(), new bar())); fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList()); 
  • retainAll modificará sua lista
  • Guava não tem APIs para List (somente para set)

Eu encontrei ListUtils muito útil para este caso de uso.

Use ListUtils de org.apache.commons.collections se não quiser modificar a lista existente.

ListUtils.intersection(list1, list2)

No Java 8, eu uso methods auxiliares simples como este:

 public static  Collection getIntersection(Collection coll1, Collection coll2){ return Stream.concat(coll1.stream(), coll2.stream()) .filter(coll1::contains) .filter(coll2::contains) .collect(Collectors.toSet()); } public static  Collection getMinus(Collection coll1, Collection coll2){ return coll1.stream().filter(not(coll2::contains)).collect(Collectors.toSet()); } public static  Predicate not(Predicate t) { return t.negate(); } 

Eu também estava trabalhando na situação semelhante e cheguei aqui em busca de ajuda. Acabei encontrando minha própria solução para Arrays. ArrayList AbsentDates = novo ArrayList (); // Irá armazenar Array1-Array2

Nota: Poste isto se puder ajudar alguém a chegar a esta página para obter ajuda.

 ArrayList AbsentDates = new ArrayList();//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 ); } 

Você pode usar commons-collections4 CollectionUtils

 Collection collection1 = Arrays.asList(1, 2, 4, 5, 7, 8); Collection collection2 = Arrays.asList(2, 3, 4, 6, 8); Collection intersection = CollectionUtils.intersection(collection1, collection2); System.out.println(intersection); // [2, 4, 8] Collection union = CollectionUtils.union(collection1, collection2); System.out.println(union); // [1, 2, 3, 4, 5, 6, 7, 8] Collection subtract = CollectionUtils.subtract(collection1, collection2); System.out.println(subtract); // [1, 5, 7] 

Se os objects na lista são hashable (ou seja, tem uma function hashCode e equals decente), a aproximação mais rápida entre as tabelas é de aprox. tamanho> 20 é construir um HashSet para o maior das duas listas.

 public static  ArrayList intersection(Collection a, Collection b) { if (b.size() > a.size()) { return intersection(b, a); } else { if (b.size() > 20 && !(a instanceof HashSet)) { a = new HashSet(a); } ArrayList result = new ArrayList(); for (T objb : b) { if (a.contains(objb)) { result.add(objb); } } return result; } } 

Solução final:

 //all sorted items from both public  List getListReunion(List list1, List list2) { Set set = new HashSet(); set.addAll(list1); set.addAll(list2); return new ArrayList(set); } //common items from both public  List getListIntersection(List list1, List list2) { list1.retainAll(list2); return list1; } //common items from list1 not present in list2 public  List getListDifference(List list1, List list2) { list1.removeAll(list2); return list1; } 

Primeiro, estou copiando todos os valores de matrizes em um único array, então estou removendo valores duplicados para o array. A linha 12, explicando se o mesmo número ocorre mais do que o tempo, coloca algum valor extra de lixo na posição “j”. No final, atravesse de start-end e verifique se o mesmo valor de lixo ocorre e descarte.

 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 

Se você tivesse seus dados em Sets, você poderia usar a class Sets de Guava.

Se o número coincidir com o que estou verificando, ele ocorrerá pela primeira vez ou não com a ajuda de “indexOf ()” se o número coincidir com a primeira vez, então imprima e salve em uma string de forma que, na próxima vez, t print porque devido a condição “indexOf ()” será falsa.

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

}

Intereting Posts