__getattribute__ est-il chronophage ? [Résolu]

[rambc]

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

[wiztricks]

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

[rambc]

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]

__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]

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]

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

[rambc]

Au temps pour moi, je plaide coupable...

[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

[rambc]

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]

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]

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]

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]

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]

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]

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

[rambc]

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]

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

[rambc]

Justement en parlant de construction, je vais m'attaquer à ce problème. C'est aussi dans cette optique que j'ai fait ce programme.

[rambc]

Pour info, les meilleures performances sont maintenant de 0,08s en moyenne avec un maximum de 3,9 s.

[wiztricks]

Envoyé par rambc

Pour info, les meilleures performances sont maintenant de 0,08s en moyenne avec un maximum de 3,9 s.

C'est bien çà fait plus de 3X de mieux mais il manque un 8X.
- W