Est-ce que je viens de prouver que le tamis d’Eratosthenes est moins efficace que la division d’essai?

TL; DR: comparer la vitesse des variantes de code à une seule taille d’entrée n’a pas de sens; La comparaison des ordres de croissance empiriques reflète véritablement la nature algorithmique du code et sera cohérente sur différentes plates-formes de test, pour la même plage de taille de test. La comparaison des valeurs de vitesse absolue n’a de sens que pour les variantes de code présentant le même comportement de croissance asymptotique ou du moins local.

Il ne suffit pas de mesurer la vitesse de vos deux implémentations avec une seule taille d’entrée. En général, plusieurs points de données sont nécessaires pour évaluer les ordres de croissance empiriques de notre code à l’exécution (car le code peut être exécuté avec différentes tailles d’entrée). Il s’agit du logarithme du ratio des temps d’exécution, en base du ratio des tailles d’entrée.

Ainsi, même si, à une entrée code_1 s’exécute 10 fois plus vite que code_2 , mais que son temps d’exécution est doublé à chaque fois que la taille d’entrée est code_2 , alors que pour code_2 il ne grossit qu’à 1.1x , très bientôt, code_2 deviendra beaucoup plus rapide que code_1 .

La véritable mesure de l’efficacité d’un algorithme est donc sa complexité en termes de temps d’exécution (et la complexité de son espace, c’est-à-dire ses besoins en mémoire). Et lorsque nous le mesurons de manière empirique, nous ne mesurons que si, pour le code particulier à scope de main (pour une plage particulière de tailles d’entrée), pas pour l’ algorithme lui-même, c’est-à-dire sa mise en œuvre idéale.

En particulier, la complexité théorique de la division d’essai est O(n^1.5 / (log n)^0.5) , en n nombres premiers produits, généralement vus comme ~ n^1.40..1.45 ordre de croissance empirique (mais cela peut être ~n^1.3 départ, pour des tailles d’entrée plus petites). Pour le tamis d’Eratosthenes, il s’agit de O(n log n log (log n)) , vu généralement par ~ n^1.1..1.2 . Mais il existe certainement des implémentations sous-optimales à la fois de la division d’essai et du tamis d’Ératosthène qui fonctionnent à une valeur inférieure ou égale à ~n^2.0 .

Alors non , cela ne prouve rien. Un sharepoint données n’a pas de sens, il en faut au moins trois pour obtenir une “vue d’ensemble”, c’est-à-dire pour pouvoir prédire avec une certaine certitude le temps d’exécution ⁄ l’espace nécessaire pour des tailles d’entrée plus grandes.

La prévision avec une certitude connue est l’object de la méthode scientifique .

BTW vos temps d’exécution sont très longs. Le calcul de 10 000 nombres premiers devrait être presque instantané, beaucoup moins que 1 / 100ème de seconde pour un programme C exécuté sur une boîte rapide. Peut-être que vous mesurez également le temps d’impression. Ne pas 🙂

Non, le temps d’exécution écoulé n’est pas une norme pour mesurer l’efficacité car il varie d’une plate-forme à l’autre – en disant “mon algorithme a fonctionné en 10 secondes” ne donne que peu, voire aucune, d’informations sur l’algorithme lui-même. En plus de cela, vous auriez besoin de lister l’intégralité des spécifications de l’environnement et des autres processus s’exécutant en même temps, ce qui serait un désastre énorme. D’où le développement des notations d’ordre (Big Oh, Little Oh, Omega, etc.).

L’efficacité est généralement divisée en deux sous-sections:

1. L’efficacité du temps.
2. Efficacité de l’espace.

… où un algorithme peut être extrêmement efficace en termes de temps, mais très inefficace en termes d’espace. Vice-versa s’applique. Les algorithmes sont analysés en fonction de leur comportement asymptotique lors de la mise à l’échelle du nombre d’instructions à exécuter pour une entrée donnée n . Ceci est une explication de très haut niveau sur un domaine qui est minutieusement étudié par des docteurs en informatique – je vous suggère de lire davantage à ce sujet ici pour obtenir la meilleure explication de bas niveau que vous trouverez.

