[Ruby] Optimisation de fonctions
| King Kadelfek |
Posté le 07 Déc 2008 à 14:46
|
|
 Messages : 44 GCPoints : 37244 |
Bonjour, pour mon programme de traitement de maps Rpg Maker, j'aurais besoin d'une optimisation de certaines fonctions. Ce sont des fonctions appelées plusieurs millions de fois lors du traitement d'un gros projet, alors le moindre caractère a son importance. Note : je me suis longtemps demandé si ce n'était pas un codage spécial de nombre sous forme d'octets. J'ai tenté à peu près tout ce que je connaissais dans ce domaine, mais pas moyen d'exprimer un nombre de cette façon. Voir la dernière capture d'écran pour voir l'utilisation successive des deux fonctions. Fonction to_128 La première fonction a pour but de faire des divisions successives d'un entier par 128. Ensuite, on prend le modulo de cet entier, on y ajoute 128, et on l'ajoute en tant qu'octet à une chaîne. Voici le code : Code :
def to_128(chiffre)
str = (chiffre % 128).chr
while (chiffre >= 128)
chiffre /= 128
str = (chiffre % 128+128).chr << str
end
return str
end
Voici une capture d'écran pour montrer le traitement appliqué (les principales étapes de calcul sont indiquées) :  Le résultat :  Comme vous pouvez le voir, les chiffres entourés en rouge se retrouvent bien dans la string générée. Je cherche un moyen d'accélérer cette fonction. J'ai fait tout ce que j'ai pu, dans l'état actuel de mes connaissances. ------------------------------------------- Fonction trouve_nombre Cette fonction est beaucoup plus complexe. C'est le penchant de to_128. Elle consiste à prendre une chaîne, à partir d'une position donnée, et à récupérer tous les octets supérieurs à 128. Ensuite, elle soustrait 128, et les met à une certaine puissance, dépendant de leur position dans la chaîne. On récupère ensuite le nombre généré. Le problème étant que l'on doit d'abord savoir sur combien d'octets dans la string s'exprime le nombre avant de pouvoir faire des traitements. Code :
def trouve_nombre(contenu, pos=@pos)
pos_fin = pos
while(contenu[pos_fin]>=128)
pos_fin += 1
end
nombre_ch = contenu[pos..pos_fin].unpack('C*')
nombre = 0
puiss = nombre_ch.size-1
(0).upto(nombre_ch.size-2) {|i|
nombre = nombre+(nombre_ch.at(i)-128)*@puissance_128[puiss]
puiss -= 1
}
nombre += nombre_ch.last
# Pour d'autres traitements
@plus_pos = nombre_ch.size
return nombre
end
Les puissances de 128 sont générées au début du programme avec ce code : Code : def creer_puissance_128(max)
@puissance_128 = []
for i in 0...max
@puissance_128[i] = 128**i
end
end
L'utilisation des deux fonctions :  Est-ce que quelqu'un connaîtrait un moyen d'optimiser l'une des deux fonctions ? Je le répète, la moindre modification dans la syntaxe permet des gains énormes de temps. D'avance, merci. :) |
|
| Mod |
Posté le 07 Déc 2008 à 17:49
|
|
 Messages : 4954 GCPoints : 2100823 |
Personnellement, je suis loin d'être suffisamment experimenté en Ruby pour pouvoir optimiser un tel code... Néanmoins, je remarque la répétition de puissance de deux, qui devrait te faire gagner quelques microsecondes : Dans to_128, la ligne chiffre /= 128 peut être remplacée par un chiffre >>= 7. Effectuer un right shift est bien plus rapide que diviser, tout du moins, c'est le cas au niveau matériel, et c'est sensible en programmation compilée. J'ignore comme peut être implémenté cet opérateur sous l'interpréteur Ruby. Chez moi, j'ai majoritairement un gain de temps, mais parfois aussi l'inverse, mais mon PC a des sautes d'humeur régulières (micro-blocages) qui peuvent influencer ce résultat, je ne me fierai donc pas à ça. Même chose, mais dans l'autre sens dans creer_puissance_128, il est possible de remplacer - toujours avantageusement, en théorie - 128 ** i par un left shift : i << 7. C'est tout ce que je peux en dire dans l'état actuel de mes connaissances... |
|
| King Kadelfek |
Posté le 09 Déc 2008 à 13:55
|
|
|
Messages : 44 GCPoints : 37244 |
J'ai testé un peu, et trouvé ça : Ce n'était même pas vraiment dans la doc... J'ai donc essayé ça : Code : chiffre >>= 7 Mais il n'y a pas de gain, malgré 206169 appels à la fonction. Peut-être y en aura-t-il sur un nombre plus grand d'appels. Je me suis aperçu de quelque chose : je n'ai pas vraiment besoin de faire tourner une boucle while. Il faut juste que je sache combien de fois faire tourner la boucle. 65 000 / 128 = 507 507 / 128 = 3 3 < 128 => on arrête Pour 65 000, cette ligne : Code : while (chiffre >= 128) Pourrait être remplacée par cette ligne : Code : for i in 0..1 Il faut juste que je sache à l'avance combien de fois il faut diviser 65 000. Ça revient à dire 65 000 est entre 128**2 et 128**3, alors on ne le divise que deux fois. Je suis en train de tenter un Regexp pour trouve_nombre. |
|
Voir le profil
Envoyer un message privé