THE Regex
Il existe une Regex qui permet de déterminer si oui ou non un nombre est premier, au 1er abord c'est plutôt cool et pas trop compliqué (lkdjiin explique très bien le fonctionnement de la chose).
J'ai au début trouvé ca fun et intriguant, mais ensuite m'est assez rapidement venue à l'esprit la question des performances, je me doutais bien que ca ne vaudrait pas un petit algo de base, mais c'est encore pire que ce que je pensais ...
Les tests
J'ai donc fait quelques tests, le tout en C#.
Tout d'abord voici la fonction qui permet de déterminer si un nombre est 1er en utilisant une Regex :
static bool isPrimeRegex(int n) {
Regex regex = new Regex(@"^1?$|^(11+?)\1+$");
Match match = regex.Match(new String('1',n));
return !match.Success;
}
Et voici la même fonction, mais utilisant un algorithme plus classique :
static bool isPrimeClassic(int n) {
if ((n & 1) == 0) {
if (n == 2) {
return true;
}
else {
return false;
}
}
for (int i = 3; (i * i) <= n; i += 2) {
if ((n % i) == 0) {
return false;
}
}
return n != 1;
}
Pour les tests je vais simplement calculer le temps d'exécution des deux méthodes (j'effectue le test 3 fois pour être sûr que les chiffres obtenus concordent bien).
Pour mesurer le temps d'execution je vais simplement utiliser la classe Stopwatch, pas besoin ici d'avoir quelque chose de super précis, c'est surtout pour avoir une idée des performances.
static void Main(string[] args) {
int n = 10000
var watch = Stopwatch.StartNew();
for (int i = 1; i <= n; i++) {
isPrimeRegex(i);
//isPrimeClassic(i);
}
watch.Stop();
Console.WriteLine("Temps : {0} ms", watch.ElapsedMilliseconds);
}
Les résultats
| Nombre/Range testé | Temps Regex (en ms) | Temps classique (en ms) |
|---|---|---|
| 1 -> 100 | 2 - 2 - 3 | 0 - 0 - 0 |
| 1 -> 1.000 | 141 - 142 - 140 | 0 - 0 - 0 |
| 1 -> 10.000 | 42313 - 41934 - 42170 | 0 - 0 - 0 |
| 1.000.000 | 36 - 36 - 36 | 0 - 0 - 0 |
| 10.000.000 | 341 - 340 - 343 | 0 - 0 - 0 |
| 100.000.000 | 3383 - 3334 - 3320 | 0 - 0 - 0 |
| 1.000.000.000 | Crash - Crash - Crash | 0 - 0 - 0 |
On peut constater que l'algo de base prend beaucoup moins de temps pour effectuer le caclul, surtout lorsqu'il sagit de "grands" nombres.
En fait, l'algo classique prend tellement peu de temps que le timer reste à 0ms, il faut tester avec des intervalles de nombres beaucoup plus grands pour avoir un résultat significatif, et dans ces cas là, la méthode Regex sera plantée depuis un bon moment.
De plus, la méthode avec la Regex va avoir une utilisation mémoire assez impressionnante : durant mes tests elle a dépassé plusieurs fois le Go de RAM allouée et dans certains cas elle va même jusqu'à planter.
une petite explication
L'explication n'est pas très compliquée, pour que la Regex fonctionne on lui génère une chaine de caractères contenant n fois "1" où n est le nombre à tester :
- Pour le nombre 3, la chaine générée est 111
- Pour le nombre 8, la chaine générée est 11111111
- Pour le nombre 12, la chaine générée est 111111111111
- Etc.
Sachant que l'utilisation d'une chaine de caractères en mémoire (en C#) est de :
20 + (n/2) * 4 octets
-> où "n" est le nombre de caractères
-> où le "20" est l'object overhead pour un système 32 bits (à remplacer par "40" pour du 64 bits)
Il est facile de faire le compte quand la chaine à générer est composée de 3 milliards de "1" : 2000000080 octets = 1,86Go ... Ouch ...
Pour le fonctionnement de la Regex, je vous renvoie encore une fois vers le site de lkdjiin qui explique bien la chose, vous pourrez constater qu'en fonction du nombre à traiter, le nombre d'opérations peut être assez astronomique, ce qui explique la lenteur du calcul.
En résumé, même si cette Regex est assez fun dans son fonctionnement, il vaut mieux ne pas l'utiliser dans votre code : ca va être lent et en plus ca risque de planter sévèrement si le nombre est un peu trop grand.
Et puis ... une Regex c'est clairement pas fait pour ça ...