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

130

Existem métodos para fazer isso? Eu estava procurando, mas não consegui encontrar nenhum.

Outra pergunta: preciso desses métodos para filtrar arquivos. Alguns são ANDfiltros e outros são ORfiltros (como na teoria dos conjuntos), então eu preciso filtrar de acordo com todos os arquivos e o ArrayLists de união / interseção que contém esses arquivos.

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

yotamoo
fonte
1
Se você não deseja criar uma nova lista, Vector.retainAll (Vector) apara seu vetor original apenas na interseção com o segundo vetor.
user2808054
@ user2808054 por quê Vector? Essa classe foi desencorajada desde o Java 1.2.
dimo414
@ dimo414 uma interface que estou usando (não tenho opção) retorna as coisas como vetores. Eu não sabia que tinha sido desencorajado! Obrigado pela informação .. Desanimado por quem? Eu não vi nenhuma nota sobre isso ser descontinuado, então isso é uma surpresa #
user2808054 1/16/16
1
Nos Javadocs: " A partir da plataforma Java 2 v1.2 ... é recomendável usar ArrayList no lugar de Vector. ". O único momento que você pode precisar Vectoré para interações entre threads, mas também existem estruturas de dados mais seguras para esses casos de uso. Veja também esta questão . Qualquer biblioteca que ainda Vectoresteja usando em 2016 é muito suspeita na minha opinião.
precisa saber é o seguinte
@ dimo414 é uma biblioteca IBM, haha! (API de dados do Lotus Domino). Obrigado pela informação, muito útil
user2808054 8/16

Respostas:

122

Aqui está uma implementação simples, sem usar nenhuma biblioteca de terceiros. Principal vantagem retainAll, removeAlle addAllé que esses métodos não modifique a entrada de listas original para os métodos.

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;
    }
}
adarshr
fonte
16
você pode criar nova lista com elementos de list1 e, em seguida, chamar retainAll, métodos addAll
lukastymo
por que você está usando strictfp nesta solução?
Lukastymo 31/03
9
Deve usar a HashSetpara intersectionque o desempenho médio do caso seja O (n) em vez de O (n ^ 2).
Zong
1
Esta postagem pode usar uma atualização para demonstrar os benefícios da API Java 8 Stream.
SME_Dev 02/09/2015
Eu recebo erro Quando tento atribuir esse valor -> Exemplo: ArrayList <String> total total = (ArrayList <String>) interseção (lista2, lista1) ---> não é possível converter java.util.arraylist para java.util.arraylist < string>
delive
123

Collection (também ArrayList):

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

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

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]
lukastymo
fonte
3
Houve uma edição sugerida de que essa união "está incorreta, pois conterá elementos comuns duas vezes" . A edição recomenda o uso de um HashSet.
Kos
5
Na verdade, foi editado, consulte: "Use uma implementação lista se você aceitar repetições, uma implementação Set se não o fizer:"
lukastymo
7
Não, retainAll não é interseção para a lista. Acima, todos os elementos em col que não estão em otherCol são removidos. Digamos que otherCol seja {a, b, b, c} e col seja {b, b, b, c, d}. Então col termina com {b, b, b, c}, que não é estritamente a interseção dos dois. Eu esperaria que fosse {b, b, c}. Uma operação diferente está sendo executada.
Demongolem 18/03/16
1
Também não vejo como addAll()é a união para listas; é apenas concatenar a segunda lista no final da primeira. Uma operação de união evitaria adicionar um elemento se a primeira lista já o contiver.
dimo414
66

Este post é bastante antigo, mas foi o primeiro a aparecer no google ao procurar esse tópico.

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

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

List<T> 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 é uma ótima opção que pode ser facilmente incluída em um método sem adicionar uma classe / método auxiliar desnecessário e ainda assim manter a legibilidade.

Fat_FS
fonte
19
Ooof, pode ser uma linha única agradável, mas leva O (n ^ 2) tempo. Converta uma das listas em uma Sete use o containsmétodo do conjunto . Nem tudo na vida tem que ser feito com correntes.
dimo414
31
list1.retainAll(list2) - is intersection

união será removeAlle entãoaddAll .

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

