Factorielle en Python

6 septembre 2009 à 23:06:55

Bonjour,

Ce message pour cesser de polluer un topic qui a commencé à devenir hors sujet ICI.

Citation : Cacophrene

Vraiment géniale la joute sur le code de la factorielle...

Pour en terminer sur le sujet, j'ai regardé l'implémentation C de la fonction math.factorial (cf. le fichier mathmodule.c des sources de la version 2.6) :

static PyObject *
math_factorial(PyObject *self, PyObject *arg)
{
	long i, x;
	PyObject *result, *iobj, *newresult;

	if (PyFloat_Check(arg)) {
		double dx = PyFloat_AS_DOUBLE((PyFloatObject *)arg);
		if (dx != floor(dx)) {
			PyErr_SetString(PyExc_ValueError, 
				"factorial() only accepts integral values");
			return NULL;
		}
	}

	x = PyInt_AsLong(arg);
	if (x == -1 && PyErr_Occurred())
		return NULL;
	if (x < 0) {
		PyErr_SetString(PyExc_ValueError, 
			"factorial() not defined for negative values");
		return NULL;
	}

	result = (PyObject *)PyInt_FromLong(1);
	if (result == NULL)
		return NULL;
	for (i=1 ; i<=x ; i++) {
		iobj = (PyObject *)PyInt_FromLong(i);
		if (iobj == NULL)
			goto error;
		newresult = PyNumber_Multiply(result, iobj);
		Py_DECREF(iobj);
		if (newresult == NULL)
			goto error;
		Py_DECREF(result);
		result = newresult;
	}
	return result;

error:
	Py_DECREF(result);
	return NULL;
}

(Noter le goto).

Comme vous pouvez le constater, ils ne sont vraiment pas foulés, c'est juste une bête boucle qui fait le produit des entiers consécutifs (lignes 28 à 38), aucune optimisation de calcul. La version de gmpy est sans doute plus efficace.

Anonyme

7 septembre 2009 à 6:52:34

Citation

aucune optimisation de calcul

Que veux-tu dire?

Que proposes-tu pour l'optimisation?

Citation

La version de gmpy est sans doute plus efficace

sans doute? Pour comparer il faudrait le code.

Et puis qu'est-ce qui doit être plus efficace dans une factorielle?

candide

7 septembre 2009 à 9:22:20

Citation : fred1599

Citation

aucune optimisation de calcul

Que veux-tu dire?

Ils n'ont pas essayé de rendre la calcul efficace, ils ont fait l'algorithme naïf. Cela m'a d'autant plus surpris que les fonctions du module math sont censées être bien optimisées (elles émulent celles de la lib standard du C).

Citation : fred1599

Que proposes-tu pour l'optimisation?

Je n'ai rien à proposer, si tu achètes une voiture qui consomme trop et que tu le signales au constructeur, tu trouverais normal qu'il te demande quelle solutions techniques tu lui proposes pour faire baisser la consommation ?

Sinon, il existe des optimisations simples basées sur une décomposition en facteurs premiers puis une exponentiation rapide.

Citation : fred1599

Citation

La version de gmpy est sans doute plus efficace

sans doute? Pour comparer il faudrait le code.

Même pas la peine, tu lis la doc de GMP et ils expliquent qu'ils ont optimisé le calcul.

Citation : fred1599

Et puis qu'est-ce qui doit être plus efficace dans une factorielle?

Ben le temps de calcul de la factorielle, rien que pour N=50000, regarde ce que ça donne :

import time
from gmpy import fac

def f(n):
    p=1
    for i in range(1,n+1):
        p*=i
    return p

def test(f,n):
    t0 = time.clock()
    z=f(n)
    # print z
    t1 = time.clock()
    print "%.3f" % (t1-t0), "CPU seconds"

n=50000
test(f,n)
test(fac,n)

13.690 CPU seconds
0.080 CPU seconds

J'ai vérifié la concordance des résultats en les envoyant dans un fichier.

Cacophrene

7 septembre 2009 à 9:56:25

Bonjour !

En fait, la bibliothèque GMP procède de la façon suivante :

1. Énumérer les multiplications à effectuer. Par exemple 2 * 3 * 4 * 5 pour 5!
2. Regrouper les puissances de 2 : 2 * 3 * ( 2 * 2) * 5 * 6 = 2³ * 3 * 5
3. Regrouper les groupes qui apparaissent plusieurs fois (aucun dans mon exemple).
4. Calculer la factorielle : 8 * 3 * 5 = 24 * 5 = 120

Partant de là, la comparaison de ces deux méthodes très différentes doit donner des performances très différentes, et il n'y a pas lieu de s'en étonner. Par contre il peut être intéressant de réécrire l'algo optimisé en Python pur pour voir quelles performances on peut espérer.

Cordialement,
Cacophrène

delroth

7 septembre 2009 à 9:57:04

C'est cool, vous avez même plus besoin de moi pour lancer des trolls ridicules sur les performances d'une factorielle \o/ .

candide

7 septembre 2009 à 13:43:26

Citation : Cacophrene

Bonjour !

En fait, la bibliothèque GMP procède de la façon suivante :

1. Énumérer les multiplications à effectuer. Par exemple 2 * 3 * 4 * 5 pour 5!
2. Regrouper les puissances de 2 : 2 * 3 * ( 2 * 2) * 5 * 6 = 2³ * 3 * 5
3. Regrouper les groupes qui apparaissent plusieurs fois (aucun dans mon exemple).
4. Calculer la factorielle : 8 * 3 * 5 = 24 * 5 = 120

T'es sûr que c'est aussi simple que ça, je viens de regarder le code source (fac_ui.c), il y a bien ce que tu dis mais il y a d'autres choses.

Cacophrene

7 septembre 2009 à 16:51:42

Salut !

Citation : candide

T'es sûr que c'est aussi simple que ça, je viens de regarder le code source (fac_ui.c), il y a bien ce que tu dis mais il y a d'autres choses.

C'est une première idée d'optimisation, facile à comprendre et à reproduire dans un autre langage. Il est évident qu'avec presque 300 lignes de code, l'implémentation de la factorielle dans GMP n'est pas aussi simple que ça.

Cordialement,
Cacophrène