__getattribute__ est-il chronophage ?

**rambc** · 26/02/2013, 15h21

Bonjour,
côté performance, vaut-il mieux éviter d'utiliser __getattribute__ ?

**wiztricks** · 28/02/2013, 12h49

Salut,
La réponse est "oui".
- W

**rambc** · 28/02/2013, 13h38

Salut.

Du coup, il vaut mieux passer par une méthode personnelle appellant la bonne méthode suivant la valeur d'une chaîne.

D'où sais-tu que c'est chronophage ? Python doit-il à chaque fois analyser la classe ? Un dictionnaire n'est-il pas créé automatiquement ?

**wiztricks** · 28/02/2013, 14h05

__getattribute__ sera toujours appelé que l'attribut soit méthode ou pas.
C'est dans le corps de la fonction __getattribute__ qu'on ira regarder dans des dict pour savoir quoi retourner. Ca fait quand même pas mal d'indirections (et d'overheads) pour juste retourner une méthode ou un attribut.

__getattr__ n'est appelé lorsque le nom n'est pas dans le dict.
Une optimisation possible dans certains cas est d'ajouter le nom/valeur dans le dict lors du premier appel: la résolution du nom suivante tapera directement dans le dict plutôt que de passer par l'indirection __getattr__.

- W

**rambc** · 28/02/2013, 14h18

J'ai du mal à te suivre. Peux-tu juste donner un exemple un peu fictif pour clarifier ton propos (si tu as 5 min).

As-tu sous la main un script prouvant ce que tu avances ?

**wiztricks** · 28/02/2013, 14h38

Tout çà est déjà écrit dans la documentation.
Que pourrais-je y ajouter?
- W

**rambc** · 28/02/2013, 14h40

Au temps pour moi, je plaide coupable...

**wiztricks** · 28/02/2013, 15h13

Et si vous preniez le temps de raconter votre besoin et l'intérêt de passer par une redirection? Cela permettrait d'avoir une discussion plus intéressante que RTFM.
- W

**rambc** · 28/02/2013, 17h47

Envoyé par wiztricks

Et si vous preniez le temps de raconter votre besoin et l'intérêt de passer par une redirection? Cela permettrait d'avoir une discussion plus intéressante que RTFM.
- W

Sauf que pour le coup, c'est un peu mérité.

Pour la (petite) histoire, j'ai finalisé la partie résolution de mon sudoku, et maintenant que j'ai un truc qui marche pas trop mal, je veux partir à la recherche des optimisations possibles.

Par exemple, j'avais une première version qui était très lente. Je me suis rendu compte que je demandais trop à Python de créer des classes sudoku.

Ensuite est venu mon questionnent sur __getattribute__ que j'ai utilisé par commodité.

**wiztricks** · 28/02/2013, 20h36

Salut,
J'ai quelque difficultés à suivre:

Par exemple, j'avais une première version qui était très lente. Je me suis rendu compte que je demandais trop à Python de créer des classes sudoku.

Il doit s'agir d'instances et non de classes.
La résolution d'un sudoku étant une fonction récursive, pas facile de comprendre la création de plein d'instances: quelques variables globales et des fonctions ancillaires pour (re-)initialiser la chose devraient suffire.

Ensuite est venu mon questionnent sur __getattribute__ que j'ai utilisé par commodité.

optimiser passe par réduire les niveaux d'abstraction (virer les classes!) plutôt qu'en ajouter.

Aurez vous le courage de poster votre code? Je ne sais pas si j'aurais le temps de le regarder d'ici le week end mais c'est tout ce que je peux offrir.

- W

**rambc** · 28/02/2013, 20h58

Bonne rectification.

T'inquiètes, je vais faire le ménage tout seul comme un grand. Le seul moment où je crée ~~des classes~~ des instances de classe, c'est au moment de la recherche par énumération quand plus aucune tactique de réduction rationnelle ne fonctionne. Je ne fais pas de l'énumération à chaque fois. Avec l'une des méthodes, j'ai un temps moyen de 0.3 secondes et un temps maxi de 45 secondes (cas très, très rares). Les tests ont été faits sur ces grilles.

