Comment mesurer le nombre d'opérations effectuées

Dans mon projet actuel, je mesure la complexité des algorithmes écrits en Java. Je travaille avec une complexité asymptotique (résultat attendu) et je veux valider l'attente par comparaison avec le nombre réel d'opérations. Utiliser Incrematation par opération me semble un peu maladroit maladroit. Y a-t-il une meilleure approche pour mesurer la complexité opérationnelle?Comment mesurer le nombre d'opérations effectuées

Merci

Edit: Plus d'infos

Les algorithmes peuvent fonctionner sur des machines différentes
Certaines parties d'algorithmes diviser pour mieux régner pourrait être premier cache, il est donc probable que les la procédure sera plus rapide que prévu
Il est également important pour moi de trouver la constante multiplicative (ou la constante additive), qui n'est pas pris en compte dans la complexité asymptotique

Source

2012-06-03 malejpavouk

Sur un ordinateur réel dont vous souhaitez mesurer le temps d'exécution, getCurrentTimeMillis(). Varier le paramètre N, obtenir des statistiques solides. Faire une estimation d'erreur. Vos moindres carrés de base iront bien.

Le comptage des opérations sur un algorithme est correct, mais son utilisation est limitée. Différents processeurs font des choses à des vitesses différentes. Compter le nombre d'expressions ou d'instructions exécutées par votre algorithme implémenté est presque inutile. Dans l'algorithme, vous pouvez l'utiliser pour faire des comparaisons pour le peaufinage, dans votre implémentation ce n'est plus le cas, les trucs du compilateur/JIT // CPU domineront.

Le comportement asymptotique devrait être très proche de la valeur calculée/attendue si vous faites de bonnes mesures.

Source

2012-06-03 19:02:01

Le problème est un peu plus complexe. Parce que je m'attends à résoudre des algorithmes de division et de conquête. Et je pourrais avoir une solution partielle pré-mise en cache. Je m'attends donc à faire beaucoup mieux que ne le suggère la complexité asymptotique ... Et je veux savoir quelle est la meilleure implémentation avec les données que la «complexité attendue». – malejpavouk

Oui, mesurer, mesurer et mesurer; et n'espérez pas. Vous pourriez vouloir partager votre D & C dans la question. –

Y a-t-il une raison particulière de ne pas mesurer uniquement le temps CPU? L'utilitaire de temps ou un profileur vous obtiendra les chiffres. Il suffit de lancer chaque algorithme avec une gamme suffisante d'entrées et de capturer le temps CPU (pas l'heure de l'horloge murale) dépensé.

Source

2012-06-03 17:53:03 easel

Oui, il pourrait fonctionner dans plusieurs environnements et les résultats ne seront pas comparables ... – malejpavouk

Ah, je vois. Je pense que ça va être vraiment dur - vous finirez par comparer l'efficacité du compilateur, du vm, de l'os et du processeur en plus de la complexité algorithmique. Je recommande d'isoler d'abord la complexité algorithmique sur une seule machine, puis d'étendre le champ et de comparer à nouveau. – easel

ByCounter peut être utilisé pour instrumenter Java (sur plusieurs classes) et compter le nombre de bytecodes exécutés par la JVM lors de l'exécution.

Source

2014-07-10 14:56:46

Comment mesurer le nombre d'opérations effectuées

Répondre

Questions connexes