Hello tout le monde
 
Voilà quelques temps que je m'amuse à créer des fractales Markus-Lyapunov avec deux ou trois logiciels. Il y a deux semaines, j'ai décidé d'apprendre le Python en créant mon propre programme à partir de zero.
Rien de tel qu'une bonne motivation pour apprendre !
 
Ayant de solides connaissances en PHP, l'entrée dans le monde Python n'a pas durée plus de deux jours
 
Plus sérieusement, les fractales markus-lyapunov sont assez interessantes à étudier et à programmer, sans compter l'aspect inédit qu'elles offrent. Si vous ne connaissez pas, cherchez rapidement sur google, on trouve quelques sites qui en parlent.
Le calcul étant assez long, elles sont très peu connues
 
Voilà mon code actuel :

#!/usr/bin/python
# -*- coding:Utf-8 -*-
# Fractales Lyapunov - Tig'Prod' - Tigriss - 2005
 
from math import *
import Image
import psyco
psyco.full()
 
def exposant_lyapunov(a,b,init,itera):
    "Calcul de l'exposant. a -> x, b -> y, init -> itérations d'ammorçage, itera -> itérations de calcul"
    global log2
    sequence=[a,b,b,a]
    max_seque=3
    x=0.5
    total=0
    i=0
    seque_init=-1
    while i < init:
        i = i + 1
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
    i=0
    seque_init = -1
    while i < itera:
        i = i + 1
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
        total=total+(log(abs(sequence[seque_init]-2.0*sequence[seque_init]*x))/log2)
    exposant=total/itera
    return exposant
 
def couleur(exposant):
    "Calcul de la couleur d'un pixel selon la palette utilisée et son exposant"
    global maxResult
    global minResult
    global iterations_used
    global longueur_palette_plus
    global longueur_palette_minus
    global colpalplus
    global colpalminus
    if exposant > 0:
        echelle=(maxResult/longueur_palette_plus)
        cindex = abs(int(exposant/echelle))
        if cindex > longueur_palette_plus - 1:
            cindex = longueur_palette_plus - 1
        if cindex < 0:
            cindex = 0
        final = colpalplus[cindex]
    else:
        echelle=(minResult/longueur_palette_minus)
        cindex = abs(int(exposant/echelle))
        if cindex > longueur_palette_minus - 1:
            cindex = longueur_palette_minus - 1
                if cindex < 0:
            cindex = 0
        final = colpalminus[cindex]
    return final
 
# Parametres des palettes de couleur
colpalplus=[]
colpalminus=[]
 
## Reglages de base
maxResult=(sqrt(5)-1.0)/2.0
minResult=(sqrt(5)+1.0)/2.0
longueur_palette_plus=256
longueur_palette_minus=511
 
## Palette CHAOS
# bleu -> noir
#i=0
#while i < 256:
#    colpalplus.append((0, 0, 255 - i))
#    i = i + 1
 
# blanc -> noir
#i=0
#while i < 256:
#    colpalplus.append((255 - i, 255 - i, 255 - i))
#    i = i + 1
 
# noir -> noir
i=0
while i < 256:
    colpalplus.append((0, 0, 0))
    i = i + 1
maxResult=1.9333897126112
 
## Palette STABLE
# noir -> jaune -> blanc
#i=0
#while i < 256:
#    colpalminus.append((i, i, 0))
#    i = i + 1
#while i < 511:
#    colpalminus.append((255, 255, i - 255))
#    i = i + 1
 
# blanc -> gris -> noir
#i=0
#while i < 256:
#    colpalminus.append((255-i, 255-i, 255-i))
#    i = i + 1
#while i < 511:
#    colpalminus.append((i - 255, i - 255, i - 255))
#    i = i + 1
 
# noir -> jaune
i=0
while i < 256:
    colpalminus.append((255-i, 255-i, 0))
    i = i + 1
longueur_palette_minus=256
minResult=-10.462186805818
 
# Parametres de la fractale
## Tailles image
largeur=400
hauteur=400
## Itérations d'ammorçage
iterations_unused=200
## Itérations de calcul
iterations_used=400
## Coordonnées du point bas gauche
## MEMO : x = largeur, y = hauteur
x=2.52
y=2.87
## Pas de coordonnées pour chaque pixel
steps=0.002825
 
## NOTE IMPORTANTE
## Ne jamais atteindre 4 pour une coordonnée ((steps*taille)+x ou y)
## sous peine de math overflow
 
image_finale=[]
 
im = Image.new("RGB",(largeur,hauteur))
 
log2=log(2)
 
