Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
msr

PriorityQueue vs sorted LinkedList

Recommended Posts

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

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.