Algumas divagações:
1) O site do EP na cos226 pede que usemos o algoritmo de dijkstra. Isso é obrigatório ou podemos explorar outras alternativas mais eficientes?
2) O unit test é necessário nesse EP?
Também gostaria de nao utilizar dijkstra
Olá Victor e Raphael,
Desculpem pela demora...
O site do EP na cos226 pede que usemos o algoritmo de dijkstra. Isso é obrigatório
Após muito meditar ... acho que devemos fazer como pede o enunciado: encontrar caminho de menor energia usando o algoritmo de Dijkstra e a estrutura IndexMinPQ. Suponho que a ideia seja desenvolver uma melhor compreensão do algoritmo de Dijkstra.
Ainda, como diz o checklist, não usem a estrutura EdgeWeightedDigraph.
Executem o algoritmo diretamente nos pixels (o digrafo fica implícito).
Migrei de uma implementação (sem Dijkstra) para a outra (com Dijkstra) muito rapidamente.
Se for pra usar IndexMinPQ da algs4, então temos que considerar na nossa implementação necessariamente uma função de Z² -> Z que leva o endereço do pixel (i, j) num outro inteiro, certo?
Oi Alessandro,
Se for pra usar IndexMinPQ da algs4, então temos que considerar na nossa implementação necessariamente uma função de Z² -> Z que leva o endereço do pixel (i, j) num outro inteiro, certo?
Legal!
Eu fiz exatamente isso, mas talvez alguém tenha outra ideia.
Teve algo parecido no percolation.
Certo
Mudando de assunto, queria tocar num ponto que está me incomodando um pouco, é em relação ao tempo de execução. No exemplo de execução que está na página do EP15, o código rodou em uns 10 segundos. Aqui em casa, depois de otimizar o máximo que consegui, cheguei em uns 60 segundos.
Penso que essa diferença se deve a capacidade de processamento do hardware, uma vez li em algum lugar que o seu processador é um core 2 quad blablabla, enquanto o meu processador é um mobile dual core da década passada.
Só que ainda estou com a pulga atrás da orelha, será que a diferença no tempo de execução se deve só ao hardware ou existe algum macete pra otimizar ainda mais o código?
Ois,
será que a diferença no tempo de execução se deve só ao hardware ou existe algum macete pra otimizar ainda mais o código?
Legal você ter levantado essa questão.
No computador que estou agora tenho duas versões do EP15.
Um delas da os tempos que estão no enunciado e que usa o algoritmo de busca em caminho mínimo em um digrafo acíclico (examina os pixels em ordem topológica). Neste computador com esse algoritmo obtenho:
% java ResizeDemo seamCarving/HJocean.png 200 100
768-by-432 image
new image size is 568 columns by 332 rows
Resizing time: 13.921 seconds.
Já, usando o algoritmo de Dijkstra, como você devem fazer.
Dijkstra não tira proveito do digrafo dos pixels ser acíclico.
Os pixels são examinados na ordem de distâncias a partir da borda.
Usando esse algoritmo obtenho:
% java ResizeDemo seamCarving/HJocean.png 200 100
768-by-432 image
new image size is 568 columns by 332 rows
Resizing time: 36.469 seconds.
Em ambas implementações o digrafo é implícito, como sugere o checklist.
Acho que tudo ajuda.
O algoritmo e o hardware.
O computador que estou usando:
% more /proc/meminfo
MemTotal: 4008052 kB
[...]
% more /proc/cpuinfo
model name : AMD FX(tm)-4300 Quad-Core Processor
cpu MHz : 1400.000
cache size : 2048 KB