Discussion :

[Virgile le chat]

Bonjour,
Dans tout cours qui traite de la complexité on trouve que le temps mis pour effectuer une somme est proportionnel à la taille des entiers mis en jeu.. Plus précisément, proportionnel à max( Log2(m), Log2(n) ), théorie mathématique à l'appui. Or quand je fais le test sous Python, je trouve un temps constant ! J'ai beau mettre de petits entier ou de grands entier, le résultat est toujours le même (environ 2 * 10^(-6) s sur ma machine).
Quelqu'un a-t-il une explication.
Merci bien.

[Jedai]

J'espère bien que ta machine fait une addition d'entier en moins d'1 microseconde, même en Python !!

Il y a essentiellement deux possibilités :

1. La précision de tes mesures est discutable... Et visiblement elle l'est si tu crois qu'une addition prend 1 microseconde.
2. Qu'appelle-tu un "grand" entier ? Tant que tu restes en dessous de 2^63 (+ de 10^18), il est assez probable que Python stocke ses entiers dans des entiers machines et que donc le coût d'une addition soit assez constant. C'est quand tu dépasses ces limites que les entiers commencent à être stockés et additionnés avec des algorithmes en O(log(max(n,m))).

--
Jedaï

[Virgile le chat]

pourtant voici mon programme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
from time import time
 
m = eval(input("entrer m : "))
n = eval(input("entrer n : "))
 
t0 = time()
m + n
t1 = time()
 
print(((t1 - t0)) * 10**6)

j'obtiens toujours environ 2... donc 2 microsecondes... mon ordi est-il si lent ? ou ai-je fais une erreur. L'unité est bien en secondes ??

[Jedai]

... Quelle précision exactement attends-tu de time() ? Selon l'OS, tu peux avoir quelque chose de très mauvais, mais au mieux, tu ne dépasses pas la microseconde, donc ton expérience indique tout au plus que l'addition prend moins de 2 microsecondes.

Pour faire un benchmark, on répète toujours l'opération qu'on souhaite mesurer. Et normalement, une boucle est suffisante. Mais ici, vu l'opération, tu as de bonne chance que tu mesures plutôt le coût de la boucle que celui de l'opération.

Peut-être :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from time import time
 
m = int(input("entrer m : "))
n = int(input("entrer n : "))
 
t0 = time()
for i in range(10**7) :
  m + n
  m + n
  m + n
  m + n
  m + n
  m + n
  m + n
  m + n
  m + n
  m + n
t1 = time()
 
print((t1 - t0)*10)

Mais je ne garantis en rien la précision de la mesure résultante... Enfin ça devrait être mieux (et en nanosecondes).

--
Jedaï

[FR119492]

Salut!

Dans tout cours qui traite de la complexité on trouve que le temps mis pour effectuer une somme est proportionnel à la taille des entiers mis en jeu.

Cet exemple montre bien que l'enseignement de la complexité est une aberration. Dans un processeur normal, le temps nécessaire pour calculer la somme de deux nombres est indépendant de la valeur des ces deux nombres.
Jean-Marc Blanc

[Prof]

Bonjour.

Dans tout cours qui traite de la complexité on trouve que le temps mis pour effectuer une somme est proportionnel à la taille des entiers mis en jeu.

J'ai l'impression que, dans la discussion qui précède, la " valeur " des entiers a été confondue avec la " taille ".

[Jedai]

Cet exemple montre bien que l'enseignement de la complexité est une aberration. Dans un processeur normal, le temps nécessaire pour calculer la somme de deux nombres est indépendant de la valeur des ces deux nombres.

Je doute fortement que tu trouves beaucoup de cours sur la complexité où il est affirmé que l'addition de deux entiers se fait en O(log(max(n,m)) sans un rappel (ou un préalable) que l'addition de deux entiers machines (donc limités en taille, ce qui a son importance dans certains contextes, scientifique en particulier) est une opération à coût constant... (nonobstant ce que l'étudiant inattentif s'en rappelle)

De plus, si tu crois vraiment que le coeur de l'enseignement de la complexité est sur la complexité des opérations arithmétiques élémentaires et que c'est pour ça que les gens suivent un cours sur la question, tu es vraiment complètement à côté de la plaque.

Cette question était assez naïve mais elle a permis à Virgile d'aborder plusieurs points importants : déjà avoir une idée de l'ordre de grandeur du temps pris par une opération élémentaire est important, de plus faire un benchmark est rarement évident, surtout pour du code aussi rapide, il y a une différence entre les entiers machines (sur 32 ou de plus en plus, sur 64 bits) et les entiers mathématiques, de taille illimitée (sauf par la mémoire).

J'ai l'impression que, dans la discussion qui précède, la " valeur " des entiers a été confondue avec la " taille ".

La valeur ou plutôt le logarithme de la valeur est proportionnel à la taille nécessaire au stockage d'un entier (toujours en supposant qu'on ne se contente pas d'entiers machines), donc la distinction a peu d'importance.

--
Jedaï