10 algorithmes marquants

12 février 2018

Inspirée d’un papier intitulé The Best of the 20th Century: Editors Name Top 10 Algorithms, une série de 2 articles (part 1 et part 2) revisitant ces classiques de l’informatique!


VMProfiler et le profilage de code

3 octobre 2017

J’avoue honteusement que cette annonce est passée sous mon radar. Tout autant que les articles subséquents. Un nouveau profiler développé par Sophie Kaleba (son blogue est ici) est maintenant disponible pour Pharo.

En préambule, elle vous explique comment obtenir le projet et l’installer dans votre image ainsi qu’elle vous fait un rapide survol de ce que l’outil peut faire et toutes les statistiques qu’il est en mesure de vous offrir.

Le premier article vous introduit au fonctionnement et aux fonctionnalité de base de l’outil.

Le deuxième article détaille les différentes informations relatives au temps d’exécution du code Pharo.

Finalement, le dernier article porte sur les autres données fournies par le profiler tels que la mémoire consommée/disponible, le garbage collection, les événements de la VM, etc.

Bref, VMProfiler est un outil vital quand vient le temps d’optimiser la performance de votre application!

Le blogue de Steven Pigeon

2 octobre 2017

Ce blogue est un heureux mélange de mathématiques, d’informatique, d’optimizations, de programmation et d’algorithmes!  Un autre des blogues que j’adore : Harder, Better, Faster, Stronger.

Des requêtes à problèmes?

17 septembre 2017

Quand MySQL se me à déraper, c’est habituellement l’oeuvre de quelques requêtes SQL problématiques.  Un petit rappel pour vous aider à trouver la/les coupables!

Du nouveau dans le problème du voyageur de commerce!

17 septembre 2017

Le problème du voyageur de commerce est un des problèmes d’optimisation les plus étudiés autant en mathématiques qu’en informatique.  Bon nombre de chercheurs ont travaillé sur ce problème complexe, en grande partie à cause de son énorme utilité dans le monde réel.

Une avancée récente (décrite ici) risque de relancer l’intérêt pour cet problème d’optimisation.

Pour les plus curieux, un site web incontournable traitant de ce problème.

Genetic Algorithms Introduction

7 août 2016

Interested in genetic algorithms?  Here’s a quick-and-short list of some of the best free material out there to get you started.

If you ever get serious about genetic algorithms, I recommend you buy Goldberg’s book Genetic Algorithms in Search, Optimization , and Machine Learning.



Quick Guide On How To Ask A MySQL-related Question Properly

1 août 2016

Note: this article was originally posted in French here.

You!  Yes!  Yep, you! I’m talking to you my friend!  You, the one that I help out in forums, on IRC, on mailing lists!

