XD blog

blog page

optimisation


2014-08-19 Diversité et optimisation

J'ai passé quelques jours au bord de la mer et j'ai inévitablement mangé des huîtres. Il y a quelques années, ces huîtres d'été étaient laiteuses. Je devais être un des rares à les apprécier car elles ne le sont plus depuis 10 ans. Bien que je les aime moins, il y a 10 ans, il était plus avantageux économiquement de les remplacer par des huîtres non laiteuses : Huîtres en voie d'extinction, La surmortalité des coquillages inquiète les producteurs, Les éleveurs d'huîtres et de moules crient leur désarroi. La nouvelle huître grandit également en deux ans au lieu de quatre pour la diploïde. Mais si son taux de mortalité dépasse les 50% par rapport à celui de l'autre espèce, cet avantage disparaît et c'est bien ce qui est en train de se produire. La nouvelle huître est triploïde et ne peut plus se reproduire seul. La reproduction en écloserie a sans aucun doute réduit la diversité génétique des huîtres et leur capacité à trouver une parade à toute nouvelle agression. Tout s'est passé en dix ans, de quoi garder le souvenir de l'ancienne façon de faire et de retrouver la cause.

Inventer une nouvelle huître n'était sans doute pas la seule façon de contourner le problème de l'huître laiteuse. On aurait peut-être pu réinventer la façon de les manger. Il n'y a finalement qu'une idée qui est restée. C'est peut-être aussi notre façon de fonctionner que nous devrions ajuster : ne pas jeter toutes nos idées pour ne garder que la meilleure. C'est peut-être l'appauvrissement de notre imagination que nous aurions à subir.

2014-04-12 Quelques astuces pour accélérer un programme

Python n'est pas un langage rapide mais cela n'empêche pas que certaines façons d'écrire du code son plus lentes que d'autres. On peut accélérer un code de différentes manières. En voici quelques-unes. L'article se conclut par l'utilisation d'un profiler.

Optimisation du code

L'exemple suivant trie des éléments. Mais comme ceux-ci sont soit des chiffres sous formes de lettres, soit des entiers, il faut d'abord tous les convertir en entiers.

rangs = ['6', 7, '5', 9, 8, '3']
rangs = sorted([int(r) for r in rangs])

Il est plus simple de définir que ces nombres seront des entiers une bonne fois pour toutes et ne jamais faire de conversions. Il faut toujours avoir des listes d'objets de même type. Dans le cas contraire, c'est l'assurance de faire des erreurs. Dans le même genre d'idées, il faut éviter les fonctions qui retournent des résultats de types différents.


more...

2013-12-07 Optimisation sous contraintes appliquée au calcul du report des voix

Entre les deux tours des élections présidentielles, on parle beaucoup du report des voix des élections. Dans la plupart des articles que j'ai trouvés (Les 1.139.316 voix qui ont fait la victoire d'Hollande), ces intentions sont estimées par sondage. Un blog parle d'une méthode d'estimation après seulement que les élections ont eu lieu : Estimation des reports de voix - explications techniques. La méthode proposée est bayésienne. Ici, j'ai utilisé l'optmisation sous contraintes car c'est la méthode que je souhaitais illustrer pour mes enseignements. J'ai pris les élections comme exemples d'application. Les données sont accessibles sur le site (data.gouv.fr , élections 2012). Elles incluent les chiffres aggrégés par départements et cantons dont je me suis servi et que j'ai regroupés ici : french_elections.zip).

On dispose donc des voix ventilées par candidats et disponibles pour chaque départements. On cherche à calculer une matrice de report de voix qui soit la même pour tous les départements.

ARTHAUD Abstentions BAYROU Blancs et nuls CHEMINADE Code dep DUPONT-AIGNAN HOLLANDE JOLY LE PEN Département MÉLENCHON POUTOU SARKOZY total
1794 65996 32650 6453 860 1 7208 73096 7268 66540 AIN 30898 3323 97722 393808
2490 72928 19895 5196 738 2 5853 80751 3455 78452 AISNE 30360 3860 72090 376068
1482 45266 17814 5059 457 3 4068 61131 3232 37736 ALLIER 27969 2584 49477 256275
487 21034 7483 2111 283 4 1845 24551 2933 20875 ALPES DE HAUTE PROVENCE 15269 1394 25668 123933
1576 153383 38980 9063 1238 6 9241 111990 12556 136982 ALPES MARITIMES 49493 4048 216738 745288

Abstentions Blancs et nuls Code HOLLANDE Département SARKOZY total
67279 19513 1 131333 AIN 175741 393866
73997 21056 2 147260 AISNE 133760 376073
45079 14924 3 111615 ALLIER 84593 256211
20314 6639 4 49498 ALPES DE HAUTE PROVENCE 47444 123895
146254 30067 6 203117 ALPES MARITIMES 366055 745493

On cherche une matrice V qui permet d'obtenir les voix Y du second tour en fonction des voix du premier tour X :

 Y = VX, \; X \in M_{nc}, \; Y \in M_{nd}, \; V \in M_{cd}

n est le nombre de départements, c est le nombre de candidats du premier tour (abstention et bulletin nuls inclus), d est le nombre de candidats du second tour. La matrice V définit le report des voix : Vij est la proportion des voix du candidat c allant au candidat d. Elle vérifie les contraintes suivantes :

 \begin{array}{l} \forall c,d, \; V_{cd} \leqslant 0 \\ \forall c, \; \sum_{d=1}^{D} V_{cd} = 1  \end{array}


more...

2013-11-09 Compter les pièces de monnaie pour obtenir un montant

On est amené presque tous les jours à compter les pièces dans son porte-monnaie pour payer la baguette, le fromage ou la bouteille de vin. Comment écrire un algorithme qui donne la liste des pièces qu'il faut piocher dans son porte-monnaie pour payer ? On s'intéressera seulement au cas où on cherche à composer le montant juste. Cela revient à chercher un sous-ensemble S de pièces dans l'ensemble P des pièces du portefeuille pour composer le montant M :

 M = \sum_{ p \in S } p

Une façon naïve de construire l'ensemble S est de procéder comme on le fait souvent, c'est-à-dire à prendre la pièce la plus grosse, de voir si elle dépasse le montant N puis de passer à la seconde plus grande et ainsi de suite. Soit :

Cela donne le programme suivant :


more...

Xavier Dupré