Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

msr

PriorityQueue vs sorted LinkedList

Mensagens Recomendadas

msr

Olá,

Qual das implementações é menos pesada: uma PriorityQueue ou uma LinkedList ordenada (usando um Comparator)?

O que pretendo é ter uma lista ordenada (ou que o elemento retirado do topo seja o mais prioritario) e de vez a vez percorre-la toda usando um interador por forma a fazer algumas operações.

Percorre-la toda so o vou fazer de vez em quando, a inserção de elementos é que é bastante frequente.

Obrigado

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Knitter

A única forma exacta de medir seria implementado com as duas e experimentar :D

No entanto, se a inserção é algo frequente, uma ArrayList é mais rápida se a lista tiver sido criada com uma capacidade suficiente para os elementos. A arraylist não tem o peso da criação dos nós, mas tem o peso de, sempre que for necessário inserir elementos além da capacidade, aumentar a capacidade da mesma.

A questão do elemento do topo ser prioritário parece-me algo que podes implementar tu, acedendo ao elemento inicial em detrimento dos outros.

No fundo a diferença entre as implementações só é significativa em casos particulares, na maioria dos casos não é relevante.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
msr

Hmmm... acho que me vou ficar então pela que der menos trabalho visto os ganhos não serem significativos. Devo por uma priorityqueue visto que para a linkedlist teria que ter o Comparator (o Comparable acaba por ser mais pratico neste caso) e tinha que correr o método sort() explicitamente.

A ArrayList não serve porque a dimensão é imprevisivel. A unica coisa que tenho a certeza é que pode aumentar bastante. Depende de um parametro introduzido ao programa, fazendo com que a dimensão da lista chegue ao final do programa com uma dimensao desde a ordem das dezenas às dezenas de milhares.

Obrigado pela sugestão!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Knitter

Não percebi isso de teres de usar um comparador, podes simplesmente implementar o método compareTo e a interface Comparable em qualquer collection do Java.

De qualquer modo, em relação a performance, só mesmo implementado com os tipos de listas que tens dúvidas e depois comparar, porque sem isso é complicado saber qual é melhor. Tipicamente escolho pelo tipo de dados que quero guardar, há situações onde a LinkedList é a escolha natural, outras onde usar uma ArrayList é melhor. Aqui recomendo que escolhas o tipo de estrutura que te ajudar a resolver o problema, que seja mais natural de usar.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
msr

Não percebi isso de teres de usar um comparador, podes simplesmente implementar o método compareTo e a interface Comparable em qualquer collection do Java.

Tens razão! Na altura estava a pensar que só dava para usar o Comparator com a LinkedList, mas depois apercebi-me que não era assim.

Obrigado!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.