Pourquoi utiliser des comparaisons au lieu de l'exécution pour comparer deux algorithmes?

Je remarque que dans quelques articles de recherche CS, pour comparer l'efficacité de deux algorithmes, le nombre total de comparaison clé dans les algorithmes est utilisé plutôt que les temps de calcul réels eux-mêmes. Pourquoi ne pouvons-nous pas comparer lequel est le meilleur en exécutant les deux programmes et en comptant le temps total nécessaire pour exécuter les algorithmes?

Il s'agit en fait d'un problème profond qui a des réponses méthodiques et pragmatiques. Je suppose que vous voulez savoir quelque chose sur les algorithmes à portée de main. Si vous voulez savoir quel algorithme fonctionne mieux sur une machine donnée sur des entrées données, allez-y et mesurez les temps d'exécution. Si vous souhaitez comparer la qualité d'un compilateur pour un algorithme donné, allez-y et mesurez les temps d'exécution. Pour apprendre quelque chose sur l'algorithme, ne le faites pas.

Permettez-moi d'abord de vous expliquer pourquoi l'utilisation des runtimes n'est pas une bonne idée.

1. Généralités Les temps d'
   exécution mesurés à l'aide d'un langage et d'un compilateur sur une machine ont peu de sens si vous modifiez un composant. Même des implémentations légèrement différentes du même algorithme peuvent fonctionner différemment car vous déclenchez une certaine optimisation du compilateur dans le cas mais pas dans l'autre.
2. Prédiction
   Vous disposez donc de deux temps d'exécution pour certaines entrées. Qu'est-ce que cela indique sur le temps d'exécution d'une autre entrée? En général, rien.
3. Signification
   Généralement, vous ne comparez pas toutes les entrées (d'une certaine taille), ce qui restreint immédiatement votre capacité à comparer les algorithmes: peut-être que votre ensemble de tests a déclenché le pire des cas dans l'un et le meilleur des cas dans l'autre algorithme? Ou peut-être que vos entrées étaient trop petites pour présenter le comportement d'exécution .
4. Mesure Bien
   mesurer les temps d'exécution n'est pas anodin. Existe-t-il un JIT? Y a-t-il eu des conflits, c'est-à-dire que vous comptez le temps que l'algorithme n'a même pas exécuté? Pouvez-vous reproduire exactement le même état de machine pour une autre exécution (de l'autre algorithme), en particulier les processus simultanés et les caches? Comment la latence de la mémoire est-elle gérée?

J'espère que ceux-ci vous ont convaincu que les temps d'exécution sont une horrible mesure pour comparer les algorithmes et qu'une méthode générale et abstraite pour enquêter sur le temps d'exécution des algorithmes est nécessaire.

Passons à la deuxième partie de la question. Pourquoi utilisons-nous des comparaisons ou des opérations élémentaires similaires?

1. Tractabilité analytique
   En supposant que vous vouliez faire une analyse formelle, vous devez être en mesure de le faire. Le comptage des déclarations individuelles est très technique, parfois même difficile; certaines personnes le font néanmoins (par exemple Knuth). Compter seulement quelques instructions - celles qui dominent le runtime - est plus facile. Pour la même raison, nous enquêtons souvent «uniquement» (limites supérieures sur) le pire cas d'exécution.

2. Dominance
   L'opération sélectionnée domine le runtime. Cela ne signifie pas qu'il contribue le plus à l'exécution - les comparaisons ne le font clairement pas, par exemple dans Quicksort lors du tri des entiers de la taille d'un mot. Mais ils sont exécutés le plus souvent , donc en les comptant, vous comptez la fréquence d'exécution des parties les plus exécutées de l'algorithme. Par conséquent, votre temps d' exécution asymptotique est proportionnel au nombre d'opérations élémentaires dominantes. C'est pourquoi nous sommes à l'aise avec la notation Landau et le mot "runtime" même si nous ne comptons que les comparaisons.

Notez qu'il peut être utile de compter plus d'une opération. Par exemple, certaines variantes de Quicksort prennent plus de comparaisons mais moins de swaps que d'autres (en moyenne).

Pour ce que ça vaut, après avoir fait toute la théorie, vous voudrez peut-être revoir les temps d'exécution afin de vérifier que les prédictions faites par votre théorie sont solides. Si ce n'est pas le cas, votre théorie n'est pas utile (en pratique) et doit être étendue. La hiérarchie de la mémoire est l'une des premières choses que vous réalisez est importante mais manquante dans les analyses de base.

Cela est dû au fait que le temps total d'exécution des algorithmes dépend du matériel sur lequel il s'exécute ainsi que d'autres facteurs. Il n'est pas fiable de comparer deux algorithmes si l'un s'exécute sur un Pentium 4 et l'autre sur, disons, un Core i7. Non seulement cela, mais disons que vous avez exécuté les deux sur le même ordinateur. Que dire qu'ils ont tous deux le même temps processeur? Que se passe-t-il si un autre processus a une priorité plus élevée que le processus de l'un des algorithmes?

Pour dépasser cela, nous nous découplons de ce temps global pour terminer, et comparons plutôt en fonction de la façon dont l'algorithme évolue. Vous avez peut-être remarqué une notation telle que O (1) ou O (n ^ 2) dans les articles de recherche. Cela peut nécessiter un peu plus de lecture, si vous êtes intéressé , voir la notation Big O .

Étant donné que les autres réponses expliquent pourquoi nous analysons le temps d'exécution en termes de nombre d'opérations élémentaires, permettez-moi d'expliquer quelques raisons pour lesquelles les comparaisons sont la bonne métrique de nombreux (pas tous) algorithmes de tri:

• pour de nombreux algorithmes de tri, le nombre de comparaisons domine le temps d'exécution, c'est-à-dire qu'au moins autant de comparaisons sont effectuées que toute autre opération élémentaire
• les comparaisons sont l' opération coûteuse ; pensez à la façon dont une routine de tri est implémentée dans la bibliothèque: la fonction de tri reçoit un tableau d'éléments et un pointeur sur une fonction qui compare deux éléments; en général, appeler et attendre l'exécution de la fonction de comparaison coûte plus cher que les opérations "internes"; comme cette fonction est fournie par l'utilisateur, il est plus difficile de l'optimiser
• (cela peut ou non être une bonne raison pour certains) nous pouvons dire quelque chose d' intéressant sur le nombre de comparaisons qui sont suffisantes et nécessaires pour trier une séquence; nous savons comment le faire dans le pire des cas et en moyenne pour diverses distributions, même comment concevoir un algorithme qui converge vers l'optimale car il est exécuté sur des éléments échantillonnés iid à partir d'une distribution inconnue ( Self-Improving Algorithms ); nous savons comment procéder lorsque certaines comparaisons sont fournies gratuitement ( Tri avec informations partielles )