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

Algoritmo de procura (em conjunto com um de ordenação)

Recommended Posts

msr

Olá,

Estou a fazer um programa em Java e tenho o seguinte:

Uma PriorityQueue que me garante que sempre que tiro um elemento (instancia da classe Evento), esse é o mais prioritário. Um Evento está associado a uma Entidade.

Em certas alturas do programa (e frequentemente) preciso de remover da PriorityQueue todos os eventos que estejam associados a uma Entidade "x".

Para isso estou a percorrer a PriorityQueue com um iterador, mas acho que essa é uma solução pesada dado que o tamanho da priorityqueue pode ser bastante grande (para dimensões da ordem dos milhares, o programa já se arrasta bastante).

A ideia será encontrar nessa PriorityQueue os eventos associados com determinada entidade o mais depressa possivel (e posteriormente remove-los).

De que forma é que acham que posso alcançar melhor desempenho neste caso?

Obrigado

Share this post


Link to post
Share on other sites
Edo

Quantas entidades diferentes é que tens? Quantas prioridades diferentes é que tens?

Share this post


Link to post
Share on other sites
Warrior

A questão do Edo é relevante, mas podes sempre guardar quais os eventos associados a cada entidade à parte, e depois remover explicitamente esses elementos.

Share this post


Link to post
Share on other sites
msr

O que estou a fazer é percorrer a prirorityqueue com um iterador e remover todos os eventos que estejam associados à entidade. Até agora foi o método mais eficiente que encontrei :bored:

A prioridade é por tempo. Cada evento tem um tempo associado, o mais prioritário é o evento com tempo menor.

Instancias de Entidade são muitas. Quantas mais suportar (mantendo desempenho aceitável) melhor. O número de eventos que que vão para a priorityqueue é aproximadamente o triplo das entidades que existem.

As entidades multiplicam-se a elas próprias, mas existe um número limite. Se por exemplo esse limite for de 1000 chego a um ponto do programa em que o número máximo aproximado de eventos na priorityqueue é de cerca de 3000. Neste caso o programa já precisa de cerca de 4segundos para terminar.

Share this post


Link to post
Share on other sites
Warrior

Não sei que linguagem estás a usar, mas percorrer e remover elementos numa priority queue com 3000 elementos devia ser tão rápido que nem darias por tal.

Aliás, percorrer e remover elementos numa priority queue de 1000000 de elementos demora menos de um segundo em qualquer PC normal.

Verifica a tua implementação porque certamente existe um erro algures. A função de comparação entre elementos é em tempo constante?

Share this post


Link to post
Share on other sites
msr

Estou a usar JAVA. As funcoes/metodos de comparação/igualdade têm todas tempo constante sim.

Mas tenho que analisar melhor o código tenho.

E adicionar elementos a uma priorityqueue tambem deve ser assim tao rapido?  Com cerca de 5000 elementos já se nota bem o "arrastanço". Mas não é certamente só disso, ha outras operações que puxam recursos e são realizadas muito frequentemente. Adicionar massivamente elementos à priorityqueue, percorre-la para remoção de elementos, uma linkedlist na ordem dos milhares de elementos que deve ser tambem ordenada (não a ordeno depois de adicionar cada elemento, ordeno-a apenas quando preciso mesmo dela ordenada) e não sei se me está a escapar mais alguma coisa.

A priorityqueue é uma pilha de eventos (cada um com um tempo definido). Cada entidade cria inicialmente 3 eventos, e por cada evento simulado é lançado um novo. O que tenho de fazer é simular esses eventos até um instante final (introduzido como parâmetro). Isto é, em cada evento a ser simulado há tambem código a consumir recursos, ie, a "engonhar" e a atrasar o final do programa.

Vou olhar para o código e ver se consigo por mais alguma coisa a funcionar mais eficientemente.

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.