Challenge mathématique #37 : Problème d'optimisation

[Bilsix]

Salut à tous !

Je crée un petit topic concernant le Challenge mathématique #37 !

Pour rappel, il s'agit de créer une "image des nombres premiers" en écrivant les nombres en spirales puis en entourant les nombres premiers. Comme par enchantement, de lignes droites apparaissent (à partir d'un graph de taille 200x200), sans qu'on ne puisse l'expliquer à l'heure actuelle.

Mon code est capable de dessiner le pattern, mais met énormément de temps.

La logique de mon programme me semble pourtant épurée :

- On passe par une structure évenement pour choisir de tracer un nombre de points choisi ou de tracer l'ensemble du graphe, avant de cliquer sur un booléen "Lancer le graphe".

- Une fois le tracé lancé, on voit les points apparaitre au fur et à mesure sur le graphe de la FA. Pour chaque chiffre, je calcule son abscisse et son ordonnée dans la spirale de chiffre centrée en 1, puis je regarde si le chiffre est premier. Si oui, je trace le point sur le graphe. Si non, je passe au chiffre suivant.

Le calcul de l'abscisse et de l'ordonnée d'un chiffre dans la spirale centrée en 1 semble prendre pas mal de temps. Pourtant, je ne fais rien de spécial :

- En entrée du VI, j'ai le sens de la spirale (gauche vers droite, droite vers gauche, haut vers bas, bas vers haut), l'abscisse et l'ordonnée du point précédent, et un cluster contenant l'abscisse max, l'abscisse min, l'ordonnée max et l'ordonnée min des points déjà calculés.

- En fonction du sens de la spirale j'incrémente/je décrémente l'abscisse/l'ordonnée pour "placer" le point. Une fois le point "placé", je regarde si les corrdonnées du point dépassent les max/min du tableau. Si oui, on doit changer de sens.

Je ne sais pas si je suis super clair... Quoiqu'il en soit, j'ai vraiment du mal à optimiser encore plus mon code.

Peut-être ai-je utilisé une mauvaise méthode ?

Vous trouverez mon code en PJ !

Au plaisir,

[Michael.C]

Tu pourrais donner la valeur moyenne de ton temps d'exécution ?

Car je viens de faire le test, je suis à 4,2 secondes par exécution, et je trouve pas cela énorme.

[Michael.C · Accepted solution]

Aller cadeau, je tombe à 100ms le run :).
J'ai fait 3 optimisations :

au niveau du sous vi :

 -> Structure Element en place pour optimisation de la mémoire

-> Activation fonction inlining du sous vi -> Gain de vitesse d'accès du main.

Au niveau du main :

-> Retrait de l'appel à référence pour le stop par une simple variable locale, et là c'est magique 🙂

[Bilsix]

C'est super Michael.C, merci !!

- Je ne m'étais jamais intéressé à la structure éléments en place. Ca me parait très utile.

- Quand tu parles d'inlining, tu parles de ne pas autoriser la mise au point du VI ?

En tout cas, merci à toi, c'est un gain de temps énorme...

[Michael.C]

L'inlining est une option apparue dans LV. Il s'agit "d'indiquer" à Labview qu'il doit considérer ce code comme faisant partie intégrante du diagramme du VI appelant.

Cela permet de réduire considérablement les temps d'accès, par contre ce mode entraine des restrictions :

1- Mise au point désactivé

2 - Vi ré entrant interdisant l'utilisation de registre à décalage

3 - Doit supporter les appels multiples.

Le gain de temps sur ton programme vient surtout de la suppresion de la référence pour le bouton stop au bénéfice d'une variable locale, ce qui a réduit les temps d'accès.

Par contre j'ai regardé le poste sur la communauté pour le challenge, et j'ai pas encore trouvé comme les autres arrivent à de tels performances sur des matrices 2000*2000 -_-.

Je suis en train de me pencher sur le sujet, pour l'instant j'arrive à optimiser le calcul de la matrice, mais dès que tu ajoutes la contraintes de nombre premier mon temps de calcul explose.

Faut que je regarde cela à tête reposé à la maison :).

[Bilsix]

C'est excellent, merci beaucoup.

Oui, les temps inférieurs à 0.5s pour du 2000x2000 (on est quand même à 4 millions de points !), c'est phénoménal...

Bon, je gagne pas mal de secondes en ne mettant plus à jour la FA pendant l'execution du calcul (affichage du "temps écoulé", dessin sur le graphe, numéro du chiffre en cours dessiné, etc), mais je ne descends carrément pas aussi bas...

[Michael.C]

Oui c'est les premières optimisations que j'ai faite :)..

Après une autre hypothèse qui va apporter un gain non négligeable, c'est d'ajouter un aspect "prédictif" à l'incrémentation de ton chiffre.

Dans ton programme actuel, tu testes toutes les valeurs de "i" dans ta boucle, ce qui n'est pas optimisé.

En effet, au delà de 2 , tu peux directement éliminer les nombres "paires", ce qui t'enlèvera déjà une bonne partie des points. Par exemple en cablant une formule de type (x+1)*2+1 au niveau de ta valeur de test, cela devrait te faire gagner encore un peu de temps :).