Discussion :

[tbc92]

J'ai des bases très faibles en Python, mais je me débrouille globalement en programmation.

Je veux faire un truc comme ça :

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
 
for i1 = 1 to  n1 step p1
  for i2 = 1 to n2 step  p2
      for i3 = 1 to n3 step p3
          if ok00 (i1,i2,i3)  then 
             for i4 = 1 to n4 step p4
                 for i5 = 1 to n5 step p5
                     if ok01 (i1,i2,i3, i4, i5)  then 
                        for i6 = 1 to n5 step p6
                             if f(i1,i2,i3,i4,i5,i6) <   best_resultat  then       best_data = (.... )
                        next i6
                     end if
                 next i5
             next i4
         end if
      next i3
   next i2
next i1

En vrai, j'ai même 11 boucles imbriquées. Et je recherche le minimum d'une certaine fonction.
Je peux éliminer certaines combinaisons (les fonctions ok00 et ok01 .... qui font intervenir des fonctions trigo ou autres).
Les pas p1, p2, p3 ... seraient tout petit à l'idéal, mais pour des raisons de performance, je vais devoir faire des impasses.

En fonctionnant ainsi , je sais globalement faire.

Mais je sais que ce n'est pas du tout 'Python' comme manière de procéder. Et que ça risque d'être atrocément long. Et quitte à faire comme ça, je ne vais pas utiliser Python.

Je viens d'installer Python, pour faire un truc comme ça :

Code :

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

1
2
3
aa = range(10)
bb= range(15)
dd = [[aa[i] , bb[j] , bb[k]  ] for i in range(len(aa) ) for j in range(len(bb) ) for k in range(len(bb) )    ]

Et là, premier challenge, comment supprimer certaines lignes de dd, par exemple supprimer les lignes telles que x^3+ y^3+ 5*z^3 serait un multiple de 7 ?
Ou comment ne pas les insérer au moment de créer dd !

Et quand je vais exploiter dd , comment je vais récupérer dd.x, dd.y et dd.z ??


Quand vous m'aurez aidé à passer cette étape, j'aurai forcément d'autres questions !

[Sve@r]

Salut

Je veux faire un truc comme ça :

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
 
for i1 = 1 to  n1 step p1
  for i2 = 1 to n2 step  p2
      for i3 = 1 to n3 step p3
          if ok00 (i1,i2,i3)  then 
             for i4 = 1 to n4 step p4
                 for i5 = 1 to n5 step p5
                     if ok01 (i1,i2,i3, i4, i5)  then 
                        for i6 = 1 to n5 step p6
                             if f(i1,i2,i3,i4,i5,i6) <   best_resultat  then       best_data = (.... )
                        next i6
                     end if
                 next i5
             next i4
         end if
      next i3
   next i2
next i1

Si les boucles imbriquées sont toutes identiques (même début, même fin, même step) alors tu peux utiliser itertools.product().

Exemple

Code python :

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

1
2
3
4
for i1 in range(0, 10, 3):
	for i2 in range(0, 10, 3):
		for i3 in range(0, 10, 3):
			print(i1, i2, i3)

Ou bien...

Code python :

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

1
2
3
4
import itertools
for x in itertools.product("".join(str(x) for x in range(0, 10, 3)), repeat=3):
	(i1, i2, i3)=map(int, x)
	print(i1, i2, i3)

Je viens d'installer Python, pour faire un truc comme ça :

Code python :

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

1
2
3
aa = range(10)
bb= range(15)
dd = [[aa[i] , bb[j] , bb[k] ] for i in range(len(aa)) for j in range(len(bb)) for k in range(len(bb))]

Et là, premier challenge, comment supprimer les lignes telles que x^3+ y^3+ 5*z^3 serait un multiple de 7 ?

En Python on ne "supprime" pas X, on "garde" not(X).
dd = [[aa[i], bb[j], bb[k]] for i in range(len(aa)) for j in range(len(bb)) for k in range(len(bb)) if ((aa[i]**3 + bb[i]**3 + 5*bb[k]**3) % 7) != 0].

Et quand je vais exploiter dd , comment je vais récupérer dd.x, dd.y et dd.z ??

for d in dd: print(d[0], d[1], d[2]).

[tbc92]

Merci !!

[tbc92]

Pour supprimer les lignes introduites à tort, ou pour ne pas les insérer...

On m'a expliqué un jour que dans Python, il faut éviter les boucles, et il faut 'factoriser' le code en manipulant des tableaux.

En gros :

Code :

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

tableau3 = associe_tableaux(tableau1, tableau2, condition_filtre)

