J'ai une série de fonctions qui sont toutes conçues pour faire la même chose. Les mêmes entrées produisent les mêmes sorties, mais le temps qu'il faut pour les faire varie selon la fonction. Je tiens à déterminer lequel est "le plus rapide", et je veux avoir une certaine confiance que ma mesure est "statistiquement significative".
Périoler Wikipedia et les interwebs me disent que la signification statistique signifie qu'une mesure ou un groupe de mesures est différente d'une hypothèse nulle par un seuil de valeur P. Comment cela s'appliquerait-il ici? Quelle est l'hypothèse nulle entre la fonction A être plus rapide que la fonction B?
Une fois que je suis défini dans toute la configuration, comment puis-je comprendre quand arrêter de mesurer? Je verrai généralement qu'un point de repère est exécuté trois fois, puis la moyenne est rapportée; Pourquoi trois fois et non cinq ou sept? Selon Cette page sur la signification statistique (que j'avoue librement que je ne comprends pas complètement), pêcheur utilisé 8 comme nombre d'échantillons qu'il avait besoin pour mesurer quelque chose avec une confiance de 98%; Pourquoi 8?
5 Réponses :
La question fondamentale que vous essayez de répondre est la difficulté que ce que vous observez aurait pu arriver par hasard? Ce salon de monnaie est-il? Jetez-la une fois: têtes. Non, ce n'est pas juste, il descend toujours des têtes. Mauvaise conclusion! Jetez-le 10 fois et obtenez-vous 7 têtes, maintenant qu'est-ce que vous concluez? 1000 fois et 700 têtes?
Pour des cas simples, nous pouvons imaginer comment comprendre quand arrêter de tester. Mais vous avez une situation légèrement différente - faites-vous vraiment une analyse statistique?
Combien de contrôle avez-vous de vos tests? Les répétent-ils d'ajouter une valeur? Votre ordinateur est déterministe (peut-être). La définition de la folie de Eistein est de répéter quelque chose et d'attendre un résultat différent. Donc, lorsque vous exécutez vos tests, obtenez-vous des réponses répétables? Je ne suis pas sûr que des analyses statistiques aident si vous faites des tests suffisants.
Pour ce que vous faites, je dirais que la première chose clé est de vous assurer que vous mesurez vraiment ce que vous pensez. Exécutez chaque test pour suffisamment longtemps que des effets de démarrage ou d'arrêt sont cachés. Les tests de performance utiles ont tendance à courir pendant de longues périodes pour cette raison. Assurez-vous de ne pas mesurer le temps dans votre harnais de test plutôt que dans votre code.
Vous avez deux variables principales: combien d'itérations de votre méthode à exécuter dans un seul test? Combien de tests à courir?
wikipedia dit ceci
en plus d'exprimer le variabilité d'une population, standard la déviation est couramment utilisée pour mesurer confiance en conclusions statistiques. Par exemple, la marge d'erreur dans Les données de vote sont déterminées par calculer la norme attendue déviation dans les résultats si le même le sondage devait être mené plusieurs fois. La marge d'erreur rapportée est typiquement environ deux fois la norme Déviation.
Par conséquent, si votre objectif est de vous assurer qu'une fonction est plus rapide qu'une autre, vous pouvez exécuter un certain nombre de tests de chacun, calculez les moyens et les écarts types. Mon attente est que si votre nombre d'itérations dans un test à un seul test est élevé, la déviation type va être faible.
Si nous acceptons cette définition de la marge d'erreur, vous pouvez voir si les deux moyens sont plus éloignés que leur marge totale d'erreur.
Chaque fois que je passe un test, je reçois un nombre légèrement différent pour la vitesse. C'est juste la façon dont l'analyse comparative va-- Un environnement informatique moderne n'est pas contrôlé, car quelqu'un d'autre a déjà signalé. Ainsi, exécutez le même test deux fois donnera des réponses de vitesse différentes, mais pas de résultats différents.
J'ai mis à jour la réponse à suggérer de regarder l'écart type.
Vous souciez-vous vraiment de la signification statistique ou de la vieille signification particulière? En fin de compte, vous êtes susceptible d'avoir à former un jugement sur la lisibilité contre la performance - et la signification statistique ne va pas vraiment vous aider là-bas.
Un couple de règles de pouce que j'utilise:
Dans la mesure du possible, testez-vous de temps pour vous faire confirmer que de petites blips (comme quelque chose d'autre interrompant votre test pendant une courte période) ne fera pas beaucoup de différence. Habituellement, je pense que 30 secondes suffisent pour cela, bien que cela dépend de votre application. Plus vous testez-vous, plus le test sera fiable sera - mais évidemment, vos résultats seront retardés :)
exécutant un test plusieurs fois peut être utile, mais si vous timingez pendant assez longtemps, il n'est pas aussi important d'OMI. Cela atténuerait d'autres formes d'erreur qui ont fait un test prendre plus de temps qu'il ne le devrait. Si un résultat de test est suspect, dirigez-vous certainement. Si vous voyez des résultats significativement différents pour différentes exécutions, passez-la plusieurs fois plus et essayez de repérer un motif.
Je me soucie vraiment de la signification statistique; Je tiens à indiquer, avec confiance numérique, que cette fonction ou cette approche est plus rapide que cette approche sur une configuration informatique donnée. Pour vos tests, pourquoi 30 secondes? D'où vient ce nombre? Intuition basée sur l'expérience? Et vous dites 'courir plusieurs fois plus de fois' - combien de fois? Existe-t-il une formule ou juste un calcul de l'enveloppe de dos?
Si la différence n'est pas absolument évidente alors allez simplement avec la version plus lisible. C'est presque toujours la meilleure façon d'y aller. Quant à 30 secondes - oui, intuition basée sur l'expérience. En ce qui concerne "combien de fois encore" - jusqu'à ce que vous ayez un ensemble de chiffres qui semblent raisonnables. Tout simplement basé sur le sentiment d'intestin.
+1 sur des différences absolument évidentes. Dans les statistiques, nous avons appelé ce "test de percussion inter-oculaire" (aka "il vous frappe juste entre les yeux").
La recherche que votre site ressemble plus à un environnement hautement contrôlé. C'est une réponse purement pratique qui s'est révélée du temps et de nouveau pour être efficace pour les tests de performance.
Si vous utilisez un code d'analyse comparative dans un environnement moderne, multi-noyau, multicœur, informatique, le nombre d'itérations nécessaires à la réalisation d'une référence utile augmente car la durée de l'opération à mesurer diminue. < / p>
Donc, si vous avez une opération qui prend environ 5 secondes, vous voudrez généralement 10 à 20 itérations. Tant que la déviation à travers les itérations reste assez constante, vos données sont suffisamment saines pour tirer des conclusions. Vous voudrez souvent jeter la première itération ou deux deux parce que le système réchauffe généralement des caches, etc.
Si vous testez quelque chose dans la gamme Millisecond, vous voudrez 10 milliers d'itérations. Cela éliminera le bruit causé par d'autres processus, etc., tirant.
Une fois que vous avez frappé la gamme de sous-millisecondes - 10s de nanosecondes - vous voudrez des millions d'itérations.
Pas exactement scientifique, mais non plus "dans le monde réel" sur un système informatique moderne.
Lors de la comparaison des résultats, examinez la différence de vitesse d'exécution en pourcentage, pas absolue. Quelque chose de moins d'environ 5% de différence est assez proche du bruit.
Mais pourquoi 10 à 20? D'où vient ces chiffres? Y a-t-il une formule ou devinez-vous simplement? Pourquoi 5% pour le bruit, et non, dit quelque chose qui concerne les écarts types de la vitesse?
Je ne me dérangerais pas d'appliquer des principes de statistiques aux résultats d'analyse comparative. En général, le terme "signification statistique" fait référence à la probabilité que vos résultats obtenaient accidentellement et ne représentent pas une évaluation précise des véritables valeurs. En statistiques, à la suite d'une probabilité simple, la probabilité qu'un résultat obtenu par hasard diminue, le nombre de mesures augmente. Dans l'analyse comparative du code informatique, il s'agit d'une affaire triviale d'augmenter le nombre d'essais (la "N" dans les statistiques) afin que la probabilité d'un résultat accidentel soit inférieure à tout seuil arbitraire que vous souciez de définir (l'alpha "ou le niveau de signification statistique).
Simplifier: référence en exécutant votre code un grand nombre de fois et ne vous inquiétez pas des mesures statistiques .
Note aux électeurs potentiels de cette réponse: cette réponse est quelque peu une simplification de la matière, conçue pour illustrer les concepts de manière accessible. Des commentaires comme "Vous ne comprenez clairement pas les statistiques" entraîneront un battement sauvage. N'oubliez pas d'être poli.
Mais par combien de "probabilité qu'un résultat obtenu par hasard diminue à mesure que le nombre de mesures augmente"? Où est le point acceptable de dire, d'accord, la probabilité est assez basse maintenant ... Appelez-la 0,5% de chances que mes résultats soient bons? Ou que cette routine est X% plus rapide qu'une autre routine et ma confiance en x% est de 99%?
@mmr: Si vous avez deux routines (A et B), et que vous les exécutions chacun de 1 000 000 fois, et que le temps moyen pour A est 1 ms et la durée moyenne de B est 2 ms, la question de la statistique est la suivante: «Compte tenu de la < i> hypothèse que A et B en réalité prennent la même quantité de temps, quelle est la probabilité que b purement par hasard mesuré deux fois aussi longtemps que A? " La réponse est la suivante: "So DAMN près de 0 que vous pourriez aussi bien dire 0".
@MMR: Les méthodes statistiques en général sont conçues pour approximativement des mesures de populations inconnues de grandes populations en mesurant des échantillons relativement petits et en extrapolant de là. Dans l'analyse comparative du code informatique, vous n'êtes de manière pratique limitée à mesurer de petits échantillons. Les méthodologies statistiques ne sont donc pas nécessaires.
@Musigeneis: Bien sûr, mais vous venez de le gérer un million de fois. Peut-être que vous pourriez faire la même déclaration à propos d'être «si damné près de zéro» à 1000 points. Où est ce seuil? Et qu'est-ce qui est "tellement près de zéro"? 0.001?
@Musigenesis # 2: Pourquoi n'est-ce pas nécessaire? Pourquoi n'est-ce pas comme une autre mesure scientifique?
@MMR: Les valeurs alpha standard en statistiques sont 0,05 et 0,01. Je parle plus comme .00000001, des ordres de grandeur en dessous de toute valeur alpha raisonnable.
@MMR: Comme je l'ai déjà mentionné, des méthodologies statistiques ont été conçues pour estimer les propriétés des populations trop volumineuses pour être comptées directement. Le code informatique ne souffre pas de ce problème.
@Musigenèse: Nous arrivons maintenant à ce que je veux savoir :) Qu'est-ce qu'une valeur alpha? Comment le déterminez-vous? Et comme pour "ne pas souffrir de ce problème", mon problème est que ces routines prennent l'ordre des heures à courir (c'est un code de traitement de l'image de levage lourd que j'essaie d'optimiser), donc je ne peux donc pas raisonnablement gérer le code un million de fois et encore terminé ce mois-ci.
@MMR: La valeur alpha est essentiellement à quel point vous êtes prêt à faire une erreur de type I, c'est-à-dire comment vous êtes prêt à rejeter une hypothèse nulle qui est réellement vraie. Dans mon exemple A et B ci-dessus, choisir un alpha de 0,05 signifierait que lors de l'exécution de tests de comparaison comme celle-ci, vous êtes prêt à vous tromper (en d'autres termes, de dire que B est plus lent qu'un quand il n'est pas) 5% du temps.
@MMR: Si chaque routine prend des heures à courir, c'est une sorte de problème différent. Je suppose que votre routine implique réellement une ou plusieurs petites pièces de code qui sont appelées encore et encore. Si tel est le cas, vous ferez mieux de mettre en place des tests de référence de ces sous-programmes plus petits et de les comparer.
Pour compliquer davantage ce problème, puisque vous voulez savoir généralement quelles méthodes sont meilleures Lorsqu'elles sont exécutées sur une variété de machines / environnements différentes, votre "N" doit faire référence au nombre de machines différentes que vous exécutez activement. , afin de généraliser correctement vos résultats. Lorsqu'il est exécuté sur votre machine, vous n'assumez vraiment que les vitesses relatives sur cette machine.
@Musigenèse: Donc, s'il y a une erreur de type I, quelle est l'hypothèse nulle de comparer deux fonctions? Qu'ils sont la même vitesse? Ou cela est plus rapide que b? Indépendamment de la temps d'exécution, je veux toujours pouvoir dire (pour des raisons politiques qui sont longues et ennuyeuses) que A est plus rapide que B, ou inversement, avec une description de confiance numérique. Lorsque je regarde les erreurs de type I sur Wikipedia, je n'ai toujours pas de sens du nombre de mesures dont vous aurez besoin, quelle est la question ultime ici.
@MMR: Dans ce cas, l'hypothèse nulle est que les deux fonctions sont la même vitesse. Si vous avez ensuite utilisé un test statistique à queue, vous pourriez dire que B est plus rapide qu'un (avec une .01 alpha ou autre), ou si vous avez utilisé un test statistique à deux queues, vous pourriez dire que B était différent d'un (plus rapide ou plus lent). Vous n'utiliseriez probablement qu'un test à queue si vous aviez une raison a priori de penser que B serait plus rapide, plutôt que simplement différent.
@MMR: Vous pouvez voir, compte tenu du nombre de choix à votre disposition pour quelque chose comme celui-ci, comment il est généralement le cas que la généralisabilité des résultats statistiques est souvent sévèrement surestimée (sans quoi ils peuvent facilement être manipulés pour produire la volonté souhaitée. Conclusions).
@MMR: Un point supplémentaire - Les formules pour calculer la signification statistique incorporent toujours la variance dans les mesures. Si la variance est élevée (ce qui signifie que les mesures sont différentes, par exemple 2, 1, 7, 25, 8, 50, etc.), il est alors difficile de rejeter l'hypothèse nulle. Si la variance est faible (par exemple 2, 2, 2, 2, 3, 2, 2), il est plus facile de rejeter NULL. En termes de laïcs, plus de cohérence dans les données indique une plus grande fiabilité de l'estimation.
@MMR: C'est pourquoi vous ne pouvez pas simplement dire que vous avez besoin d'un nombre arbitraire de mesures (comme 8, par exemple) pour obtenir un niveau de confiance donné. La valeur N nécessaire dépend de la variance de l'échantillon.
@MMR: point final (pour réel cette fois) - Les mesures de référence informatique ont généralement une variance incroyablement faible. Un ensemble donné d'instructions prend presque exactement la même durée chaque fois qu'ils sont courants. Donc, en plus des ordinateurs pouvant facilement générer un grand N, ils ont seulement besoin un petit n.
Vous posez deux questions:
A est supérieure à la durée moyenne de la fonction B ?
- Si vous voulez une certaine confiance dans votre réponse, combien d'échantillons devriez-vous prendre?
La réponse la plus courante à la première question est que vous souhaitiez soit calculer un Intervalle ou effectuez un T-Test . Ce n'est pas différent de toute autre expérience scientifique avec une variation aléatoire. Pour calculer l'intervalle de confiance de 95% du temps de réponse moyen pour la fonction, il suffit de prendre la moyenne et d'ajouter 1,96 fois l'erreur standard de chaque côté. L'erreur standard est la racine carrée de la variance divisée par N. c'est-à-dire, xxx où sigma2 est la variance de la vitesse pour fonction A et N Est-ce que le nombre de courses que vous avez utilisés pour calculer la moyenne et la variance. Votre deuxième question concerne Statistique Analyse de la puissance et la conception des expériences. Vous décrivez une configuration séquentielle dans laquelle vous vous demandez si vous souhaitez continuer à échantillonner. La conception d'expériences séquentielles est en fait un problème très délicat dans les statistiques, car, en général, vous n'êtes pas autorisé à calculer les intervalles de confiance ou les valeurs de P, puis tirer des échantillons supplémentaires conditionnels à ne pas atteindre votre signification souhaitée. Si vous souhaitez faire cela, il serait plus sage de mettre en place un modèle bayésien et de calculer votre probabilité postérieure que la vitesse a est supérieure à la vitesse B. Ce, cependant, est une overcilleuse massive.
dans un environnement informatique Il est généralement assez trivial d'obtenir un très petit intervalle de confiance, car le dessin important N est facile et parce que la variance est généralement petite - une fonction gagne évidemment.
Étant donné que Wikipedia et la plupart des sources en ligne sont encore horribles Quand il s'agit de statistiques, je vous recommande d'acheter Statistiques d'introduction avec R . Vous apprendrez à la fois les statistiques et les outils pour appliquer ce que vous apprenez.
Merci pour la référence! Mais supposons que j'ai déjà pris des échantillons. Puis-je calculer CI's pour des trois pistes échantillonnées de N, puis de 4, puis de 5, et etc., jusqu'à N, pour déterminer si j'ai déjà frappé un seuil au moment où je reçois le temps que je reçois à N? D'après ce que vous dites, "vous n'êtes pas autorisé à calculer les intervalles de confiance ni les valeurs de p ..." Mais si j'ai déjà rassemblé les données, est-ce que ça va? Pourquoi ne puis-je pas simplement vérifier les données que je dois voir si j'ai besoin de continuer?
Il convient parfaitement à ce que vous voulez de faire des données de pré-test. Vous pouvez jouer autour de vous et voir ce que n vous donne le type d'intervalle de confiance que vous désirez. Toutefois, lorsque vous calculez votre intervalle de confiance final, vous ne pouvez pas la baser sur un échantillon où N est une fonction des caractéristiques de cet échantillon particulier (c'est-à-dire des observations précédentes de N-1). La question à garder à l'esprit est la suivante: la procédure que j'utilise pour choisir N conduit à un résultat équivalent à N tirages aléatoires? Par exemple, augmenter N jusqu'à ce que le CI soit inférieur à 1, créez toujours CI inférieur à 1, alors que l'échantillonnage au hasard N ne le fera pas.