Utilizzo di uno strumento profiler per l'analisi di un algoritmo di forza bruta in Java

5

Mi è stato chiesto di creare un profilo (utilizzando alcuni strumenti, come YourKit o JVisualVM) un paio di implementazioni del Problema del venditore ambulante (trovare il percorso minimo che visita tutto il gruppo dato di città), nel contesto di un'analisi degli algoritmi e corso di laurea in Design.

Considerando l'approccio della forza bruta dell'algoritmo, mi chiedo, tuttavia, come utilizzare al meglio gli strumenti (ad esempio, JVisualVM) per analizzare le complessità spaziali e temporali dell'algoritmo. Se non sono in errore, l'algoritmo ha una complessità spaziale di O (n), in quanto cresce sostanzialmente in modo lineare con il numero di città, mentre è O (n!) Nella complessità temporale.

La matematica non è il problema qui.

Dopo aver giocato un po 'con entrambi gli strumenti di riferimento, ho difficoltà a capire come possono essere utili al mio problema.

Certo, posso vedere quali metodi vengono utilizzati di più e quale% del tempo viene utilizzato in ognuno di essi, e qual è l'effettivo footprint di memoria, in modo che tutti possano essere considerati suggerimenti su dove ottimizzare.

Ma a parte questo, oltre a vedere la% della CPU che viene effettivamente utilizzata (o gli accessi IO, che non si verificano mai in questo programma), non riesco a vedere come posso imparare qualcosa sull'algoritmo con questi strumenti rispetto alla matematica prima di cui non ha fatto.

Quali dovrebbero essere le mie principali preoccupazioni quando utilizzo i profiler per l'analisi degli algoritmi? Inoltre, ho inserito le funzionalità di registrazione del tempo di base incorporate nel mio programma. Forse potrei usare gli strumenti di profilazione per fare meglio quel lavoro?

Grazie

    
posta devoured elysium 22.02.2012 - 23:30
fonte

1 risposta

2

In genere utilizzo l'approccio PDM (Performance Diagnostic Model) come insegnato da Kirk Pepperdine (è un esperto di livello mondiale sulle prestazioni Java). Una delle cose che insegna è che il profiler è un bisturi che usi una volta diagnosticata la natura generale del problema / analisi delle prestazioni che vuoi fare. In genere inizi a guardare chi è il consumatore dominante della CPU. Questo può essere:

  1. Sistema (cioè Sistema operativo / Hardware)
  2. Utente (che a sua volta si divide in JVM o nell'applicazione)
  3. Nessun dominatore (che in genere significa fame di CPU)

Quindi la mia domanda è: a quale domanda stai cercando di rispondere analizzando queste implementazioni? È la loro performance? Se è così allora il profiler è in realtà il posto sbagliato da cui iniziare (a cominciare dal profiler è l'equivoco comune che viene insegnato).

    
risposta data 22.02.2012 - 23:52
fonte

Leggi altre domande sui tag