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

19

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?

a
la source
Bienvenue! J'espère que la plupart de ces papiers n'utilisent pas les temps d'exécution. Je sais que certains le font, cependant, en particulier dans les communautés les plus appliquées et lorsque les systèmes considérés sont très complexes.
Raphael

Réponses:

14

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.

Raphael
la source
1
Gardez à l'esprit que l'analyse formelle a aussi ses limites. Par exemple, le cas moyen des distributions d'entrée non uniformes est souvent insoluble.
Raphael
10

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 .

Chris Howell
la source
1
De plus, le temps d'exécution réel dépend de la taille et du contenu de l'entrée réelle utilisée pour exécuter les algorithmes!
Tsuyoshi Ito
7

É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 )
Sasho Nikolov
la source
1) "au moins autant de comparaisons sont effectuées que toute autre opération élémentaire" - jusqu'à un facteur constant. 2) "les comparaisons sont l'opération coûteuse" - cela suppose un paramètre générique. Pour le tri d'entiers (qui est généralement analysé), les swaps sont généralement plus chers.
Raphael
sûr. op semblait confus quant à l'analyse des algorithmes en général, ne voulait pas apporter des facteurs constants. j'espère que le fait que je parle d'un paramètre générique ressort clairement de la description - la routine de tri dans une bibliothèque standard n'est pas un tri entier
Sasho Nikolov
ainsi que les articles que op a vu ne concernent certainement pas les algorithmes de tri d'entiers spécialisés, personne ne compte le nombre de comparaisons
Sasho Nikolov
@Raphael Le tri des petits entiers n'est pas un problème courant dans la pratique. Je parie que le tri le plus courant au monde se fait sur des chaînes (d'une certaine longueur ou d'une autre ). Même pour le tri d'entiers, je ne sais pas s'il est exact que les swaps sont plus chers - la branche est une opération relativement coûteuse sur un processeur haut de gamme moderne, car la prédiction de branche serait pour la plupart inutile pour le tri.
Gilles 'SO- arrête d'être méchant'
@Gilles En soi, les échanges sont plus chers que les comparaisons entières que n'importe quelle plate-forme que je connais. Les coûts "secondaires" comme, par exemple, les erreurs de prédiction des succursales sont certainement un facteur dont l'impact fait l'objet de recherches continues. (En ce qui concerne l'utilisation dans la pratique, je ne peux pas faire de déclaration qualifiée. Cependant, j'observe que les responsables de bibliothèques standard continuent d'améliorer les algorithmes de tri qu'ils utilisent pour les types de données primitifs, je suppose donc qu'ils voient beaucoup d'utilisation (ab).)
Raphael