[Python 3.X]Calcul sur toutes les combinaisons possible (optimisation)

Bonjour,

Voici le problème :
Soit un univers de 20 actions. Chaque action a une note ESG, ODD et Carbon qui vont de 1 à 10.
L'objectif est de retrouver un portefeuille de 3 actions qui a la meilleure moyenne des 3 notes: ((somme note ESG/3) + (somme note ODD / 3) + (Somme note Carbone / 3) / 3

Voici mon code qui fonctionne:

Code:

---

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

from itertools import combinations import pandas as pd   actions = { "action1": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action2": {"ESG": 7, "ODD": 9, "Carbon": 3}, "action3": {"ESG": 9, "ODD": 7, "Carbon": 4}, "action4": {"ESG": 10, "ODD": 4, "Carbon": 8}, "action5": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action6": {"ESG": 4, "ODD": 6, "Carbon": 7}, "action7": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action8": {"ESG": 1, "ODD": 8, "Carbon": 5}, "action9": {"ESG": 5, "ODD": 3, "Carbon": 9}, "action10": {"ESG": 2, "ODD": 1, "Carbon": 2}, "action11": {"ESG": 10, "ODD": 8, "Carbon": 5}, "action12": {"ESG": 7, "ODD": 4, "Carbon": 3}, "action13": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action14": {"ESG": 4, "ODD": 9, "Carbon": 2}, "action15": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action16": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action17": {"ESG": 9, "ODD": 1, "Carbon": 8}, "action18": {"ESG": 5, "ODD": 7, "Carbon": 4}, "action19": {"ESG": 2, "ODD": 3, "Carbon": 7}, "action20": {"ESG": 1, "ODD": 6, "Carbon": 9} }   x = 3 df = pd.DataFrame(columns=['actions', 'ESG', 'ODD', 'Carbon', 'Moyenne'])   for combi in combinations(actions.keys(), x): ESG = 0 ODD = 0 Carbon = 0 for action in combi: ESG += actions[action]['ESG'] ODD += actions[action]['ODD'] Carbon += actions[action]['Carbon'] df = df.append({'actions': combi, 'ESG': ESG/3, 'ODD': ODD/3, 'Carbon': Carbon/3, 'Moyenne': ((ESG/3)+(ODD/3)+(Carbon/3))/3}, ignore_index=True)   print(df)

---

Mon soucis c'est qu'au tout début j'ai mentionné un univers de 20 actions et un portefeuille de 3 actions, soit 1139 combinaisons possible.
Dans la réalité, il y a 1500 actions et le portefeuille peut en contenir jusqu'à 500. Le nombre de combinaison possible est colossal et le calcul est interminable.

Quelqu'un saurait comment rechercher le meilleur portefeuille en prenant en compte les contraintes?
Merci.

Salut,

Citation:

---

Envoyé par Fani0304

Quelqu'un saurait comment rechercher le meilleur portefeuille en prenant en compte les contraintes?

---

Il y a une rubrique et un forum rien que pour les algorithmes... c'est là bas que se cachent ceux qui savent.

- W

bonjour

Pour parler uniquement python, ajouter une ligne dans pandas est très long donc ajouter uniquement si la moyenne est plus haute te feras dans un premier temps en gagner pas mal

Code:

---

1 2 3 4 5 6 7

best = 0 for combi in combinations(actions.keys(), x): ... moyenne = ((ESG/3)+(ODD/3)+(Carbon/3))/3 if moyenne > best: best = moyenne df = df.append({'actions': combi, 'ESG': ESG/3, 'ODD': ODD/3, 'Carbon': Carbon/3, 'Moyenne': moyenne}, ignore_index=True)

---

ps: et pas compris pourquoi utiliser pandas si tu ne désires que la meilleure moyenne
if moyenne > best['moyenne']:
best = {'actions': combi, 'ESG': ESG/3, 'ODD': ODD/3, 'Carbon': Carbon/3, 'Moyenne': moyenne}


-----------
Tous cela est sans importance avec des valeurs type 1500 et 500


####################################
Sinon algo, je trouve le même résultat avec:

Code:

---

1 2 3 4 5 6

filtre = [] for action in actions: moyenne = sum(a for a in actions[action].values()) / len(actions[action]) filtre.append([action, moyenne]) filtre.sort(key = lambda i: i[1], reverse =True) print(filtre[0:3])

---

résultat

Code:

---

1 2 3 4 5 6

