Interseção e união de ArrayLists em Java
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?
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 por quê Vector? Essa classe foi desencorajada desde o Java 1.2.
@ 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
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.
@ dimo414 é uma biblioteca IBM, haha! (API de dados do Lotus Domino). Obrigado pela informação, muito útil
— user2808054 8/16
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.
você pode criar nova lista com elementos de list1 e, em seguida, chamar retainAll, métodos addAll
por que você está usando strictfp nesta solução?
— Lukastymo 31/03
Deve usar a HashSetpara intersectionque o desempenho médio do caso seja O (n) em vez de O (n ^ 2).
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>
Collection (também ArrayList):
Use uma implementação de lista, se você aceitar repetições, e uma implementação de conjunto, se não:
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.
Na verdade, foi editado, consulte: "Use uma implementação lista se você aceitar repetições, uma implementação Set se não o fizer:"
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
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.
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:
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
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.
união será removeAlle entãoaddAll .
— O GiG
Ambas retainAll()e removeAll()são operações O (n ^ 2) nas listas. Nós podemos fazer melhor.
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
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
— Stan Kurilin
Você pode usar CollectionUtilsdo apache commons .
— pé azul
Caso alguém ache a resposta um pouco curta demais: 'CollectionUtils.containsAny' e 'CollectionUtils.containsAll' são os métodos.
— 12136 Sebastian
que é estranho que CollectionUtils do Apache commons não suporta genéricos
— Vasyl Sarzhynskyi
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).
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?
Infelizmente - seria mais barato fazê-lo em O (n ^ 2) :) Para Números esta solução é bom ...
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)?
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.
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.
Aqui está uma maneira de fazer uma interseção com fluxos (lembre-se de que você deve usar o java 8 para fluxos):
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:
— Deutro
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.
Você pode usar o commons-collections4 CollectionUtils
— xxg
No Java 8, eu uso métodos auxiliares simples como este:
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.
— Jeroen Vuurens
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.
Interseção de duas listas de objetos diferentes com base na chave comum - Java 8
— Niraj Sonawane
que tal diferença definida entre os 2 lista?
JDK8 + (provavelmente o melhor desempenho)
Se você não se importa com o desempenho e prefere um código menor, basta usar:
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.
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.
Explique o código que você apresentou em vez de apenas uma resposta de código.
Estou apenas dando uma pista que você tem que colocar qualquer valor de lixo
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.
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.
— Dilabeing
Use o método retentAll () para encontrar o elemento comum ... ou seja, interseção list1.retainAll (list2)
— yamini shrestha
Se você tivesse seus dados em Sets, poderia usar a Setsclasse Guava .
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.
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
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.