O GiG
fonte
1
Ambas retainAll()e removeAll()são operações O (n ^ 2) nas listas. Nós podemos fazer melhor.
dimo414
1
Votei, mas agora tenho uma pergunta. retainAllde {1, 2, 2, 3, 4, 5} acima de {1, 2, 3} resulta em {1, 2, 2, 3}. Não deveria ser {1, 2, 3} o cruzamento?
GyuHyeon Choi
21

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

Verifique a biblioteca da goiaba para obter filtros A goiaba também fornece interseções e uniões reais

 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)
Stan Kurilin
fonte
12

Você pode usar CollectionUtilsdo apache commons .

pé azul
fonte
7
Caso alguém ache a resposta um pouco curta demais: 'CollectionUtils.containsAny' e 'CollectionUtils.containsAll' são os métodos.
12136 Sebastian
2
que é estranho que CollectionUtils do Apache commons não suporta genéricos
Vasyl Sarzhynskyi
7

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

Este possui 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 ++, não sei se isso também é verdade em Java).

AJed
fonte
1
Não genérico o suficiente, T pode não ser comparável e, em alguns casos comparando é caro ...
Boris Churzin
Não é genérico, concordo totalmente. Comparação é cara? como você resolveria isso?
AJed
Infelizmente - seria mais barato fazê-lo em O (n ^ 2) :) Para Números esta solução é bom ...
Boris Churzin
Infelizmente - você não respondeu minha pergunta. Deixe-me reformular, como O (n ^ 2) é melhor, dada uma função de comparação do custo c (n)?
AJed
1
Converter uma entrada em um conjunto e chamar contains()um loop (como sugere Devenv) levaria tempo O (n + m). A classificação é desnecessariamente complicada e leva tempo O (n log n + m log n + n). Concedido que reduz o tempo O (n log n), mas ainda é pior que o tempo linear e muito mais complexo.
dimo414
4

Eu acho que você deve usar a Setpara armazenar os arquivos, se quiser fazer uma interseção e união neles. Então você pode usar goiaba 's conjuntos de classe para fazer union, intersectione filtrar por um Predicatebem. A diferença entre esses métodos e as outras sugestões é que todos esses métodos criam vistas preguiçosas da união, interseção etc. dos dois conjuntos. O Apache Commons cria uma nova coleção e copia os dados para ela. retainAllaltera uma de suas coleções removendo elementos dela.

ColinD
fonte
4

Aqui está uma maneira de fazer uma interseção com fluxos (lembre-se de que você deve usar o java 8 para fluxos):

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());

Um exemplo para listas com tipos diferentes. Se você tem uma noção entre foo e bar e pode obter um objeto de barra de foo, pode modificar seu fluxo:

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());
Deutro
fonte
3
  • retallAll modificará sua lista
  • A goiaba não possui APIs para a lista (apenas para o conjunto)

Achei o ListUtils muito útil para este caso de uso.

Use ListUtils em org.apache.commons.collections se você não deseja modificar a lista existente.

ListUtils.intersection(list1, list2)

Bala
fonte
3

Você pode usar o commons-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]
xxg
fonte
2

No Java 8, eu uso métodos auxiliares simples como este:

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();
}
Pascalius
fonte
1

Se os objetos na lista são hasháveis ​​(ou seja, possuem um hashCode decente e uma função igual), a abordagem mais rápida entre as tabelas aprox. size> 20 é construir um HashSet para a maior das duas listas.

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;
    }
}
Jeroen Vuurens
fonte
1

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

Nota: Publique isso se puder ajudar alguém a acessar esta página para obter ajuda.

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 );
        }
Shubham Pandey
fonte
1

Interseção de duas listas de objetos diferentes com base na chave comum - Java 8

 private List<User> intersection(List<User> users, List<OtherUser> list) {

        return list.stream()
                .flatMap(OtherUser -> users.stream()
                        .filter(user -> user.getId()
                                .equalsIgnoreCase(OtherUser.getId())))
                .collect(Collectors.toList());
    }
Niraj Sonawane
fonte
que tal diferença definida entre os 2 lista?
jean
1
public static <T> Set<T> intersectCollections(Collection<T> col1, Collection<T> col2) {
    Set<T> set1, set2;
    if (col1 instanceof Set) {
        set1 = (Set) col1;
    } else {
        set1 = new HashSet<>(col1);
    }

    if (col2 instanceof Set) {
        set2 = (Set) col2;
    } else {
        set2 = new HashSet<>(col2);
    }

    Set<T> intersection = new HashSet<>(Math.min(set1.size(), set2.size()));

    for (T t : set1) {
        if (set2.contains(t)) {
            intersection.add(t);
        }
    }

    return intersection;
}

