Uso de uma ferramenta de criação de perfil para auxiliar na análise de um algoritmo de força bruta em Java

5

Pediram-me para criar um perfil (usando alguma ferramenta, como YourKit ou JVisualVM) algumas implementações do Traveling Salesman Problem (encontrar o caminho mínimo que visita todo o conjunto de cidades), no contexto de uma Análise de Algoritmos e pós-graduação em Design.

Levando em consideração a abordagem de força bruta do algoritmo, estou pensando, no entanto, em como usar melhor as ferramentas (por exemplo, JVisualVM) para analisar as complexidades espaciais e temporais do algoritmo. Se não estou em erro, o algoritmo tem complexidade espacial de O (n), já que basicamente cresce linearmente com o número de cidades, enquanto é O (n!) Em complexidade temporal.

A matemática não é o problema aqui.

Depois de jogar um pouco com ambas as ferramentas referidas, estou tendo dificuldade em entender como elas podem ser de alguma utilidade para o meu problema.

Claro, posso ver quais métodos estão sendo usados mais e qual% do tempo está sendo usado em cada um deles, e qual é o tamanho real da memória, de modo que todos possam ser considerados como dicas para otimização.

Mas além disso, e além de ver a% da CPU que está realmente sendo usada (ou acessos de IO, que nunca ocorrem neste programa), não consigo ver como posso realmente aprender algo sobre o algoritmo com essas ferramentas do que a matemática anterior não o fizeram.

Quais devem ser minhas principais preocupações ao usar profilers para a análise de algoritmos? Além disso, eu coloquei recursos básicos de gravação de tempo incorporados no meu programa. Talvez eu pudesse usar as ferramentas de criação de perfil para fazer melhor esse trabalho?

Obrigado

    
por devoured elysium 22.02.2012 / 23:30
fonte

1 resposta

2

Eu normalmente uso a abordagem do Modelo de Diagnóstico de Desempenho (Performance Diagnostic Model - PDM) como ensinado por Kirk Pepperdine (ele é um dos maiores especialistas mundiais em desempenho de Java). Uma das coisas que ele ensina é que o profiler é um bisturi que você usa depois de ter diagnosticado a natureza geral do problema de desempenho / análise que deseja fazer. Você normalmente começa olhando para quem é o consumidor dominante da CPU. Isso pode ser:

  1. Sistema (ou seja, sistema operacional / hardware)
  2. Usuário (que por sua vez se divide na JVM ou no Aplicativo)
  3. Sem dominador (o que geralmente significa falta de CPU)

Então, minha pergunta é: que pergunta você está tentando responder ao analisar essas implementações? É o desempenho deles? Se assim for, então o profiler é realmente o lugar errado para começar (começando com o profiler é equívoco comum que é ensinado).

    
por 22.02.2012 / 23:52
fonte