Each and every day, I answer questions related to MySQL, mostly about SQL queries or optimization problems. Whether it’s on dBForums, Stack Overflow, MySQL.com, developpez.net or on IRC (irc.freenode.net, channel #mysql), it’s always the same thing! If you want me to help you, make it easy for me!

So, here’s a quick guide explaining what you have to do if you want us/me to help you solve your problem as quickly as possible.

Explain what your problem is as simply and clearly as possible

If you’re unable to explain, in one sentence, what you are trying to do, we’re off to a very bad start.  You have to know what you’re talking about first!  You have to know what you’re trying to do in the first place!

A good example: « I’m trying to find the best salesman in every store located in a district that sells less than the national district average« . This is clear and simple to understand!

A bad example: « My SQL query is slow, there it is » :

 COUNT(*) AS x1k1, w.nndt, w.n01_d
 p_usr_htgg w
    puw_user w2
    temp_eoms te ON te.mt = w2.mt
    w2.k1 = w.k1 AND w.sales = MAX(w2.sales)
 w.nndt, w.n01_d
 COUNT(*) > 3
 x1k1 DESC
 0, 100 

Can you see the difference between these two examples? In one case, the problem is clear.  In the second case, just seeing the SQL without any further explanation makes me want to puke! How can I help with all that SQL garbage?

Start small!  If you have no clue about how to use JOINs, don’t focus on the the ROLLUP or aggregate stuff!!!  Learn the basics while you’re at it! Learn the lingo as well.  If you don’t know what something means, ask it! Don’t pretend you know when you don’t!

One more thing : pick names that are meaningful for tables and columns! Acronyms and cryptic abbreviations tell me nothing! Same thing for table and column names in Italian, Greek, Spanish or German!  Use English !

Be precise

« I have a huge database with an enormous amount of concurrent users and my query is very slow and it is executed many many times« .

What is huge for you is probably a joke for Google, Amazon and GitHub or for someone working in bioinformatics: give me numbers (number of records, tablespace size, etc.), not your impressions!

« Enormous » is often relative! Fifty concurrent users and a table of 100 million rows on a server with 2G of RAM is an enormous amount of users! But on a server with 16 processors and 128G of RAM, 50 concurrent users is not a problem at all : once again, give me numbers, not adjectives!

« Many many times » doesn’t mean anything to me! What does that mean exactly? 200 times/minute? 15 times per minute? What? Give me precise numbers! What do you mean by slow? 3 seconds or 0.2 seconds? Be precise!

Don’t make me google for you

Please, make some minimal effort! Often times, I can give you an URL explaining your problem faster than the time it took you to write your question!  You would have saved everyone’s precious time if you would have googled in the first place!

Give me some test data and expected results

« It doesn’t work!  I should have six xyz records for every abcd record but I only get five ».

This tells me nothing useful!  I don’t know your database, your tables, your domain, the content of the columns, etc.  Even worse, I don’t know what’s in those tables, how the data is spread out, the selectivity of some columns, etc. Creating a test example with some data only takes two minutes on SQLFiddle!

Show me the EXPLAIN

Your query is slow? So what! Why? I have no way to know unless you give me the EXPLAIN of your query, I cannot help you at all nor even know why MySQL picks a particular access plan over a more promising one!


Even if you provided me with the EXPLAIN of your SQL query, I still need to know what the table looks like.  One is useless without the other! I also need the SHOW CREATE TABLE, it’s as simple as that!

Are both keys referenced in your JOIN of the same type and length? Is the LIKE in your query way too slow because we have to scan 4Mb of text in every record? Are we trying to match records by looking into a 1G BLOB column?  Is it an InnoDB, a MyISAM or another table type?  What are the character set and collation?


In some cases, your query is fine and the problems you encounter are caused by session/server/client parameters!  You have to know how to use SHOW VARIABLES!

Learn to use SHOW STATUS

Sometimes, you have to be able to check the status of your server. This is essential! In that case, SHOW STATUS is another command you must know!


The SHOW TABLE STATUS will allow you, in a glance, to have a precise picture of what’s in your database.  You’ll be able to see, in one shot, table names, their type, their size, collation info, etc. Very useful command : for you and for me!

Give me some volumetrics

I just said it earlier and I’ll say it again : I need numbers, measures, to help you! Give me numbers, not fuzzy impressions!

Most of your queries execute in 0.1 second but your server cannot keep up? Why? Perhaps, it would have been useful to know that you have 3500 concurrent connections at any moment hitting this poor server!  Or that one particular query is executed 900 times per minute!

Your query takes 27 seconds to complete? Perhaps you should have told me that your table has 728 million records!

You wonder why the EXPLAIN of your query shows a full table scan even though you’ve indexed just about everything on that table? Had I known your table only has 8 records, I would have told you that in that case a full table scan is perfectly normal!

If you want me to help you, I need a minimum of context !  Only numbers can tell me the real story!  Not « enormous » nor « many » or « slow » !

Take a deep breath : do not panic!

Premature optimization is the root of all evil.

« I have this HYPER-HUGE-BIGGEST-OH-MY-GOD database and my query, with 2 INNER JOIN, is executed every 15 seconds and we add 2500 records to the main table every month… »

Take it easy!  Relax!  MySQL is not Excel : it can handle lots of data! For my own amusement, my server at home has 10000+ tables! Performance is mostly a matter of hardware and every database is different!

Unless you’re trying to compete with Google or you have a very complex query that causes real problems, don’t try to optimize every SQL query and make it execute in less that 100 milliseconds! In some cases, it’s just not possible possible.  Focus on the real problems!

Don’t make me sweat over a query for 4 hours and end up telling me that this SQL runs once a year on January 1st at 2h15 AM and it takes 5 minutes to complete when only 2 users are connected!  Pick your battles! I don’t mind helping you out but I don’t like to waste my time!

Don’t try to optimize everything!  Work on what counts!

Use SQLFiddle

It’s easy to use and it works great when debugging SQL queries!  And it’s free!  And it’s here!  And it allows us to work on exactly the same thing!

Use a pastebin

Please, don’t flood the IRC channel with a query of 35 lines!  It’s annoying for everyone and it’s rude! Use a pastebin (or even better, SQLFiddle). There’s Pastie, gist.github et pastebin.com.

Use the MySQL client

Some problems are extremely hard to reproduce and difficult to understand. The last thing we need is some PHP code on top of your query!  Another thing: please, don’t use crap like PHPMyAdmin or any other clumsy tool when trying to debug or fix things! All you need is the MySQL client !  It works just fine on every platform supported by MySQL, it’s rock solid and, honestly, it’s all you need! If you’re on Windows, you can always use HeidiSQL.

Use \G

Instead of forcing me to scroll to the right for eons just to see the complete result of your query, an EXPLAIN or a SHOW TABLE STATUS, add \G at the end of your SQL statement to force the client to display results vertically and limit them to 80 chars per line if necessary!

Format your code

SELECT count(*) as
x1k1, w.nndt, 
from P_USR_HTGG 
w where exists (
SELECT w2.id FROM puw_user w2
left join 
temp_eoms te ON te.mt = w2.mt where 
w2.k1 = w.k1 AND w.sales = 
group by w.nndt,
having count(*) > 3
order BY x1k1 
desc limit 0, 100

Can you quickly see what going on in that query? Not me! And it’s the exact same query that was at the beginning of this post!  Which one is easier to read?

Write the reserved words and functions in uppercase! SELECT, FROM, WHERE, INNER JOIN, SUBSTRING, HAVING, GROUP BY, ORDER BY, IN, EXISTS, COUNT, etc. Indent your code and regroup « logical » parts (for instance, sub-selects) of the work done by your query. If I have to read your query with a magnifier to identify what I’m looking for, it doesn’t help!

Don’t be overexcited

We’ve been working on your query for 30 minutes and now you’re satisfied with the speed and results?  Comes out you only needed an extra index?

Don’t precipitate yourself to add the index in production! What sometimes takes 3 seconds on test data can take hours on a production database! Besides, when applying changes to a production database, you should always make sure you have a recent backup first!

This advice can sound somewhat useless and stupid but not so long ago, a poor guy I was helping had the very bright idea to add the missing index to his production database right away… only to realize that his production table had 94 million records!  The index creation took a few hours… during the peak hours!

Be open to criticism

Lots of times, a poor design or a bad choice of data types is the problem, not the circumvoluted query you’re trying to optimize.  Your query is unnecessary complex because of this! Be open to suggestions : we’re just trying to help you!

Like here.

Say thanks

I’m helping people with their MySQL/SQL problems because I like it and the diverse nature of problems out there helps me stay mentally sharp and up-to-date with MySQL.  If I spend 2 hours of my time helping you, a « thank you » is not much to ask in return!


























Les casse-tête

24 janvier 2016

Ceux qui me connaissent bien le savent, j’adore me casser la tête sur une foule de « petits » problèmes (mathématiques, algorithmiques ou autres) : ça permet de garder le cerveau en forme et ça me donne une occasion de faire du Smalltalk et de me garder à jour dans mes skills autant de programmation que d’analyse.

Si vous êtes comme moi, voici une liste de ces petits casse-tête qui m’amusent en ce moment (ou depuis un bout) et qui pourrait vous servir de suggestions…

Les nombres de Lychrel

Avant tout, un peu de vocabulaire!

Un palindrome est une mot, une phrase ou un nombre qui s’écrit de la même façon à l’endroit et à l’envers.  Par exemple, Laval, Bob ou 17371.  Ça peut également être une phrase ou un bout de texte comme « Mon nom » ou le célèbre « A man, a plan, a canal: Panama ».

Grosso modo, un nombre de Lychrel est un nombre qui ne peut pas former de nombre palindrome lorsqu’on l’additionne à répétition avec son « inverse ».

Par exemple, 59 n’est pas un nombre de Lychrel puis qu’on aboutit à un palindrome au bout des itérations suivantes:

59 + 95 = 154
154 + 451 = 605
605 + 506 = 1111

L’histoire devient passionnante quand des mathématiciens se sont intéressés au plus petit nombre pour lequel on n’a pas encore trouvé de nombre palindrome après une quantité anormalement élevée d’itérations.  Il s’agit de 196.

Le problème est fascinant en soi de par la simplicité des opérations impliquées (des additions et la détection de palindrome) et les raccourcis et astuces nécessaires (autant mathématiques qu’algorithmiques) pour tenter de le résoudre.

Parmi les incontournables sur le sujet, il y a les sites de Jason Doucet et celui de Wade VanLandingham.

Le site What If?

Un site de questions absurdes avec des explications sérieuses et scientifiques.  Un challenge pour le cerveau quand on essaie de formuler une réponse aux problèmes présentés! Ce qui est intéressant, c’est le raisonnement et les arguments des réponses à des problèmes aussi hypothétiques que, bien souvent, idiots!  Comme celui-ci par exemple.

La persistence multiplicative

On définit grossièrement la persistence multiplicative par le nombre de fois qu’on peut multiplier les chiffres d’un nombre entre eux jusqu’à ce que le résultat ne comporte qu’un seul chiffre.

Par exemple:

679 ->  6 * 7 * 9 = 378
378 ->  3 * 7 * 8 = 168
168 ->  1 * 6 * 8 = 48
48 ->  4 * 8 = 32
32 ->  3 * 2 = 6

On dira donc que le nombre 679 a une persistence multiplicative de 5.

À ce jour, nous ne connaissons aucun nombre en deça de 10^233 (10 à la puissance 233) ayant une persistence multiplicative supérieure à 11. C’est précisément cette limite qui intéresse les mathématiciens!

Évidemment, ce qu’il est intéressant de chercher ce sont les nombres dits candidats.  Tout nombre comportant un 0 est éliminé d’office (ça occasionne forcément un résultat de zéro). Comme la multiplication par 1 n’apporte rien de plus, on ne considérera que les nombres sans le chiffre 1.  De plus, on éliminera les nombres comportant à la fois le chiffre 5 et un nombre pair comme cela produira un multiple de 10, donc un résultat de zéro.

Pour un bref aperçu de la persistence multiplicative, il y a une page de Wolfram sur le sujet. Pour un résumé des optimisations et trucs possibles, il y a ce papier.

La conjecture de Collatz

Un autre problème mathématique non résolu : la conjecture de Collatz (aussi appelée conjecture de Syracuse).

Si vous avez quelques cycles de CPU à partager, il existe un projet BOINC juste ici.

Autrement, je vous recommende de lire sur le sujet.  Les diverses astuces pour accélérer les calculs sont aussi surprenantes qu’efficaces!

Euler Project

Un site qui propose des problèmes mathématiques à être résolus par ordinateur!  Il y a un hic!  Il devient assez rapidement évident que la solution est bien souvent (pour ne pas écrire toujours) algébrique et mathématique.

C’est ce dont je me suis encore rendu compte récemment, en scrappant toute une nuit à faire des calculs pour résoudre le problème 131!


Il y a tant d’articles sur le sujet qu’un simple recherche Google devrait suffire à vous tenir occupé en lecture jusqu’à la fin des temps!

Pour ma part, par pur amusement, je me suis attardé à résoudre ces petits problèmes d’une façon surprenante : le préambule, le premier article, la seconde partie et la dernière partie.

Pour un aperçu des techniques de résolution (autres que la force brute), il y a cette liste.

EinStein würfelt nicht!

Communément appelé EWN, ce petit jeu renforme une quantité de particularités contre-intuitives. Autre difficulté, l’aspect probabiliste qui vient tout brouiller les cartes!

Vous pouvez y jouer sur le site de jeux Little Golem si ça vous intéresse.  Pour ma part, je planche sur quelques idées de stratégies que j’entends bien tester avec un programme bientôt.


Un petit jeu tout simple!  Et pourtant!

J’ai commencé à étudier de plus près le ruzzle comme en témoigne cet article et celui-ci.

Comme je n’ai toujours pas trouvé de grille meilleure que celle de M. Müller, ma quête se poursuit! Des nouvelles pour très bientôt!


Opérations dangereuses

4 mars 2015

Un excellent article sur les unsafe operations.

MySQL, PostgreSQL et optimisation

4 mars 2015

Un eBook gratuit: Practical Guide to Query Optimization for MySQL and PostgreSQL.