Eficiência - Collections

jorgefrancisco:

Olá pessoal, tranquilo?

Tenho que desenvolver uma aplicação que envolve grafos enormes, e para isso estou pensando em utilizar a representação de grafos em listas de adjacência juntamento com outras idéias para melhoria de desempenho.

Um dos principais requisitos é a rapidez de acesso aos dados do grafo… Para isso, gostaria de saber se um ArrayList, por exemplo, é tão eficiente quanto um vetor (em relação ao acesso indexado, por exemplo). Pergunto isso devido ao fato de ArrayList ser dinâmico e possuir métodos que facilitarão muito o meu trabalho. Ou se esse acesso “indexado” do ArrayList na verdade não é indexado, tendo que percorrer toda a lista para encontrar determinado dado.

Bom… é basicamente isso… desde já, obrigado!

Abraços.

Usar arrays de primitivos como int[] por exemplo será bem mais rápido do que usar ArrayList e outras classes da Collection. E isso é experiência própria. Na “Maratona de Programação” várias soluções só passam por tempo se você usar arrays de primitivos. O mesmo algoritmo mais usando ArrayList não passa. Mas acredito eu, que o fato do ArrayList ter que usar as classes Wrappers colabora muito para essa diferença de velocidade.

Mas enfim, se você precisa de performance, use []. Seu código vai ficar mais feio, mas vai ser mais rápido.

[]'s

Caso queria uma performance maior…Utilize LinkedList ao invez de arrayList , isto se vc for utilizar indexacao…

faloew

Pois é… eu já imaginava isso… O problema em questão é que meu grafo vai crescer dinamicamente, sendo aí que o ArrayList se encaixa como uma luva, porém em relação a eficiência realmente deve perder feio pra um vetor de primitivos… as duas opções tem suas vantagens e desvantagens… =)

bom… tenho que ver diretinho e pesquisar se não há uma solução melhor!

Obrigado pela resposta, lavh!

Abraços!

Acho que é melhor, primeiro, usar as classes adequadas do Collections Framework (em java.util e java.util.concurrent), e DEPOIS ver se é necessário fazer a otimização.
Acho que se você usar as classes adequadas, talvez nem seja preciso fazer tal otimização.
Faça funcionar primeiro, e depois veja se

De qualquer maneira, isto aqui:

String[] r = new String[10000];
String s = r[4500];

e

List<String> r = new ArrayList<String>();
String s = r.get(4500);

são mais ou menos equivalentes em tempo (principalmente se o “just-in-time compiler” decidir que o tal trecho de código deva ser compilado). Acho que você pode ter alguns problemas de desempenho se tiver de usar wrappers (Integer em vez de int). De qualquer maneira, acho que há algumas implementações de classes análogas a ArrayList, mas “bitoladas” para os tipos primitivos, para que essas operações sejam também rápidas. Por exemplo, http://www.jetbrains.com/idea/openapi/5.0/com/intellij/util/containers/IntArrayList.html

jorgefrancisco:

Olá pessoal, tranquilo?
Tenho que desenvolver uma aplicação que envolve grafos enormes, e para isso estou pensando em utilizar a representação de grafos em listas de adjacência juntamento com outras idéias para melhoria de desempenho.

Você só pode falar de eficiencia se soubre os requisitos do seus sistema. O fato de arraylist ser dinamico pode ser irrelevante se o seu modelo de grafo é estático (ou seja, é carregado uma vez e depois é só lido).
Vc precisa saber o equilibro entre escrita e leitua. E na leitura, se é indexada ou iterativa.
De posse destes dados vc faz a sua escolha.

1. Não use arrays. Usar arrays é para quem sabe o questá fazendo. É como usar float. É preciso ter muito boas razões para usar arrays. Arrays não são polimorficos, logo estará violando a programação orientada a objetos e isso tem consequencias.

ArrayList implementa RandomAccess o que significa que é equivalente ao uso de array para operações get(i). LinkedList é mais lenta nestas operações, mas mais rápida em iteração. ArrayList só é ruim se vc adiconar itens durante a execução. Para um processo em que vc adiciona pouco e lê muito usando get(i) ArrayList é o ideal. Mas se vc adiciona mesmo muito pouco (tipo uma vez na inicialização) e itera a toda a hora considere usar a nova CopyOnWriteArrayList que é ainda mais eficiente.

Se vc faz mais interações do que get(i) não use ArrayList. Use LinkedList. LinkedList é mais rápida na edição e na iteração. Só perde quando usa get(i). Portanto, evite usar get(i) e use LinkedList.

Se vc não usa get(i) e só precisa de List porque precisa conter repetidos, use LinkedList. Se tem a certeza que não existem repetidos e get(i) é inutil use Set. Se os seus objetos são ordenáveis utilize TreeSet, caso contrario use HashSet ( lembre-se de impleemntar equals e hashCode corretamente). Se precisar manter a ordem se insersão use LinkedHashSet.
Set é melhor que list já que pode ser mais eficiente sem suportar get(i).

Portanto?