Plutôt que :

Code :

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

1
2
3
Pour tout élément1 de tableau1 
  Pour tout élemént2 de tableau2
    Si condition_filtre (element1, element2) alors insère dans tableau3.

Je sais faire la boucle, j'ai fait ça des milliers de fois dans différents langages.

J'ai tendance à croire que ce conseil qu'on m'a donné, c'est un très bon conseil. Et en tout cas, pour l'efficacité ou pour le fun, c'est ce que je vais essayer de respecter sur ce mini chantier.

[tyrtamos]

Bonjour,

Je me suis amusé il y a ... un certain temps (2008!) à trouver un moyen de créer des boucles imbriqués "à la volée" dans un programme, sans en connaitre le nombre au départ.

Voilà la logique:

On crée la liste des arguments de range des variables de boucles.
Par exemple: boucles = [[1, 5, 2], [0, 3, 1], [1, 4, 1]] correspondrait à:

Code :

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

1
2
3
4
5
6
for i in range(1, 5, 2):
    for j in range(0, 3, 1):
        for k in range(1, 4, 1):
            #...
            print(i, j, k)
            #...

Dans la partie la plus profonde des boucles, on va calculer la valeur de tous les indices de boucles de la façon suivante:

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
boucles = [[1, 5, 2], [0, 3, 1], [1, 4, 1]]
 
compteurs = [x[0] for x in boucles]  # => initialisation des compteurs de boucle (= valeur initiale de boucle)
compteurs[-1] -= boucles[-1][2]  # le 1er incrément sera pour rien
indmax = len(boucles)-1  # => index de la dernière boucle (la plus interne)
finboucle = False  # => drapeau pour condition de fin de la boucle globale
 
while True:
    # incrémentation des compteurs, test de boucle et condition de sortie
    for x in range(indmax, -1, -1):
        compteurs[x] += boucles[x][2]
        if compteurs[x]>=boucles[x][1]:
            if x==0:
                finboucle = True
                break
            compteurs[x] = boucles[x][0]
        else: break
    if finboucle: break
 
    # =====> partie utile de la boucle <=====
    # ...
    print(compteurs)
    # ...

