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

msr

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

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

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.