Recentemente passamos por um problema de performance com a api java.List. O cenário é o seguinte:
O componente recebe uma lista (java.List) contendo em torno de 60.000 elementos.
A lista é iterada para processar cada um dos elementos contidos nela.
Essa iteração passa a ficar muito lenta na medida que o tamanho da lista aumenta. Fizemos uma medida, e constatamos que o algoritmo de busca do List (metodo get) é O(n2). Analizamos o codigo fonte dessa classe e concretizamos a suspeita.
O problema de um algoritmo da ordem de O(n2) é que fica muito pesado quando o volume de entrada é muito grande. Por esse motivo precisamos usar uma solução caseira para subistituir o java.List.
O rascunho que usamos para buscar um elemento da lista é o seguinte:
For (i = 0 ; - < tamanhoLista ; i++)
elemento = lista.get (i)
Como o metodo get da lista é O(n) e precisamos de um outro da ordem O(n) para iterar a lista, o algoritmo total fica O(n2).
Alguem conhece outro elemento de Lista que tenha uma performance boa na iteração de seus elementos?
Você está usando um LinkedList ou um ArrayList?
O tempo de busca do get no ArrayList é O(1). Apenas no LinkedList você tem esse tempo de O(n).
Mesmo no caso do LinkedList, a iteração deve ser eficiente se você usar um Iterator. Se você estiver usando Java 5 ou superior, substitua o seu for comum por um foreach:
for (TipoDoElemento elemento : lista) {
//faz qualquer coisa
}
Isso usará o Iterator implicitamente.
Se for inferior ao Java 5, use o iterator explicitamente:
Iterator it = lista.iterator();
while (it.hasNext()) {
Object elemento = it.next();
//Faz qualquer coisa
}
diegosantiviago
Não entendi porque o get é O(n), você está usando LinkedList?
Se você usar ArrayList seria O(1).
sergiotaborda
mtuliomk:
Ola,
Recentemente passamos por um problema de performance com a api java.List. O cenário é o seguinte:
O componente recebe uma lista (java.List) contendo em torno de 60.000 elementos.
A lista é iterada para processar cada um dos elementos contidos nela.
Essa iteração passa a ficar muito lenta na medida que o tamanho da lista aumenta. Fizemos uma medida, e constatamos que o algoritmo de busca do List (metodo get) é O(n2). Analizamos o codigo fonte dessa classe e concretizamos a suspeita.
O problema de um algoritmo da ordem de O(n2) é que fica muito pesado quando o volume de entrada é muito grande. Por esse motivo precisamos usar uma solução caseira para subistituir o java.List.
O rascunho que usamos para buscar um elemento da lista é o seguinte:
For (i = 0 ; - < tamanhoLista ; i++)
elemento = lista.get (i)
Como o metodo get da lista é O(n) e precisamos de um outro da ordem O(n) para iterar a lista, o algoritmo total fica O(n2).
Alguem conhece outro elemento de Lista que tenha uma performance boa na iteração de seus elementos?
Primeiro, o seu mecanismo de iteração é péssimo. Use um iterador. SEMPRE!
Segundo, esse numero de elementos na lista é absurdo. Desenvolva um List especial seguindo o padrão FastLane Reader.
Este tipo de mecanismo libera-o de ter 60000 obejtos na memoria e tendo apenas 1.
E
entanglement
Espera um pouquinho.
Um java.util.List (quer seja um ArrayList ou um LinkedList) não deve ser usado para buscar alguma coisa.
Para efetuar a busca, ponha os elementos em um LinkedHashSet (se você precisa que os elementos fiquem organizados como em um ArrayList ou LinkedList) ou um TreeSet (se você prefere que os elementos fiquem ordenados).
Como você sabe que tanto List como Set guardam referências, não valores, é possível até mesmo guardar cada elemento em um List (para você ter as coisas como você já tem) e um Set (para você achar as coisas).
M
mtuliomk
Ola ViniGodoy ,
Estamos usando o ArrayList. Estranho… em testes com o Iterator a performance foi pior. Pelo que percebemos, quando fazemos um get(i) internamente ele percorre todos os elementos até chegar no i.
Abc,
Tulio
ViniGodoy
Tulio. Você tem certeza que esse é um problema do seu ArrayList? Eu já fiz testes com mais objetos do que isso!
Já tentou usar um profiler? Dê uma olhada no VisualVM, numa dessas o erro está em outro lugar.
A implementação do get() do ArrayList é trivial, pode abrir os fontes da Sun e ver.
sergiotaborda
mtuliomk:
Ola ViniGodoy ,
Estamos usando o ArrayList. Estranho… em testes com o Iterator a performance foi pior. Pelo que percebemos, quando fazemos um get(i) internamente ele percorre todos os elementos até chegar no i.
Vc tem a certeza abosluta ?
Faça um cast para ArrayList só para confirmar. Esse comportamento que descreve é tipico do LinkedList
a performance com iterator não pode ser pior que get(i).