1. preciso mesmo de suportar duplicados ?
   Sim = List , não = Set

Se escolheu List :
2) Edito mais do que leio, ou leio mais do qu edito ?
Mais leitura = ArrayList (ou CopyOnWriteArraylist se tem mesmo quase nenhuma edição)
Mais edição = LinkedList

3. Só itero ou uso get(i) ? ( não vale pensar em iterar usando get(i) para responder a isto)
   Ou seja, o meu acesso é realmente aleatório ou sempre leio em uma certa ordem ?
   Iteração (ordem) = LinkedList , get(i) ( aleatorio) = ArrayList

3.1) Se o acesso é aleatorio posso substituir por Map ?
Não = mantenha a lista escolhida.
Sim = Map e aplique o mesmo principio de Set ( os prefixo são os mesmos)

Se escolheu Set
4) Os objetos contidos são ordenáveis ( implementam Comparable ou existe um Comparator para eles) ?
Sim = TreeSet
Não = 4.1
4.1) A ordem que itero é realmente importante ou basta passar por todos os itens ?
Importante = LinkedSet , não = HashSet

Claro que exclui concorrencia desta escolha.

lavh:

jorgefrancisco:

Olá pessoal, tranquilo?

Tenho que desenvolver uma aplicação que envolve grafos enormes, e para isso estou pensando em utilizar a representação de grafos em listas de adjacência juntamento com outras idéias para melhoria de desempenho.

Um dos principais requisitos é a rapidez de acesso aos dados do grafo… Para isso, gostaria de saber se um ArrayList, por exemplo, é tão eficiente quanto um vetor (em relação ao acesso indexado, por exemplo). Pergunto isso devido ao fato de ArrayList ser dinâmico e possuir métodos que facilitarão muito o meu trabalho. Ou se esse acesso “indexado” do ArrayList na verdade não é indexado, tendo que percorrer toda a lista para encontrar determinado dado.

Bom… é basicamente isso… desde já, obrigado!

Abraços.

Usar arrays de primitivos como int[] por exemplo será bem mais rápido do que usar ArrayList e outras classes da Collection. E isso é experiência própria. Na “Maratona de Programação” várias soluções só passam por tempo se você usar arrays de primitivos. O mesmo algoritmo mais usando ArrayList não passa. Mas acredito eu, que o fato do ArrayList ter que usar as classes Wrappers colabora muito para essa diferença de velocidade.

Mas enfim, se você precisa de performance, use []. Seu código vai ficar mais feio, mas vai ser mais rápido.

[]'s

Depois de ir 1 vez para a maratona eu fiquei convencido de que lá, usar

import algo;

em Java, não funciona.

Em C++, só uso os

#include <iostream>
#include <string>

E nada mais

Eu trabalhei com um AG de 1600 indivíduos e ordenava eles (usando Bubble ainda). Usando 100 gerações, demorava tipo menos de 40 segundos. Você tá fazendo o Algoritmo do Kruskal? Eu usei o sort e deu beleza. Pra grafos com 30 arestas pra baixo. A primeira vez que demorou pra executar algo em Java foi no AG que eu falei acima.

Abraço!

muito obrigado pelas impressões, pessoal… serão muito úteis, sem dúvida!

Abraços!

Concordo em gênero, número e grau com o thingol e com o sergio.

De onde surgiu isso???

Completamente errado, e por vários motivos:

1. LinkedList tendem a ter seus dados dispersos pela memória, o que provoca falhas de cache e perda drástica de performance ao percorrer a lista;
2. Acessar os índices de um LinkedLIst envolve percorrer a lista inteira. O que é lento.
3. LinkedList ocupa muito mais memória. Há um overhead por elemento.

Nas arquiteturas atuais, mesmo o fato de inserir/remover elementos de um LinkedList não representa um ganho tão significativo quanto anteriormente. Os processadores otimizaram muito cópias de blocos de memória, os caches são maiores (o que aumenta muito o ganho na hora de percorrer um arraylist). São raros os casos que uma lista ligada chega a ser melhor que uma estrutura linear.

Finalmente, teste o seu código várias vezes com um profiler (pode ser o do Netbeans). Ele ajuda a identificar gargalos, que raramente se referem as implementações feitas pela Sun. Não otimize no achismo.

Andre Brito:

E nada mais

Eu trabalhei com um AG de 1600 indivíduos e ordenava eles (usando Bubble ainda). Usando 100 gerações, demorava tipo menos de 40 segundos. Você tá fazendo o Algoritmo do Kruskal? Eu usei o sort e deu beleza. Pra grafos com 30 arestas pra baixo. A primeira vez que demorou pra executar algo em Java foi no AG que eu falei acima

Eu tenho trabalhado com algoritmos genéticos em Java, e não vi grandes diferenças de performance. Você chegou a rodar um profiler no seu código para ver onde estava lento? Geralmente, o que pesa nos AGs é a forma que você implementa a função de Fitness.

Aliás, sua população estava grande hein? Geralmente recomenda-se trabalhar com populações entre 20 até 30 individuos. É difícil ver problemas com domínios maiores.