[['action11', 7.666666666666667], ['action4', 7.333333333333333], ['action3', 6.666666666666667]] # pandas avec combinations() # df.sort_values('Moyenne', ascending=False) actions ESG ODD Carbon Moyenne 330 (action3, action4, action11) 9.666667 6.333333 5.666667 7.222222 41 (action1, action4, action11) 9.333333 5.666667 6.333333 7.111111

---

bonjour et merci à tous pour vos réponses.

Je n'ai peut être pas très bien posé ma question.
Mon besoin ne se situe pas au niveau du calcul, c'est qu'une moyenne!!!!
Mon problème se situe au niveau du nombre d'itération du calcul.

Dans le premier code que j'ai posté, c'est une combinaison de 3 sur un univers composé de 10 éléments, soit 1 139 combinaisons possibles. C'est gérable dans un dataframe, une liste ou une base de données.

Maintenant, dans le code ci-dessous, c'est une combinaison de 10 sur un univers composé de 40 éléments, soit 847 660 528 possibilités.

Code:

---

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

from itertools import combinations import pandas as pd   actions = { "action1": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action2": {"ESG": 7, "ODD": 9, "Carbon": 3}, "action3": {"ESG": 9, "ODD": 7, "Carbon": 4}, "action4": {"ESG": 10, "ODD": 4, "Carbon": 8}, "action5": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action6": {"ESG": 4, "ODD": 6, "Carbon": 7}, "action7": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action8": {"ESG": 1, "ODD": 8, "Carbon": 5}, "action9": {"ESG": 5, "ODD": 3, "Carbon": 9}, "action10": {"ESG": 2, "ODD": 1, "Carbon": 2}, "action11": {"ESG": 10, "ODD": 8, "Carbon": 5}, "action12": {"ESG": 7, "ODD": 4, "Carbon": 3}, "action13": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action14": {"ESG": 4, "ODD": 9, "Carbon": 2}, "action15": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action16": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action17": {"ESG": 9, "ODD": 1, "Carbon": 8}, "action18": {"ESG": 5, "ODD": 7, "Carbon": 4}, "action19": {"ESG": 2, "ODD": 3, "Carbon": 7}, "action20": {"ESG": 1, "ODD": 6, "Carbon": 9}, "action21": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action22": {"ESG": 7, "ODD": 9, "Carbon": 3}, "action23": {"ESG": 9, "ODD": 7, "Carbon": 4}, "action24": {"ESG": 10, "ODD": 4, "Carbon": 8}, "action25": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action26": {"ESG": 4, "ODD": 6, "Carbon": 7}, "action27": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action28": {"ESG": 1, "ODD": 8, "Carbon": 5}, "action29": {"ESG": 5, "ODD": 3, "Carbon": 9}, "action30": {"ESG": 2, "ODD": 1, "Carbon": 2}, "action31": {"ESG": 10, "ODD": 8, "Carbon": 5}, "action32": {"ESG": 7, "ODD": 4, "Carbon": 3}, "action33": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action34": {"ESG": 4, "ODD": 9, "Carbon": 2}, "action35": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action36": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action37": {"ESG": 9, "ODD": 1, "Carbon": 8}, "action38": {"ESG": 5, "ODD": 7, "Carbon": 4}, "action39": {"ESG": 2, "ODD": 3, "Carbon": 7}, "action40": {"ESG": 1, "ODD": 6, "Carbon": 9} }   x = 10 df = pd.DataFrame(columns=['actions', 'ESG', 'ODD', 'Carbon', 'Moyenne'])   for combi in combinations(actions.keys(), x): ESG = 0 ODD = 0 Carbon = 0 for action in combi: ESG += actions[action]['ESG'] ODD += actions[action]['ODD'] Carbon += actions[action]['Carbon']   print(str(action + ':' + ((ESG/3)+(ODD/3)+(Carbon/3))/3))   # df = df.append({'actions': combi, 'ESG': ESG/3, 'ODD': ODD/3, 'Carbon': Carbon/3, 'Moyenne': ((ESG/3)+(ODD/3)+(Carbon/3))/3}, ignore_index=True)

---

Voici ma question :

Parmi les 847 millions de possibilités, comment trouver la combinaison qui a la meilleure note (moyenne dans notre cas)?

Merci.

Citation:

---

Envoyé par Fani0304

...
L'objectif est de retrouver un portefeuille de 3 actions qui a la meilleure moyenne des 3 notes: ((somme note ESG/3) + (somme note ODD / 3) + (Somme note Carbone / 3) / 3 ...

---

Mathématiquement ça revient à chercher les plus grandes sommes non ? Ou alors j'ai rien compris .
((a1+a2+a3)/3+(b1+b2+b3)/3+(c1+c2+c3)/3)/3 == ((a1+b1+c1)+(a2+b2+c2)+(a3+b3+c3))/9 n'est-il pas ?