# Construction
i=hauteur
j=1
while i > 0:
    while j <= largeur:
        image_finale.append(couleur(exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used)))
        j = j+1
    j=1
    print i,"(",hauteur," )"
    i = i - 1
 
# Enregistrement
im.putdata(image_finale)
im.save("lyapunov.jpg" )
 
print "Terminé"

 
(J'espere que la présentation et les commentaires vous iront ^^)
 
Une fois lancé, ce code va prendre a peu pret une minute (Duron 2Ghz), et sortir une image 400*400 peinte en jaune/noir (vous pouvez jouer avec les quelques palettes déjà présentes, dans CHAOS et STABLE).
 
Comme dis plus haut, l'execution prend environs 1 minute 20 sur un Duron 2Ghz, sous Ubuntu, et en dirigant le flux de sortie vers /dev/null.
Le "problème", c'est qu'avec mon programme habituel, la même fractale se fait en 20/30 secondes à tout casser.
 
Aussi, j'ai cherché à optimiser le code (bon moyen d'apprendre ), avec un certain succès (2 minutes, avec mon tout premier code fonctionnel). Psyco m'a aussi permit de gagner 10/15 secondes.
 
Mais maintenant, je ne sais pas quoi tenter d'autre, aussi, je fais appel à vous pour m'aider à améliorer la bête, si celà est possible
Et en passant, si qqun a déjà bossé sur les Lyapunov, qu'il se manifeste !
 
Actuellement, j'ai deux voies possibles à étudier, en calcul pur :
- Améliorer l'algo de calcul en ligne 33. Après un tour exhaustif sur le net, j'ai récupéré deux ou trois programmes (en MatLab, Java, et C), chacun utilisait un algo légérement différent, comme par exemple deux cosinus et un sinus dans la formule. L'actuel est le seul que j'ai pu faire fonctionner correctement
- Limitation du calcul selon si on est en zone de chaos (noir), ou en zone de stabilité (jaune/marron/noir intérieur aux formes). Le programme que j'utilise fonctionne de cette maniere, c'est très net quand il passe dans une zone de chaos total. Idem, je n'ai pas réussi à trouver un systeme correct pour faire celà, sans pour autant perdre les couleurs (le chaos est noir dans cet exemple, mais on peux en faire ce qu'on veut).
 
Si qqun a une idée...
 
Reste ensuite le côté programmation pure, et là, il y a certainement tout un tas de subtilités que je n'ai, de fait, pas encore intégré (comme par exemple une différence notable entre while et for, ou des choses du genre). Hormit ce point, je ne pense pas avoir de probleme structurel.
 
Voilà ! Je fais donc appel à vos lumières éclairées ! Et merci d'avance de m'avoir lu jusqu'au bout

Si ton programme "habituel" est dans un langage compilé rapide (C/C++) ou même en Java/C#, ça n'a strictement rien d'étonnant, le Python est un langage interprété relativement lent en termes de vitesse d'exécution.

Là je peux pas t'aider, à part à la limite te proposer de passer ton code au profiler

Sur le Python pur:
 

• Les docstrings, ça s'écrit avec des triple-quotes, donc

def exposant_lyapunov(a,b,init,itera):
    "Calcul de l'exposant. a -> x, b -> y, init -> itérations d'ammorçage, itera -> itérations de calcul"

doit être transformé en

def exposant_lyapunov(a,b,init,itera):
    """Calcul de l'exposant. a -> x, b -> y, init -> itérations d'ammorçage, itera -> itérations de calcul"""

De plus il manque le prototype et ce docstring est franchement peu compréhensible, en tout cas à moi il ne me sert absolument à rien (a->x wtf? qu'est-ce que je peux en tirer?)
 

• Trop de variables globales -_-
• Tu pourrais placer les données de configuration dans un fichier à part importé au lancement
• Dans l'idéal, utilise le module "logging" plutôt que des print pour logger le déroulement de ton bouzin
• remplacer

i=hauteur
j=1
while i > 0:
    while j <= largeur:
        image_finale.append(couleur(exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used)))
        j = j+1
    j=1
    print i,"(",hauteur," )"
    i = i - 1

par

for i in xrange(hauteur, 0, -1):
    for j in range(1, largeur+1):
        image_finale.append(couleur(exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used)))

et tes

i=0
while i<value:
    i+=1

par des

for i in range(value):

• Concatène les opérations similaires.

je vois un  

i=0
while i < 256:
    colpalplus.append((0, 0, 0))
    i = i + 1

et quelques lignes plus bas

i=0
while i < 256:
    colpalminus.append((255-i, 255-i, 0))
    i = i + 1

