Discussion :

[yaya793]

Bonsoir a tous,
Je suis tout nouveau sur le forum, c'est la premiere fois que je publie et vous remercie deja pour toutes les précieuses aides que j'ai pu avoir grace a ce site.
Voila, je démarre en python, et je bloque sur un exercice.
En réalité le code que j'ai mis en place fonctionne, mais a partir du moment ou j'ai un nombre extrêmement élevé de valeurs a prendre en compte ( de l'orde de 10**4 minimum) la console m'affiche un message d'erreur spécifiant que la compilation est terminée due a un trop long temps de compilation.
Voici mon code:

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
import random
import math
 
num=[random.randint(1,10**4) for i in range(10**5)]
k= random.randrange(10**7)
print("le nombre de coupe est de {}".format(k))
print("le tableau de base est {}".format(num))
while k!=0:
    a=max(num)
    pos=num.index(a)
    b=math.ceil(a/2)
    num[pos]=b
    k=k-1
print("le nouveau tableau est {}".format(num))
somme=sum(num)
print("la somme est de {}".format(somme))

Celui a pour but de créer un tableau dans lequel il y a un nombre de valeurs compris entre 0 et 10^5, et ou chacune des valeur vaut entre 1 et 10**4.
On définit un nombre k qui signifie le nombre de fois ou on va diviser un nombre du tableau par 2.
Ex: num=[4,5,7,9]
k=2
Le 1e chiffre : on prend le chiffre 9 qu'on divise par 2, le résultat obtenue arrondi a l'entier supérieur remplace le chiffre en question
Le 2e Chiffre: on prend le chiffre 7 qu'on divise par 2, le résultat obtenue arrondi a l'entier supérieur remplace le chiffre en question
Les deux coupes ( correspondant a k=2) ont été faites.
On calcul la somme des valeurs du tableau.
Le but de l'exercice est d'obtenir la somme la plus petite

Mon problème est donc que des qu'on passe dans des nombres extrêmement élevé la machine ne me donne plus de résultat.
J'ai entendu parler de list comprehension mais je n'ai pas réussi a en créer.
Si quelqu'un peut me donner un coup de main pour le réaliser ou une idée je suis preneur

Désolé par avance pour le long bloc

Bonne soirée a tous

[fred1599]

Une seule question,

Quel est l'intérêt d'afficher une liste de 100 000 valeurs ?

[yaya793]

Il n'y a pas spécialement d'intérêt.
C'est une des conditions de l'exercice que j'essaye de resoudre

[fred1599]

S'il n'y a pas d'intérêt alors ne le fait pas ! Surtout que cette partie est sans doute celle qui bloque ton programme...

Affiche juste la somme et ça devrait aller.

[yaya793]

J'ai retenté sans l'affichage des tableaux, mais le résultat reste identique.
Le message d'erreur est :

Compiler message:
Terminated due to timeout

[fred1599]

Le message d'erreur est:
"
Compiler message:
Terminated due to timeout
"

À quel endroit exactement ?

[yaya793]

Il n'y a pas plus de precision avec ce message

[fred1599]

Pourquoi les variables a et pos sont dans la boucle ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
import random, math
 
num=[random.randint(1,10**4) for i in range(10**5)]
k= random.randrange(10**7)
print("le nombre de coupe est de {}".format(k))
a=max(num)
pos=num.index(a)
while k!=0:
    b=math.ceil(a/2)
    num[pos]=b
    k=k-1
somme=sum(num)
print("la somme est de {}".format(somme))

[yaya793]

la variable a est dans la boucle pour que a chaque fois qu'on fait tourner la boucle, la division par 2 d'un nombre ce fait sur le plus grand nombre de la liste pour qu'a la fin on est la plus petite somme possible.
De même pour la variable pos.

J'ai l'impression que c'est pas nécessaire finalement...

[fred1599]

Avec ton code fait des print sur ta variable a, puis sur ta variable b et enfin ta variable pos, regarde les résultats, et voit si des variables sont sans intérêts.

J'ai l'impression que certaines semblent pas obligatoires, mais j'ai pas bien compris l'objectif de l'exercice, malgré ce que tu expliques précédemment.

[yaya793]

L'idée c'est qu'on part d'un tableau avec un nombre élevé de variable a l'intérieur.
On définit un nombre k, ce nombre représente un nombre de mouvement.
Il faut minimiser la valeur de la somme des variables du tableau
En sachant que le mouvement est : diviser par 2 un terme du tableau et mettre la nouvelle valeur a sa place

J'ai essayer de faire comme vous m'avez dis mais ca fonctionne moins bien qu'avant

[fred1599]

J'ai essayer de faire comme vous m'avez dis mais ca fonctionne moins bien qu'avant

Ce que je demande est d'observer les variations de tes variables. Te semblent-elles cohérentes, logiques par rapport à ton algorithme ?

Est-ce que votre problème a un nom scientifique ? À la limite si je peux voir l'algorithme, ça m'aidera à comprendre le vôtre...

[yaya793]

Le code que j'ai envoyer de base fonctionne a merveille quand je rentre un tableau de petite taille.
C'est quand ca s'agrandit que ca se complique.

Je n'ai malheureusement pas le nom de l'algorithme même en ayant chercher un peu sur internet.

[lg_53]

Pour ce genre de traitement (tableau de grande taille avec recherche de min ou de max ou d'opération arithmétique) on fait mieux que des listes. Il existe une librairie dédié : Numpy

Si tu ne veux pas passer par numpy il faut trouver un autre algorithme plus performant. Par exemple plutot que de rechercher le max à chaque fois, pourquoi ne pas trier le vecteur de départ ? Ainsi l'opération de diviser en 2 vous l'appliquer au 1er terme, puis au 2eme (ou encore au 1er si celui ci est toujours plus grand que le second), puis au 3eme, etc, jusqu'à tant que la variation totale du vecteur vous satisfasse. Là vous n'avez plus à rechercher la position de la valeur max. Soit c'est la valeur en cours encore (une valeur qui était très grande, et qui même après avoir été divisée par 2 reste plus grande que les autres) soit c'est la valeur suivante.

Et si on ne veut pas à la fin avoir le vecteur avec ses composantes mélangées, et bien on peut garder en mémoire quelque part la clé de tri, et s'en resservir à la fin pour remettre la nouvelle liste dans le meme ordre que l'ancienne.

[lg_53]

Résultat assez éloquant avec numpy :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import random, math
 
from time import time
import numpy as np
 
nb_val = 10**2
##nb_val = 10**4
##nb_val = 10**5
 
num=[random.randint(1,10**4) for i in range(nb_val)]
k= random.randrange(10**7)
print("le nombre de coupe est de {}".format(k))
 
t0 = time()
while k!=0:
    a=max(num)
    pos=num.index(a)
    b=math.ceil(a/2)
    num[pos]=b
    k=k-1
t1=time()
 
somme=sum(num)
print("la somme est de {}".format(somme))
print("Temps d'execution: %d seconds"%(t1-t0))
 
####### Methode avec numpy
 
num = np.random.randint(1,10**4,nb_val)
### Je garde le meme k que precedemment
 
t0 = time()
while k!=0:
    pos=num.argmax(num)  ### On cherche ici la position du max directement
    num[pos]=math.ceil( num[pos]/2 )
    k=k-1
t1=time()
 
somme=np.sum(num)
print("la somme est de {}".format(somme))
print("Temps d'execution: %d seconds"%(t1-t0))

Me donne en sortie :

Code :

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

1
2
3
4
5
le nombre de coupe est de 3627315
la somme est de 100
Temps d'execution: 22 seconds
la somme est de 441989
Temps d'execution: 0 seconds

qui est donc au moins 22 fois plus rapide, et dont la rapidité peut encore être améliorée si là aussi on trie l'array en amont.

PS : code testé et éxécuté avec le compilateur en ligne https://repl.it/repls/WrithingOutlandishLanserver

[fatbob]

D'autant que dans le programme proposé, on recherche (au maximum) 10**7 fois le max dans une liste de 10**5. Ça commence à faire beaucoup. Si l'algo évite ce calcul ça ne sera pas neutre :-)

[fatbob]

Je pense qu'il y a une erreur dans le test :-] : le k décrémente jusqu'à 0 puis y reste ensuite. Donc le test avec numpy n'est pas fait.
Ce qui explique entre autre la somme très importante si l'on considère le nombre de divisions pas 2 effectuées.

[lg_53]

Je pense qu'il y a une erreur dans le test :-] : le k décrémente jusqu'à 0 puis y reste ensuite. Donc le test avec numpy n'est pas fait.
Ce qui explique entre autre la somme très importante si l'on considère le nombre de divisions pas 2 effectuées.

Oups bien vu, le while modifie k, qui donc vaut déjà 0 à l'entrée de la 2eme boucle. Je pourrais donc faire un k1 et un k2, que j'initialise au départ avec la même valeur. Bon après je vais pas non plus abuser ici sur le nombre de variable : autant ne pas s'embêter, on connait le nombre d'itération à l'avance donc dans ce cas là on utilise un for et pas un while, et là k ne bouge plus donc je n'ai plus le problème.

Et en effet là la différence avec numpy est un peu moins grande tout de même :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import random, math
 
from time import time
import numpy as np
 
nb_val = 10**2
##nb_val = 10**4
##nb_val = 10**5
 
num=[random.randint(1,10**4) for i in range(nb_val)]
k= random.randrange(10**7)
print("le nombre de coupe est de {}".format(k))
 
t0 = time()
for i in range(k):
    a=max(num)
    pos=num.index(a)
    b=math.ceil(a/2)
    num[pos]=b
t1=time()
 
somme=sum(num)
print("la somme est de {}".format(somme))
print("Temps d'execution: %d seconds"%(t1-t0))
 
####### Methode avec numpy
 
num = np.random.randint(1,10**4,nb_val)
### Je garde le meme k que precedemment
 
t0 = time()
for i in range(k):
    pos=np.argmax(num)  ### On cherche ici la position du max directement
    num[pos]=math.ceil( num[pos]/2 )
t1=time()
 
somme=np.sum(num)
print("la somme est de {}".format(somme))
print("Temps d'execution: %d seconds"%(t1-t0))

donne :

Code :

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

1
2
3
4
5
le nombre de coupe est de 4493048
la somme est de 100
Temps d'execution: 29 seconds
la somme est de 100
Temps d'execution: 27 seconds

[Sve@r]

Bonjour

J'ai entendu parler de list comprehension mais je n'ai pas réussi a en créer.

Si tu as un souci de taille et que Python ne peut plus étaler, les listes par compréhension ne solutionneront pas ton problème car c'est toujours Python qui bosse.

Les listes par intension (ou par compréhension, les deux termes sont autorisés) permettent de créer des listes à la volée à partir d'un itérable en entrée.
Exemple:

Code python :

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

1
2
a=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
b=[x**2 for x in a]

Ici b est créé comme prenant chaque élément de a mis au carré. Ca remplace en fait l'écriture classique

Code python :

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

1
2
3
a=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
b=[]
for x in a: b.append(x**2)

On peut ausi écrire b=[x**2 for x in range(10)] pour montrer que l'entrée n'est pas nécessairement un tableau mais peut aussi être n'importe quel truc pourvu qu'il soit itérable. Mais c'est juste un raccourci d'écriture, pas un gain de mémoire ou de performances.