JDK8 + (provavelmente o melhor desempenho)

public static <T> Set<T> intersectCollections(Collection<T> col1, Collection<T> col2) {
    boolean isCol1Larger = col1.size() > col2.size();
    Set<T> largerSet;
    Collection<T> smallerCol;

    if (isCol1Larger) {
        if (col1 instanceof Set) {
            largerSet = (Set<T>) col1;
        } else {
            largerSet = new HashSet<>(col1);
        }
        smallerCol = col2;
    } else {
        if (col2 instanceof Set) {
            largerSet = (Set<T>) col2;
        } else {
            largerSet = new HashSet<>(col2);
        }
        smallerCol = col1;
    }

    return smallerCol.stream()
            .filter(largerSet::contains)
            .collect(Collectors.toSet());
}

Se você não se importa com o desempenho e prefere um código menor, basta usar:

col1.stream().filter(col2::contains).collect(Collectors.toList());
İsmail Yavuz
fonte
0

Solução final:

//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;
}
Choletski
fonte
0

Primeiro, estou copiando todos os valores de matrizes em uma única matriz e removendo valores duplicados na matriz. Linha 12, explicando se o mesmo número ocorre mais do que o tempo, coloque algum valor extra de lixo na posição "j". No final, vá do início ao fim 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<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]+" ");
    }
}   
}
Ashutosh
fonte
1
Bem-vindo ao Stack Overflow! Observe que a pergunta é sobre ArrayList. Além disso, receio que essa implementação em particular deixe as coisas a serem desejadas. O valor 99999999, que é usado como sentinela, pode ocorrer na entrada. Seria melhor usar uma estrutura dinâmica, como ArrayList, para armazenar o resultado da união.
SL Barth - Restabelecer Monica
1
Explique o código que você apresentou em vez de apenas uma resposta de código.
precisa saber é
Estou apenas dando uma pista que você tem que colocar qualquer valor de lixo
Ashutosh
Fico feliz em ver que você adicionou uma explicação. Infelizmente, a resposta em si ainda é ruim. Não há razão para usar matrizes. Você deve usar uma estrutura dinâmica como ArrayList. Se (por algum motivo) você precisar usar matrizes, considere usar uma matriz em Integervez de int. Então você pode usar em nullvez do seu "valor de lixo". "Valores de lixo" ou "valores de sentinela" geralmente são uma má idéia, porque esses valores ainda podem ocorrer na entrada.
SL Barth - Restabelecer Monica
0

Após o teste, aqui está minha melhor abordagem de interseção.

Velocidade mais rápida em comparação com a abordagem HashSet pura. O HashSet e o HashMap abaixo apresentam desempenho semelhante para matrizes com mais de 1 milhão de registros.

Quanto à abordagem do Java 8 Stream, a velocidade é bastante lenta para um tamanho de matriz maior que 10k.

Espero que isso possa ajudar.

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));
}
Dilabeing
fonte
0

Use o método retentAll () para encontrar o elemento comum ... ou seja, interseção list1.retainAll (list2)

yamini shrestha
fonte
-1

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

Neil
fonte
-1

Se o número corresponder ao que eu estou verificando, ocorrerá pela primeira vez ou não com a ajuda de "indexOf ()" se o número corresponder à primeira vez, imprima e salve em uma string para que, na próxima vez que o mesmo número corresponda, ele será vencido ' t imprime porque devido à 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;
                }
           }
       }    
}

}

Ashutosh
fonte
2
Faça código não basta postar como uma resposta, dar alguma pequena explicação do que você está fazendo
Brandon Zamudio
é meu primeiro programa que eu carregado
Ashutosh
2
Embora esse código possa ajudar a resolver o problema, ele não explica por que e / ou como responde à pergunta. Fornecer esse contexto adicional melhoraria significativamente seu valor a longo prazo. Por favor edite sua resposta para adicionar explicação, incluindo o que limitações e premissas se aplicam.
precisa