Le tout peut devenir

for i in range(256):
    colpalplus.append((0, 0, 0))
    colpalminus.append((255-i, 255-1, 0))

Tu peux également utiliser les list comprehensions:

colpalplus = [(0, 0, 0) for i in range(256)]
colpalminus = [(255-i, 255-i, 0) for i in range(256)]

Mais ça résulte en deux itérations sur [0, 256[ au lieu d'une, donc les perfs sont probablement inférieures à la version précédente.

• Tout fichier python est un module, il est donc d'usage de planquer le code "exécuté" ne servant pas à l'initialisation du module lui même derrière:

if __name__ == "__main__":

De cette manière ce code n'est pas exécuté quand on importe le fichier.
 
Après, sur les calculs en tant que tels je peux pas t'aider, étant une quiche en maths.

 
Source ?

http://www.python.org/doc/current/ [...] 0000000000
 
 
C'est pas un impératif (c'est une convention), mais un docstring monoligne ne correspond pas aux conventions et du multiline avec des single quotes c'est moche  
 
 
Accessoirement, sur les perfs:
 
Sans Psyco
Code originel
>pythonw -u "frac.py"
>Exit code: 0    Time: 195.798
 
Code avec boucles modifiées
>pythonw -u "frac_modded.py"
>Exit code: 0    Time: 179.000
 
Donc gain de ~8%
 
Avec Psyco, les optimisations des boucles font que le gain est statistiquement inexistant
 
Code originel
>pythonw -u "frac.py"
>Exit code: 0    Time: 46.580
 
Code boucles modifiées
>pythonw -u "frac_modded.py"
>Exit code: 0    Time: 46.520
 
(runs fait sur un Athlon64/3000+)
 
Par contre tu peux peut-être voir du côté de Shed Skin, c'est un compilateur Python > Natif, il est en tout début de dev mais vu que ton code c'est principalement des maths ça passera peut-être (edit: marche pas, il comprend pas où trouver PIL)
(pas de bol, parce que si on dégage la gestion d'images ça compile, et ça va bien vite )
 
Et dans un futur qui se rapproche, Pypy arrivera peut-être un jour à être plus rapide que CPython

 
Sur plusieurs lignes oui tout à fait c'est indispensable (à moins de trafiquer) mais là il s'agissait de lignes simples, donc pas besoin de s'encombrer avec des triple quotes.
 
Comment ça mes interventions sont sans intérêt ?

Oui mais j'y ai dit que ses lignes simples elles puaient du bout

C'est z-lyapunov (ICI) que j'utilise. Un peu ancien, mais il fonctionne, y comprit dans Wine.
En effet, c'est compilé, donc c'est plus rapide. Mais ça fait une sacré différence tout de même, presque tout ce que j'ai pu lire montre que Python réagit plus vite que ça, donc...
 

 
Oui, c'est ce que je comptais faire sous peu, même si je suis certain des points chauds (ligne 33... )
 

 
A vrais dire, comme dis plus haut, j'apprend en direct, donc c'est pas évident de connaitre ce genre de conventions tordues Surtout que j'ai appris les docsstrings qq heures avant
Quand au contenu... j'en suis bien conscient. A terme, ça sera lisible. En attendant, ça remplit parfaitement sa tache de memo perso, et c'est plus propre que des commentaires.
 

Sauf que j'ai besoin de passer ces variables. Et tout rentrer en argument, c'est pas super propre non plus. Une autre subtilité que je ne connais pas ?
 

Nop, dès que j'ai un code clean, j'attaque une interface graphique. L'idéal serait de pouvoir visionner la construction en temps réel. J'envisage wxPtyhon pour ça.
 

Ok, je vais aller voir ça

Bon ben dès que j'ai fini de me battre avec les quote, j'applique, merci
J'aurais du regarder les for de plus pret, ainsi que range, que j'ai déjà rencontré, en plus...
 

Là on touche un autre truc. Cette partie sera completement reconstruite sous peu. J'ai besoin de pouvoir générer des palettes plus facilement qu'a la main comme ça. Sans compter que les palettes peuvent avoir la longueur que l'on souhaite (cf la palette STABLE Noir/Jaune/Blanc), et non identique avec la palette opposée.
Mais je note tes améliorations, ça va reservir.
 

J'ai vu un truc du genre, en effet. J'ai passé, vu que pas vital sur le momment, mais je regarde ça plus sérieusement sous peu.
 

Et ben vais pas me géner, on va sauver les infos dans un fichier, puis suffira d'executer la création de l'image dans un second script Je regarde ça aussi
 

On est tous une quiche de qqchose
 
Merci pour touts ces infos, j'ai de quoi bien m'occuper now !

Bof

J'ai passé un coup de profiler (sans avoir activé psyco), il a trouvé que... les fonctions abs() et log() sont appelées 64 millions de fois chacune (non non, pas blague, sur 160.000 appels d'exposant_machin) et bouffent à elles deux 44% des ressources (23 et 21, par contre je me souviens plus laquelle des deux prend 23 et laquelle prend 21).
 
Le reste, c'est le reste du code dans ta fonction de recherche de l'exposant, donc normal

Aucun rapport

 
(merci pour le coup de profiler)
Assez impressionant. Mais assez normal en fait, ça fait 160.000*400 pour l'abs, plus 160.000 autres pour la couleur, idem pour log. Et encore, le log(2) est en variable
J'ai une piste pour un algo qui serait un poil plus léger, je suis en train d'essayer de le comprendre, lol
 

 
Ben... je n'ai plus besoin de stocker des variables en fichier à partir du momment où tout est défini à la main en interface. Sans compter que sauver les parametres spécifique à une seule image n'est pas très utile. Ou alors j'ai pas bien saisis ton idée

Hum, je viens de faire qq tests, et...
 
Original (w/psyco) : 1m20/25
Boucles optimisée (w/psyco) : 1m7/8 (Le gain correspond)
Mais :
Boucles optimées (wo/psyco) : 3m10
 
Pour le coup, je comprend plus là Sans compter que non optimisé et sans psyco, je fais plutot 2m10...
 
M'enfin, ça commence à faire une sacrée avancée !

Yes !
 
Je viens de trouver un nouvel algo bien plus performant ! Et même assez logique, si j'avais un peu mieux suivit mes maths (comme quoi... )
 
Voilà la nouvelle fonction exposant_lyapunov :
 

def exposant_lyapunov(a,b,init,itera):
    "Calcul de l'exposant. a -> x, b -> y, init -> itérations d'ammorçage, itera -> itérations de calcul"
    sequence=[a,b,b,a]
    max_seque=3
    x=0.5
    total=1
    seque_init=-1
    for i in range(init):
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
    seque_init = -1
    for i in range(itera):
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
        total=total*abs(sequence[seque_init]-2.0*sequence[seque_init]*x)
# Cet if est là pour éviter qu'a un momment, "0.0" arrive dans la log, ce qui n'est mathématiquement pas possible
# Je ne sais pas encore d'où il vient, ni si "1" est la bonne chose à faire. En attendant, le reste marche. Je ferais une comparaison par différence sous toshop avec ces deux techniques
    if total <= 0:
        exposant=log(1)/itera
    else:
        exposant=log(total)/itera
    return exposant

 
Avec ce nouvel algo, je supprime 99% des log, et du coup, j'atteins les 30 secondes de calcul ! 55% de gain
Doit encore y avoir à gratter, sur l'if entre autres, et y'a ptet qqchose à faire avec l'abs.
 
Je vais me pencher sur la colorisation, qui doit bien bouffer aussi.
 
EDIT :
Bon, cet algo pose problème. Les parties noires/sombres des zones stables sont changés en jaune pur, et j'ai l'impression que ça morfle sur les.... "branches" sombres, le dégradé sombre n'est pas le même.
Hormit ça, le reste est ok.

Très interressant ton programme. Je viens de le faire tourner sous linux.
Voici les perfs avec psyco :  
 

 
sans psyco

   
 
c'est sans appel !
 
Mon proc

 
 
Pourrais tu nous donner un petit lien pour l'algo et la formule j'ai la flemme de chercher

Oui, psyco est un JIT ( http://en.wikipedia.org/wiki/Just-in-time_compilation ), il fonctionne extrèmement bien pour des programmes très répétitifs dans ce genre.
 
Pour des programmes avec très peu de répétitions, le gain est largement inférieur (il est inférieur à 50%), et la consommation en RAM prend un ordre de grandeur.

 
Hop !
 
http://perso.wanadoo.fr/charles.vassallo/index.html -> Bon site, un des plus complet sur le thème
http://gjoly.free.fr/fractales-pro [...] osant.html -> Page plus mathématique, mais très intéressante aussi
http://www.chaospro.de/lyap.php -> Et vala là où j'ai déniché le dernier algo
 
En parlant d'algo, j'ai corrigé celui de tt à l'heure :
 

def exposant_lyapunov(a,b,init,itera,ligne):
    "Calcul de l'exposant. a -> x, b -> y, init -> itérations d'ammorçage, itera -> itérations de calcul"
    global log2
    sequence=[a,b,b,a]
    max_seque=3
    x=0.5
    total=1
    total2=0
    seque_init=-1
    for i in range(init):
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
    seque_init = -1
    for i in range(itera):
        seque_init=seque_init + 1
        if seque_init > max_seque:
            seque_init = 0
        x=sequence[seque_init]*x*(1.0-x)
        total=total*abs(sequence[seque_init]-2.0*sequence[seque_init]*x)
    if total == 0:
        exposant=(log(0.00000001)/log2)/itera
        print "############### ", exposant, total2/itera
    else:
        exposant=(log(total)/log2)/itera
    return exposant

 
Modif toute bête (ajout de /log2)
 
Mais il reste un problème, certains des points les plus sombres (croisement des "fils", voire dans les fils pour qq pixels) dans les zones stables sont "brulés" dans l'opération.
A un momment, total devient tellement petit que le résultat fait 0, et comme c'est une multiplication (l'algo précédent etait une addition), une fois total passé à 0 toute la suite est brulée. Je n'ai aucune idée pour contrer ça mathématiquement, par contre, on peut stocker les coordonnées à probleme, pour les recalculer avec l'algo précédent.
 
Si qqun voit une autre idée...
 
Voilà une version fiable :

 
Et voici une version brulée :

up
 
Je suis en train de mettre en place le système de "récupération" des pixels perdus. On va bien voir ce que ça donne ^^
 
Par  contre, il y a un probleme de math range quand on pousse trop des itérations. Ca, c'est vraiment pas génial, il faudrait passer outre, sinon on ne peut atteindre une précision suffisante pour une image "propre" (1000 itérations d'initialisation, et 5000 de calcul).
Enquête en route, et si jamais un spécialiste math sous python passe par ici...

