Estamos acostumados ao fato de que as coleções padrão no JDK são feitas muito bem e se comportam intuitivamente. Mas é realmente assim? Ontem Roman Elizarovelizarovpostou no Twitter as notícias sobre um novo batente interessante.Segure firme: Set.removeAll(list)em certos casos, ele pode funcionar para O (N²). Como assim?
Roman descobriu um problema ao depurar um pedaço de código que, por um motivo incrível, funcionava muito devagar. Ele o lançou no criador de perfil incorporado no IntelliJ IDEA e viu instantaneamente no gráfico de chama que estava perdendo o tempo todo dentro do método AbstractSet.removeAllem uma chamada list.contains(link para o local exato no código ).Para entender o que está acontecendo, considere um exemplo um pouco diferente. Jon Skeet escreveu anteriormente um post "Há um buraco na minha abstração, querida Liza, querida Liza" , na qual ele considera o seguinte caso interessante.Digamos que temos um HashSet do qual vamos excluir algo. Suponha que removamos elementos de outra coleção B de uma coleção A. Muitas vezes acontece que muitos elementos de B simplesmente não existem em A. Analisaremos um caso especial quando A e B não se cruzam - ou seja, nada precisa ser feito.Escreveremos um programa simples no qual os tamanhos de nossas coleções são definidos na linha de comando. Para que esses conjuntos não se cruzem exatamente, preenchemos um deles apenas com números positivos e o outro apenas com números negativos. Em seguida, removemos da primeira coleção todos os elementos da segunda e medimos o tempo decorrido usandoSystem.currentTimeMillis(). Esta não é a melhor maneira do mundo para calcular o intervalo de tempo, mas possibilita copiar e colar o código diretamente do Habr para o Idea e evita a necessidade de configurar um novo projeto Maven para o JMH.import java.util.*;
public class Test {
public static void main(String[] args) {
int sourceSize = Integer.parseInt(args[0]);
int removalsSize = Integer.parseInt(args[1]);
Set<Integer> source = new HashSet<Integer>();
Collection<Integer> removals = new ArrayList<Integer>();
for (int i = 0; i < sourceSize; i++) {
source.add(i);
}
for (int i = 1; i <= removalsSize; i++) {
removals.add(-i);
}
long start = System.currentTimeMillis();
source.removeAll(removals);
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (end - start) + "ms");
}
}
Código muito simples que pode ser escrito sem recuperar a consciência. Agora vamos executá-lo com parâmetros diferentes. Primeiro, tente um conjunto de 100 elementos dos quais você precisa lançar 100:$ java Test 100 100
Time taken: 1ms
Até agora, tudo é rápido o suficiente, mas o que acontece se você aumentar os números?java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
Como você gosta disso: agora esperamos três minutos. Parece intuitivamente que o tempo de processamento de uma coleção menor (300.000 itens no segundo caso) deve ser menor do que no processamento de uma coleção maior (um milhão de itens no primeiro caso). Imediatamente o oposto é verdadeiro. A vida não estava se preparando para isso, certo?Agora, o segredo do foco.De fato, é descrito em texto não criptografado no JavaDoc correspondente :O código de implementação determina se é menor: conjunto ou coleção. Isso é feito usando o método sizeem cada um deles. Se houver menos elementos no conjunto, a iteração é executada no conjunto e a cada iteração é verificado se o elemento atual está na coleção. Se sim, o elemento é removido do conjunto usando o método removeiterador. Se a coleção for menor no número de elementos, será necessário ignorar a coleção já, removendo do conjunto todos esses elementos usando o método removedo conjunto.
Na prática, isso significa que, quando chamado source.removeAll(removals):- Se a coleção é
removalsmenor do que source, em seguida, o método é chamado removeno HashSet, e é muito rápido; - Se a coleção for
removalsmaior ou igual em tamanho que source, então é chamado um método removals.containsque funciona muito lentamente para ArrayList.
No JDK 8, algo como isso é responsável por esse trecho de código:public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
Parece que o JDK escolheu uma maneira bastante ruim de lidar com a tarefa, mas como ela já está descrita no JavaDoc, não há como voltar atrás.Ou existe?As pessoas correram para o tweet de Roman Elizarov, e Zheka Kozlov encontrou o bug correspondente publicado no JDK 15 com o artista Stuart Marx.E depois disso, o próprio Stuart Marx entrou na discussão e confirmou que estava realmente lidando com esse problema:Portanto, há luz no fim do túnel. Se você atualizar para as versões mais recentes do Java, é claro.achados
As conclusões desta história são as seguintes: há um problema que vale a pena conhecer. O problema já está sendo reparado, mas reparado apenas para usuários felizes de Java fresco, e você realmente não deve esperar por isso.Em geral, ao tentar armazenar muitos dados em coleções em Java, você pode ter vários problemas não intuitivos para os quais precisa estar preparado.
Então, crianças, hoje aprendemos algo novo!Como continuação do banquete, recomendo que você analise alguns relatórios de Roman Elizarov, que ajudou a trazer esse bug à luz. Obviamente, esses relatórios não têm nada a ver com o bug em si, mas existem várias placas de lata diferentes:JPoint, , 2020 . , , , .