Plus intéressant, la dite méthode ne semble pas avoir besoin de faire d'énumération brutale ! Elle a juste besoin de voir ce qu'il se passe uniquement au niveau directement supérieur de l'arbre de recherche.

Je vois comment éviter de créer inutilement des instances de classe via une simple pile. Je n'ai juste pas le temps de le faire pour le moment (je bosse dur sur un projet info qui demande pas mal de rédaction au propre très chronophage).

PS : je mettrais le code en ligne sous peu. Le 16 mars au plus tard, c'est sûr.

**wiztricks** · 01/03/2013, 12h13

J'espère que vous avez pris le temps de lire la prose de Peter Norvig (que j'avais mentionné dans un autre post sur l'interface graphique). Il a fait des millions de tests de résolution de grilles et constate:

The average time to solve a random puzzle is 0.01 seconds, and more than 99.95% took less than 0.1 seconds, but a few took much longer:

0.032% (1 in 3,000) took more than 0.1 seconds
0.014% (1 in 7,000) took more than 1 second
0.003% (1 in 30,000) took more than 10 seconds
0.0001% (1 in 1,000,000) took more than 100 seconds

note: si votre solveur est a 0.3s, vous avez un facteur 10/30 d'optimisation à réaliser.
- W

**rambc** · 01/03/2013, 13h48

Merci pour cette indication !

Mon programme permet aussi de classer des grilles, et j'ai une méthode purement rationnelle (en fait, c'est une conjecture bien solide que je fais).

De plus, mes tests en temps ont été fait avec des grilles n'ayant que 17 indices, soit deux fois moins que ce que l'on trouve dans les livres.

En toute rigueur, il faudrait comparer avec les mêmes grilles (pas la patience de faire le tri dans ce fouillis d'explications dans la page mentionnée).

Ceci étant entre 0,3 secondes et 0,1 secondes c'est un peu une course à l'échalote mais je regarderais la semaine prochaine tranquillement si je peux faire mieux.

**wiztricks** · 01/03/2013, 14h26

Envoyé par rambc

Ceci étant entre 0,3 secondes et 0,1 secondes c'est un peu une course à l'échalote mais je regarderais la semaine prochaine tranquillement si je peux faire mieux.

Je ne veux pas vous décourager mais il écrit "The average time to solve a random puzzle is 0,01 seconds". 0,1s c'est pour 99.95% des puzzle: il s'agit d'une distribution (un percentile) pas d'une moyenne.

Si on peut espérer un gagner un facteur 3 en optimisant.
Pour gagner un facteur 30, il faudra oser remettre à plat le design.

- W

**rambc** · 01/03/2013, 14h53

On verra... Ce n'est pas mon graal de toute façon.

**rambc** · 04/03/2013, 00h10

Envoyé par wiztricks

Si on peut espérer un gagner un facteur 3 en optimisant.
Pour gagner un facteur 30, il faudra oser remettre à plat le design.

Pas si sûr. Je viens de me rendre que le programme que tu cites s'arrête dès qu'une solution est trouvée. Or le mien examine toutes les possibilités et donc si un sudoku a 200 solutions, il les trouvera (tant qu'il y a assez de mémoire bien entendu).

Ceci explique la différence de temps. Je viens de rajouter un mode pour s'arrêter dès qu'une solution est trouvée. Je vais tester cela sous peu.

**wiztricks** · 04/03/2013, 11h02

Envoyé par rambc

Pas si sûr. Je viens de me rendre que le programme que tu cites s'arrête dès qu'une solution est trouvée. Or le mien examine toutes les possibilités et donc si un sudoku a 200 solutions, il les trouvera (tant qu'il y a assez de mémoire bien entendu).

Ceci explique la différence de temps. Je viens de rajouter un mode pour s'arrêter dès qu'une solution est trouvée. Je vais tester cela sous peu.

A priori une bonne grille de sudoku n'a qu'une solution (enfin, c'est ce qui se raconte dans les forums spécialisés sur la question et qui complique la construction automatique des "grilles").

- W