L'exécution donne:

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
[1, 0, 1]
[1, 0, 2]
[1, 0, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
[3, 0, 1]
[3, 0, 2]
[3, 0, 3]
[3, 1, 1]
[3, 1, 2]
[3, 1, 3]
[3, 2, 1]
[3, 2, 2]
[3, 2, 3]

Dans chacune de ces listes, vues dans la partie la plus profonde des boucles, le 1er élément donne i, le second j et le 3ème k. Ce qui veut dire que les indices des boucles s'obtiennent par: compteurs[0], compteurs[1], compteurs[2]

On voit bien la progression des indices de boucles.

Plus d'infos sur mon site: https://python.jpvweb.com/python/mes...les_imbriquees

J'aime bien le principe de ce calcul, mais ça date de 13 ans: peut-être pourrait-on faire mieux maintenant?

[Sve@r]

J'aime bien le principe de ce calcul, mais ça date de 13 ans: peut-être pourrait-on faire mieux maintenant?

Oui je pense...

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
 
def genere_boucle(*boucles):
	# Initialisation du résultat
	res=[x[0] if len(x) > 1 else 0 for x in boucles]
 
	# Travail de génération (présumé infini)
	while True:
		# On commence par retourner le résultat (qui fait partie des boucles en cours y compris et surtout pour le départ) 
		yield res
 
		# Traitement des boucles en partant de la fin vers le début
		for i in range(len(boucles) - 1, -1, -1):
			# On mémorise la taille de la boucle en cours (les boucles ont certains éléments facultatifs donc toutes les boucles n'ont pas la même taille)
			l=len(boucles[i])
 
			# On incrémente le résultat en cours de l'incrément de la boucle en cours (ou de 1 si pas d'incrément)
			res[i]+=boucles[i][2] if l > 2 else 1
 
			# Si le résultat est cohérent avec la borne max de la boucle on a fini l'incrément (on ne traite alors pas les autres boucles) 
			if res[i] < boucles[i][1 if l > 1 else 0]: break
 
			#  Le résultat ayant dépassé la valeur max, il est réinitialisé à la valeur de départ de la boucle (0 par défaut) et on passe à la boucle suivante (ou plutôt la précédente) 
			res[i]=boucles[i][0] if l > 1 else 0
 
		# Si on n'a jamais breaké...
		else:
			# C'est qu'on a traité toutes les boucles alors sortie du while
			break
		# for
	# while
# genere_boucle()
 
for b in genere_boucle((1, 3), (1, 6, 2), (4,)): print(b)

Déjà on gère la notion d'éléments facultatifs (comme borne min ou incrément) et surtout on évite le compteurs[-1] -= boucles[-1][2] initial pas forcément nécessaire...

[wiztricks]

Salut,

J'ai tendance à croire que ce conseil qu'on m'a donné, c'est un très bon conseil. Et en tout cas, pour l'efficacité ou pour le fun, c'est ce que je vais essayer de respecter sur ce mini chantier.

Un tableau se réalise de tas de façons et tout dépend de comment est faite la fonction "associe_tableaux".

Sûr que faire des calculs de matrices avec des listes de listes de base sera plus lent que de le faire faire par numpy (dont pas mal de code ont été optimisés en C).

J'aime bien le principe de ce calcul, mais ça date de 13 ans: peut-être pourrait-on faire mieux maintenant?

Avec product, écrit sur un coin de table:

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
>>> from itertools import product
>>> boucles = [[1, 5, 2], [0, 3, 1], [1, 4, 1]]
>>> for z in product(*[range(*v) for v in boucles]):
...     print(z)
...
(1, 0, 1)
(1, 0, 2)
(1, 0, 3)
(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(3, 0, 1)
(3, 0, 2)
(3, 0, 3)
(3, 1, 1)
(3, 1, 2)
(3, 1, 3)
(3, 2, 1)
(3, 2, 2)
(3, 2, 3)
>>>

et non testé pour voir si c'est plus rapide mais en tous cas, c'est plus court...

- W

[tyrtamos]

Bonjour wiztricks

Effectivement, avec product d'itertools, c'est plus court!

Merci!

[Sve@r]

On m'a expliqué un jour que dans Python, il faut éviter les boucles, et il faut 'factoriser' le code en manipulant des tableaux.

En gros :

Code :

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

tableau3 = associe_tableaux(tableau1, tableau2, condition_filtre)

Plutôt que :

Code :

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

1
2
3
Pour tout élément1 de tableau1 
  Pour tout élemént2 de tableau2
    Si condition_filtre (element1, element2) alors insère dans tableau3.

Tout à fait. En fait la raison principale c'est que l'opération "insere dans tableau" est assez gourmande (l'insertion force le décalage de ce qui suit et ça...). Ok il y a l'opération "append()" qui insère à la fin et donc qui est moins gourmande mais tout de même...

Donc ce qui en alrgorithme classique s'écrirait...

Code python :

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

1
2
3
4
res=[]
for x in orig:
	if test(x) == v:
		res.append(fct(x))

s'écrira dans ce que tu nommes "factorisation" et qui se nomme en réalité les "listes en compréhension" res=[fct(x) for x in orig if test(x) == v]. Dans cette écriture on crée la liste final d'un seul bloc "à la volée".

Appliqué à ton exemple, cela serait tableau_3=[... (ce qu_il faut mettre dans tableau_3)... for element_1 in tableau1 for element_2 in tableau_2 if condition_filtre(element1, element2)].

Si tu veux je me suis amusé à écrire un petit benchmark pour comparer le append() via la liste en comprehension

Code python :

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
#!/usr/bin/env python3
# coding: utf-8
 
import random
import timeit
from functools import partial
 
# La fonction qui testera chaque élément de la liste
def test(x): return x > 100
 
# La fonction qui crée la liste par append()
def fct_append(l):
	res=list()
	for x in l:
		if test(x): res.append(x)
# fct_append()
 
# La fonction qui passe par les listes en compréhension
def fct_comprehension(l): return list(x for x in l if test(x))
 
# Les fonctions à tester (on évitera la lambda pour être le plus impartial possible)
fct={
	"append" : fct_append,
	"comprehension" : fct_comprehension,
}
 
# Initialisation random
random.seed()
 
# La liste témoin
temoin=list(range(10_000_000))
 
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("start", len(temoin))
for (k, v) in random.sample(fct.items(), len(fct)):
	t=timeit.Timer(partial(v, temoin)).repeat(repeat=10, number=20)
	print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for

Et un résultat que j'ai eu (attention il faut attendre 6mn)

Code :

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

1
2
3
start 10000000
append: min=16.679654, max=17.124029, avg=16.880704
comprehension: min=15.728750, max=15.972923, avg=15.836860

[tbc92]

J'imagine que ce sont des milli-secondes, mais peu importe en fait.
L'écart entre 15.8 et 16.9 n'est pas non plus révolutionnaire , environ 6%

Par curiosité (je pourrais faire les tests moi-même, mais ce week-end seulement), si la fonction test() est très compliquée, l'écart va augmenter (plus de 6%) ou diminuer ?

Dans ce que je comprends, la méthode par compréhension fait que tous les NEXT i implicites, dans les boucles, sont compilés, et non plus interprétés. Et c'est là le principal bénéfice sur ce mini-exemple.

Et dans la commande : return list(x for x in l if test(x))
A chaque fois qu'on passe sur cette instruction, la fonction list() a besoin d'avoir un truc compilé, donc list commence par compiler la fonction test(), puis peut exécuter la fonction test-compilée() plein de fois pour tous les éléments x, au lieu d'exécuter une fonction test-non-compilée plein de fois dans la méthode classique avec des boucles

Du coup, si mon interprétation est bonne, le bénéfice sera en principe plus important (en pourcentage du temps total de traitement) si la fonction test() est assez compliquée.

Et de toutes façons, c'est le nerf de la guerre, la fonction test() doit être aussi bien écrite que possible.

[lg_53]

On m'a expliqué un jour que dans Python, il faut éviter les boucles, et il faut 'factoriser' le code en manipulant des tableaux.

Les tableaux en tant que tel n'existent pas en python. Soit on parle de liste de liste, et dans ce cas là, et bien vous n'avez pas le choix, il faut itérer sur les indices, soit vous utilisez numpy, et dans ce cas là si A et B sont deux tableaux de même taille, alors numpy vous permet d'écrire A+B sans avoir à parcours tous les indices de chaque tableau. Et là je prend A+B en exemple, mais il y a beaucoup d'autres opérations que numpy vous permet de faire sur les tableaux entiers (que numpy appelle des arrays).

Ensuite vous présentez un problème, avec 2 aspects qui sont différents. D'un côté vous voulez une écriture plus compacte pour une quinzaine de boucle imbriquée. De l'autre vous voulez un qqch qui ne soit pas trop lent à exécuter. Ce sont 2 choses différentes, et les codes les plus courts ne sont pas forcément les plus rapides.

Si j'en reviens à votre besoin initial, vous chercher le minimum d'une fonction. Et donc en fait les boucles imbriquées, ce n'est pas ca votre problème.
Pourquoi vous amusez vous à parcourir l'espace des paramètres pour trouver le minimum de la fonction, alors que vous avez des choses dans scipy qui sont déjà faites pour ca (googliser scipy optimize vous allez voir plein de chose). Et si vous rentrer un peu dans le détail de ce que font ces méthodes, vous allez voir que ce n'est pas de la recherche de minimum exhaustif, mais plutôt des choses basé sur des méthode de descente, avec le risque d'obtenir un minimum local et non global. Mais ca, ca peut se corriger, en faisant une petite phase d'initialisation soit en MonteCarlo, soit sur une grille de l'espace des paramètres assez grossière. Tout dépend après de comment votre fonction est fichue : est-elle bien régulière (mathématiquement parlant), sans discontinuité ni saut brusque de valeur ? Il vous faut quoi comme précision/incertitude sur ce minimum ?

[wiztricks]

Salut,

Mais je sais que ce n'est pas du tout 'Python' comme manière de procéder. Et que ça risque d'être atrocément long. Et quitte à faire comme ça, je ne vais pas utiliser Python.

Si j'écris:

Code :

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

1
2
3
4
for i1 = 1 to  n1 step p1
  for i2 = 1 to n2 step  p2
      for i3 = 1 to n3 step p3
          if ok00 (i1,i2,i3)  then

je trie les ok000(i, j, k) pour i, j, k variant de... et ce sera d'autant plus long qu'il y aura de triplets (i, j, k) a tester.

Mais dans ce cas, le soucis n'est pas du côté de Python mais de l'algo. (la première chose à optimiser).
Côté Python on pourra améliorer l'esthétique en réduisant le nombre de lignes avec par exemple itertools.product.

Code :

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

1
2
3
>>> list(product(range(3), range(1,4,2)))
[(0, 1), (0, 3), (1, 1), (1, 3), (2, 1), (2, 3)]
>>>

ce sera plus souple à coder mais peut être pas plus rapide.

Et là, premier challenge, comment supprimer certaines lignes de dd, par exemple supprimer les lignes telles que x^3+ y^3+ 5*z^3 serait un multiple de 7 ?

Vous devriez savoir le faire avec un code basique: une boucle qui filtre... pour autant qu'on sache résoudre de façon algorithmique ce genre d'équation (sinon, pas la peine de se lancer à coder...).

- W