Concernant les performances, j'ai fait quelques améliorations en trois temps que j'ai documentées dans la branche need-for-speed, en résumé :
Casser la symétrie : accélération de 8 %.
Utilisation d'une borne de c_max précalculée par une autre heuristique : accélération de 88 %.
Micro-optimisations dans le goulet d'étranglement : 25 %.
La 2e est utile en pratique, mais elle ne doit évidemment pas être employée pour évaluer les performances du FPTAS « pur ».
Ceci dit, quelques mauvaises nouvelles :
Après quelques expérimentations, je ne pense pas que le FPTAS soit vectorisable. La structure fondamentale est un cache, donc un dictionnaire Python est déjà bien adapté.
J'ai aussi essayé l'accélération soi-disant offerte par Pypy, mais les performances sont même légèrement dégradées.
Il me reste l'hypothèse Numba, jusqu'à présent je n'arrive même pas à l'exécuter en JIT, et les messages d'erreurs sont plutôt obscurs.
Je n'ai pas dit mon dernier mot, mais il est possible qu'on ne puisse pas faire mieux avec Python. Autres possibilités que je vois actuellement :
Réécrire le FPTAS (qui ne fait que quelques lignes) dans un langage que tu connais bien, C. Tu dois pouvoir interfacer facilement (mais je ne parle pas d'expérience) Python et C à l'aide de la bibliothèque ctypes.
Utiliser Redis pour gérer le cache (je ne sais plus si tu as vu Redis avec moi, c'est très facile à prendre en main en tout cas).
Concernant les performances, j'ai fait quelques améliorations en trois temps que j'ai documentées dans la branche need-for-speed, en résumé :
La 2e est utile en pratique, mais elle ne doit évidemment pas être employée pour évaluer les performances du FPTAS « pur ».
Ceci dit, quelques mauvaises nouvelles :
Je n'ai pas dit mon dernier mot, mais il est possible qu'on ne puisse pas faire mieux avec Python. Autres possibilités que je vois actuellement :