Code:

---

1 2 3

actions = { "action1": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action2": {"ESG": 7, "ODD": 9, "Carbon": 3}, "action3": {"ESG": 9, "ODD": 7, "Carbon": 4}, "action4": {"ESG": 10, "ODD": 4, "Carbon": 8}, "action5": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action6": {"ESG": 4, "ODD": 6, "Carbon": 7}, "action7": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action8": {"ESG": 1, "ODD": 8, "Carbon": 5}, "action9": {"ESG": 5, "ODD": 3, "Carbon": 9}, "action10": {"ESG": 2, "ODD": 1, "Carbon": 2}, "action11": {"ESG": 10, "ODD": 8, "Carbon": 5}, "action12": {"ESG": 7, "ODD": 4, "Carbon": 3}, "action13": {"ESG": 8, "ODD": 5, "Carbon": 6}, "action14": {"ESG": 4, "ODD": 9, "Carbon": 2}, "action15": {"ESG": 3, "ODD": 10, "Carbon": 1}, "action16": {"ESG": 6, "ODD": 2, "Carbon": 10}, "action17": {"ESG": 9, "ODD": 1, "Carbon": 8}, "action18": {"ESG": 5, "ODD": 7, "Carbon": 4}, "action19": {"ESG": 2, "ODD": 3, "Carbon": 7}, "action20": {"ESG": 1, "ODD": 6, "Carbon": 9} } A = sorted(actions,key = lambda x:sum(actions.get(x).values()),reverse=True) print(A[:3])

---

Désolé mais je ne comprends pas..

Avec le calcul de josmiley et mon code, on trouve bien la même chose que toi avec tes 40 actions ??? (résultat instantané)

Code:

---

1 2	[['action11', 7.666666666666667], ['action31', 7.666666666666667], ['action4', 7.333333333333333]] ['action11', 'action31', 'action4']

---

Ton dataframe (avec ma modif post #3) trié par moyenne (10 secondes de calcul):

Code:

---

1 2 3 4 5 6

actions ESG ODD Carbon Moyenne 2324 (action4, action11, action31) 10.000000 6.666667 6.000000 7.555556 6096 (action11, action24, action31) 10.000000 6.666667 6.000000 7.555556 2317 (action4, action11, action24) 10.000000 5.333333 7.000000 7.444444 2610 (action4, action24, action31) 10.000000 5.333333 7.000000 7.444444 1694 (action3, action11, action31) 9.666667 7.666667 4.666667 7.333333

---

Citation:

---

se situe au niveau du nombre d'itération du calcul.

---

ici c'est uniquement 40 moyennes (de 3) donc que du très léger , même avec tes 1500/500

Citation:

---

comment trouver la combinaison qui a la meilleure note (moyenne

---

Puisque tu recherches uniquement le N° 1, c'est justement simple, c'est la combinaison des meilleures moyennes ?
une petite boucle de 1500 actions pour calculer les moyennes, puis retour des 500 meilleures moyennes

----------
peut-être que l'on ne comprend pas, mais dans tes messages, tu n'indiques même pas quelle est la bonne réponse, cela n'aide pas.

Citation:

---

Envoyé par Fani0304

Mon besoin ne se situe pas au niveau du calcul, c'est qu'une moyenne!!!!
Mon problème se situe au niveau du nombre d'itération du calcul.
Parmi les 847 millions de possibilités, comment trouver la combinaison qui a la meilleure note (moyenne dans notre cas)?

---

Vous commencez par imposer un algorithme qui trouve assez vite pour un petit nombre d'actions mais qui devient trop lent lorsque le nombre d'actions est important. Si vous ne changez pas d'algorithme, il n'y a aucune chance pour que ça aille plus vite car la vitesse est liée à la complexité de l'algo.

- W

Citation:

---

Envoyé par wiztricks

Salut,



Il y a une rubrique et un forum rien que pour les algorithmes... c'est là bas que se cachent ceux qui savent.

- W

---

Wiztricks a raison, on est plus sur un problème d'algorithme, qu'un problème de python. On est sur un type d'algorithme de minimisation sous contrainte.

Car en effet en terme de combinatoire, on a 1500! / (1000! x 500!) Est justement sur ce calcul qui indique le nombre de combinaison possible voici la réponse de python :

Citation:

---

np.math.factorial(1500)/( (np.math.factorial(1000))*(np.math.factorial(500)) )
Traceback (most recent call last):

line 1, in <module>
np.math.factorial(1500)/( (np.math.factorial(1000))*(np.math.factorial(500)) )

OverflowError: integer division result too large for a float

---

Donc même avec le bon algorithme, je crains que la machine qui soit capable d'un tel calcul (dans une échelle de temps utile) en se limitant à sommer ne soit pas forcément à notre portée :D

Citation:

---

Envoyé par AF_2.8

Donc même avec le bon algorithme, je crains que la machine qui soit capable d'un tel calcul (dans une échelle de temps utile) en se limitant à sommer ne soit pas forcément à notre portée :D

---

Un "bon" algo. sera celui qui trouvera la solution sans s'embourber dans l'explosion combinatoire de tous les calculs.
Et des algo. d'optimisations, il y en a plein... reste à savoir celui qui sera le plus pertinent à appliquer ici (mais le forum algo. est là pour çà)

- W

Dites moi si je suis à côté de la plaque, mais pourquoi ne pas paralléliser ?
Tu créé 500 df de 3 enregistrements que tu traites dans 500 threads différents. Ainsi en combinant le meilleur résultat de chaque threads tu te retrouves avec un portefeuille des 500 meilleures actions ?
Il est certain qu'un meilleur algo permettrait de s'en sortir plus rapidement, mais cette solution devrais déjà permettre une réduction significative du temps de traitement.

Citation:

---

Envoyé par BioKore

Il est certain qu'un meilleur algo permettrait de s'en sortir plus rapidement, mais cette solution devrais déjà permettre une réduction significative du temps de traitement.

---

Ben, ici on met plus de ressources au boulot... Mais 500 threads sont parallélisables avec 500 CPU, si on a que 10 CPU, faire tourner 10 threads sera suffisant si on sait distribuer le boulot. La réalité est qu'avec Python et son GIL (Global Interpreter Lock) 10 threads seront sérialisées et ne consommeront qu'un seul CPU.

- W

Citation:

---

Envoyé par wiztricks

Ben, ici on met plus de ressources au boulot... Mais 500 threads sont parallélisables avec 500 CPU, si on a que 10 CPU, faire tourner 10 threads sera suffisant si on sait distribuer le boulot. La réalité est qu'avec Python et son GIL (Global Interpreter Lock) 10 threads seront sérialisées et ne consommeront qu'un seul CPU.

---

Oui, bien entendu, utiliser moins de threads, ou en tout cas suivant une distribution plus réfléchie fait bien plus de sens que la méthode que je propose.
N'utilisant que très rarement, de manière explicite, le multithreading, je laisse donc cette optimisation à la discrétion des plus expérimentés que moi en la matière. En général, lorsque j'utilise cette méthode, je fais des découpages en multiple de 16 (nombre de cœurs de mon CPU) et je laisse le gestionnaire de processus gérer le reste.
Le sens de mon post était ici plus de proposer un éventuel axe d'optimisation du temps de calcul.

Par contre, tu soulèves un point intéressant sur le GIL, si je comprends bien, en dessous d'un certain nombre de threads demandés, Python sérialise les processus ?
J'imagine que ceci est en rapport avec l'overhead nécessaire pour gérer les threads c'est bien ça ?

Citation:

---

Envoyé par BioKore

Par contre, tu soulèves un point intéressant sur le GIL, si je comprends bien, en dessous d'un certain nombre de threads demandés, Python sérialise les processus ?
J'imagine que ceci est en rapport avec l'overhead nécessaire pour gérer les threads c'est bien ça ?

---

En dessous? Non dès qu'on a plus d'un thread...
Le GIL sert juste à verrouiller l'accès aux structures de données pour le sérialiser (et éviter corruptions et états inconsistants).

Citation:

---

Envoyé par BioKore

Le sens de mon post était ici plus de proposer un éventuel axe d'optimisation du temps de calcul.

---

La durée dépend de la capacité CPU, ajouter plus de CPU pour faire le boulot semble raisonnable (sur le papier) mais avec Python on ne peut pas le faire avec des threads qui ne permettent que le support d'opérations d'entrées sorties asynchrones. Et même dans ce cas, le coût (overhead) n'est pas nul et on lui préférera asyncio.

- W

Bonjour,

Citation:

---

Le sens de mon post était ici plus de proposer un éventuel axe d'optimisation du temps de calcul.

---

Avant de faire cela, il faut optimiser son algorithme, puis si besoin de performance supplémentaire, vérifier qu'on utilise toutes les fonctions CPython plutôt que du pur Python (ce que fait @josmiley dans sa solution).

Si avec cela, on a toujours pas ce qu'on veut niveau performance, on peut regarder du côté des modules numpy, pandas, multiprocessing, ... mais en général, ces besoins sont assez rares.