Existe-t-il une norme pour comparer les temps d'exécution expérimentalement?

10

Ma situation

J'écris un article présentant un module logiciel que j'ai développé et je veux comparer son temps d'exécution à d'autres modules pour la même tâche. Je suis conscient des inconvénients des expériences d'exécution , mais supposez, étant donné qu'il n'y a aucun moyen de contourner cela dans mon cas. (Je peux théoriquement déduire certaines propriétés, mais cela ne suffit pas pour tout.)

Les scénarios spécifiques que je veux utiliser pour l'analyse comparative ont deux paramètres: la complexité  du problème et une graine aléatoire  qui détermine le problème détaillé. Je veux surtout montrer la dépendance de  . En partant des investigations préliminaires et de la théorie, l'influence de sur le temps d'exécution est mineure ou négligeable. Une seule tâche prend au plus dix minutes.r n rnrnr

Question réelle

Je recherche une procédure communément acceptée ou publiée sur la réalisation de telles expériences ou au moins une liste des pièges courants (idéalement publiés).

Ce que j'ai trouvé jusqu'à présent

Rien. Les recherches sur Internet produisent toutes sortes de résultats non liés, mais je n'utilise peut-être pas la bonne terminologie. Y compris le mot-clé minimum, que je sais être un bon standard (voir ci-dessous), n'a pas aidé non plus.

Comment je le ferais

  • Exécutez toutes les expériences sur la même machine avec un logiciel potentiellement interférent tel qu'une interface graphique désactivée autant que possible.

  • Soumettez tous les modules à la même sélection de scénarios, c'est-à-dire les mêmes et  .rnr

  • Pour chaque scénario, testez les différents modules directement les uns après les autres dans un ordre aléatoire. En d'autres termes, la boucle sur les différents modules est la plus interne. Cela devrait éviter les biais sur les différents modules en raison des fluctuations lentes des performances de la machine (par exemple, en raison des changements de température). L'ordre aléatoire devrait éviter les biais à travers des effets tels que la mise en cache ou un module toujours testé après le même.

  • Pour chaque , prenez le temps d'exécution minimum sur plusieurs scénarios avec différentes graines comme référence. Cela devrait éviter les biais sur les différents modules en raison des fluctuations de courte durée des performances de la machine qui rendent les exécutions individuelles exceptionnellement mauvaises.n

algorithm-analysis reference-request runtime-analysis experimental-analysis Wrzlprmft
la source
Cela pourrait aider à expliquer votre raisonnement pourquoi vous pensez "qu'il n'y a aucun moyen de contourner cela dans mon cas". Mais bien sûr, probablement comme une question distincte et un lien, car cette question est suffisamment bien ciblée.
Apiwat Chantawibul
@Billiska: Je ne sais pas exactement ce que vous voulez que je fasse. Pourquoi devrais-je expliquer mon raisonnement pour une approche expérimentale dans une question distincte? Je n'ai aucune question à ce sujet.
Wrzlprmft
Je dois être en désaccord avec vous en prenant le temps d'exécution minimum de l'expérience répétée. Vous semblez penser qu'il pourrait y avoir uniquement un contour vers le haut. Serait-il possible d'avoir également un contour vers le bas? Il est plus courant d'examiner simultanément plusieurs statistiques, par exemple, moyenne, médiane, max. Qui sait qu'ils peuvent montrer quelque chose à quoi vous ne vous attendiez pas. C'est une expérience empirique après tout.
Apiwat Chantawibul
2
C'est très large; des livres peuvent être écrits sur le sujet, par exemple "A Guide to Experimental Algorithmics" de McGeoch. On pourrait même dire que vous demandez: "Existe-t-il une norme pour faire de la science?". Je ne suis donc pas sûr que cette portée soit raisonnable. Vous avez des questions plus spécifiques?
Raphael
2
Lâchement liés: cs.stackexchange.com/q/39597/755 , cs.stackexchange.com/q/29854/755 , cs.stackexchange.com/q/74178/755 .
DW

Réponses:

2

Le "Guide de l'algorithmique expérimentale" de CC McGeoch est une bonne référence pour

  • comment mettre en place des expériences sur les algorithmes,
  • comment interpréter et utiliser les résultats, et
  • comment itérer vers des résultats plus significatifs si nécessaire.
Raphael
la source
2

En plus du temps écoulé pour chaque exécution, signalez les secondes du mode utilisateur et système, ainsi que le nombre total de paquets IP et le nombre total d'E / S de disque, ne serait-ce que pour vérifier que certains nombres sont systématiquement "faibles" et ont un impact négligeable sur le temps écoulé.

Sur https://wiki.freebsd.org/BenchmarkAdvice PHK et d'autres offrent de bons conseils, y compris

Utilisez ministat pour voir si vos chiffres sont significatifs. Pensez à acheter un "Guide des statistiques sur les dessins animés"

J_H
la source