Notez que je joins le lien pour la notation Big Oh – les notations soeurs peuvent toutes être trouvées en dehors de cette page Wikipedia et il s’agit généralement d’un bon sharepoint départ. Il entrera également dans la différence d’efficacité en termes d’espace et de temps.

Petite application de l’efficacité du temps en utilisant Big Oh:

Considérez la fonction récursive suivante dans Racket (serait en Python si je le savais – meilleur pseudo code que je puisse faire):

 (define (fn_a input_a) (cond [(empty? input_a) empty] [(empty? (rest input_a)) input_a] [(> (first input_a) (fn_a (rest input_a))) (cons (first input_a) empty)] [else (fn_a (rest input_a))])) 

… nous voyons ça: empty? , rest , > et tout d’ first sont tous O (1). Nous remarquons également que dans le pire des cas, un appel est fait à fn_a dans les troisième et quasortingème conditions sur le rest de input_a . Nous pouvons alors écrire notre relation de récurrence sous la forme, T (n) = O (1) + 2T (n – 1). En regardant cela sur un graphique de relation de récurrence, nous voyons que fn_a est d’ordre O (2 ^ n) car dans le pire des cas, deux appels récursifs sont effectués.

Il est également important de noter que, par la définition formelle de Big Oh, il est également correct (bien que inutile) de déclarer que fn_a est O (3 ^ n). Lors de l’parsing, de nombreux algorithmes sont définis à l’aide de Big Oh, mais il serait plus approprié d’utiliser Big Theta pour resserrer les limites, ce qui signifie essentiellement: l’ordre le plus bas et le plus précis par rapport à un algorithme donné.

Faites attention, lisez les définitions formelles!

Une durée d’exécution plus longue signifie-t-elle un algorithme moins efficace?

Pas nécessaire. L’efficacité du programme est mesurée non seulement par le temps qu’il prend, mais aussi par les ressources qu’il prend. L’espace est un autre facteur dont il faut tenir compte tout en tenant compte de l’efficacité.

Du wiki : –

Pour une efficacité maximale, nous souhaitons minimiser l’utilisation des ressources. Cependant, les différentes ressources (par exemple, le temps et l’espace) ne peuvent pas être comparées directement. Le choix de l’algorithme considéré comme le plus efficace dépend souvent de la mesure de l’efficacité considérée comme la plus importante. , ou pour une utilisation minimale de la mémoire, ou pour une autre mesure?

En général: oui, mais quand vous êtes dans la tranche inférieure à 1 seconde, il y a beaucoup de bruit qui peut être déroutant …

Exécute chaque test plusieurs fois et utilise des statistiques sur les résultats (par exemple, moyenne ou moyenne / écart en fonction de l’importance de vos préoccupations)

Et / ou l’obliger à travailler plus fort – comme trouver un plus grand nombre de nombres premiers

En bref, oui, si par efficacité, vous entendez gagner du temps. Il y a aussi des considérations de mémoire.

Faites attention quand vous mesurez – assurez-vous que vos outils de chronométrage sont précis.

Assurez-vous de mesurer sur la même machine lorsque rien d’autre n’est en cours d’exécution.
Assurez-vous de mesurer plusieurs fois et prenez une moyenne et la varinace pour une comparaison décente.
Demandez à quelqu’un de vérifier votre code pour vérifier qu’il fait ce que vous pensez qu’il est en train de faire.

L’efficacité des algorithmes se mesure normalement à l’efficacité avec laquelle ils gèrent de grandes entrées. 10 000 nombres n’est pas une entrée très importante, vous devrez peut-être en utiliser un plus grand avant que le tamis d’Ératosthène ne devienne plus rapide.

Alternativement, il peut y avoir un gros dans une de vos implémentations

Enfin, l’efficacité des algorithmes peut être mesurée par la quantité de mémoire nécessaire (mais cette mesure est moins courante, d’autant plus que la mémoire est si bon marché de nos jours).