BTW édite tes posts et remplace tes [code] par des [code=python]

dans  

exposant=(log(0.00000001)/log2)/itera

je pense que tu peut optimiser légèrement,
log(a)/log(b) = log(a-b)
donc tu dois pouvoir faire ( si jme trompe pas ) :

exposant = log(0.000000001 - 2)/itera

et pareil a d'autres endroits du code ... ca te fait économiser une division, je sais pas si ca permet de gagner kkchose de sensible mais c'est toujours ca.
 
[edit pas édité mais après réflexion ...]
Un log d'un nombre négatif spa bon chuis con ^^
 
( plus bas si total est > 2 tu peut t'en  servir, mais le test sera plus lourd que le gain je suppose )

 
Fait. En fait, j'avais essayé au début, mais la preview ne m'avait rien donnée... J'ai du me gourrer en tapant "python"
Du coup, j'ai édité les posts précédents.
 

 
En fait, cette partie du code était là pour éviter au programme de planter avec un log(0), ou pire, un log négatif
Maintenant, je met la valeur minResult à la place. Ca résoud rien, mais c'est plus visible
 
Oui, en effet, le gain est annulé En plus, cette opération n'est pas executée un grand nombre de fois, comparé au calcul par itérations.
 
Sinon, hier, j'ai séparé la boucle principale du programme en deux, une pour remplir une liste avec les exposants, et une autre pour les couleurs. Je verais dans le futur si je dois refusionner ou pas, mais je garde cette fenetre ouverte pour pouvoir faire un traitement à la liste avant de passer à la couleur :
 
Remplacer la grande boucle finale par :
 

for i in xrange(hauteur, 0, -1):
    liste_exposants_ligne=[]
    for j in range(1, largeur+1):
        liste_exposants_ligne.append(exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used))
        #exposant=exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used,i)
        #image_finale.append(couleur(exposant))
    liste_exposants.append(liste_exposants_ligne)
    print i,"(",hauteur," )"
 
for i in range(0, hauteur):
    for j in range(0, largeur):
 
        #liste_exposants_ligne.append(exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used))
        #exposant=exposant_lyapunov(i*steps+y,j*steps+x,iterations_unused,iterations_used,i)
        image_finale.append(couleur(liste_exposants[i][j]))
    print i,"(",hauteur," )"

 
Et

image_finale=[]

 
Par

liste_exposants=[]
image_finale=[]

 
Bon, et faut que je trouve un moyen de me débarraser des problèmes de calcul trop poussé...

up
 
Dispositif de récupération des parties perdues en place, et ça consomme presque rien en temps.
 
Maintenant, j'essaye de comprendre pourquoi quand on pousse trop les itérations, ça plante
 
Je posterais une version fonctionelle ce soir