Otimizei meu algoritmo O(n^7) com goto, agora ele é um O(n^5 log n) sem goto! Para n=25, caiu de 1 minuto para 2 segundos.
Troquei 4 loops aninhados por 3 dijkstras consecutivos. A parte ruim é que o método ficou comprido, cada dijkstra é levemente diferente do outro e eu não consegui achar um jeito de encapsular isso de um jeito reusável. Ficou com cara de copy and paste.
Se alguém quiser conferir, o método é o unreachable_iterator:
antes, linha 330: http://ideone.com/mwTh9O
depois, linha 379: http://ideone.com/CbGumR
Troquei 4 loops aninhados por 3 dijkstras consecutivos. A parte ruim é que o método ficou comprido, cada dijkstra é levemente diferente do outro e eu não consegui achar um jeito de encapsular isso de um jeito reusável. Ficou com cara de copy and paste.
Se alguém quiser conferir, o método é o unreachable_iterator:
antes, linha 330: http://ideone.com/mwTh9O
depois, linha 379: http://ideone.com/CbGumR
Nenhum comentário:
Postar um comentário