Application récursive d'une fonction

Coucou,

je viens de faire ça, ça sert à calculer des listes de valeurs de fonctions
récursives. Par exemple, pour calculer les premiers termes de la suite de Fibonacci :

Code:

---

1 2 3 4 5 6 7

> recurse(X = c(1,1), FUN = sum, n = 2, times = 40) [1] 1 1 2 3 5 8 13 [8] 21 34 55 89 144 233 377 [15] 610 987 1597 2584 4181 6765 10946 [22] 17711 28657 46368 75025 121393 196418 317811 [29] 514229 832040 1346269 2178309 3524578 5702887 9227465 [36] 14930352 24157817 39088169 63245986 102334155 165580141 267914296

---

OK ? FUN est la fonction à appliquer, n est le nombre d'éléments à lui passer (ordre de récurrence de la suite), times est le nombre de fois où on doit le faire, et X est le vecteur avec lequel on démarre (de longueur >= n)...

Ma question est la suivante : je suis très surpris qu'un truc pareil n'existe pas dans R ; j'ai exploré toutes les variantes de apply (lapply, rapply, mapply, etc) et je n’ai rien trouvé. Quelqu'un a une idée ?

À part ça, si vous voyez une amélioration à suggérer à ce code, allez-y...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

recurse <- function(X, FUN, n, times) { l <- length(X); if(n > l) { stop("Pas assez de valeurs dans X pour démarrer."); } args <- X[(l-n+1):l]; for(i in 1:times) { nxt <- FUN(args); X <- c(X,nxt) args <- c( args[2:n], nxt); } return(X); }

---

En plus court pendant la boucle

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

recurse <- function(X, FUN, times, n=length(X)) { if(length(X)<n){stop('Pas assez de X');} for(i in 1:(times-n)) { X <- c(X,FUN(X[i:(i+n)])) } return(X); }   recurse(c(1,1),sum,2,10)

---

Oui, à quelques modulations près... (ta fonction ne fait pas la même chose que la mienne !).

J'ai préféré gérer le vecteur args à part parce que je supposais que ça irait plus vite que de l'extraire de X à chaque tour de boucle, mais après tout je n’en sais rien.

Bon, donc pas de variante de apply() à proposer ?

Il me semble bien que les deux fonctions font la même chose… Je l'ai testé avec ton exemple Fibonnaci, et ça fonctionne (avec moins d'instructions)

Tu as testé et tu obtiens la même chose ? Elle est bien bonne.

On va pas en faire une pendule, mais ça ne peut pas être la fonction que tu as postée ici que tu as testée et qui donne la même chose. Si je copie colle ton code j’obtiens

Code:

---

1 2 3

> recurse(c(1,1),sum,2,10) Erreur dans recurse(c(1, 1), sum, 2, 10) : Pas assez de X

---

C’est juste à cause de l’ordre des arguments.

Autre erreur nettement plus embêtante : de i à i+n il y a n+1 termes, et non n termes ; donc même en rectifiant le prototype ou l’ordre dans lequel on passe, les arguments, ça ne marche pas. On obtient par exemple

Code:

---

1 2 3 4 5

> recurse(c(1,1),sum,10,2) [1] 1 1 NA NA NA NA NA NA NA NA > recurse(c(1,1,1),sum,10,2) [1] 1 1 1 3 5 9 17 31 57 105 193

---

C’est vachement pas la même chose, n’est-ce-pas ?
Il faut par exemple remplacer

Code:

---

1 2	X[i:(i+n)]

---

par

Code:

---

1 2	X[i+0:(n-1)]

---

Une fois ces erreurs somme toute vénielles corrigées, ta fonction devient :

Code:

---

1 2 3 4 5 6 7 8 9 10

ta_recurse <- function(X, FUN, n=length(X), times) { if(length(X)<n){stop('Pas assez de X');} for(i in 1:(times-n)) { X <- c(X,FUN(X[i+0:(n-1)])) } return(X); }

---

Bon, et maintenant le résultat :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

> recurse(c(1,1),sum,2,10) -> A > recurse(A,sum,2,10) -> B > A [1] 1 1 2 3 5 8 13 21 34 55 89 144 > B [1] 1 1 2 3 5 8 13 21 34 55 89 144 [13] 233 377 610 987 1597 2584 4181 6765 10946 17711 > ta_recurse(c(1,1),sum,2,10) -> A > ta_recurse(A,sum,2,10) -> B > A [1] 1 1 2 3 5 8 13 21 34 55 > B [1] 1 1 2 3 5 8 13 21 34 55 2 3 5 8 13 21 34 55

---

Ce n’étaient ni la variante dans le prototype ni l’erreur sur le nombre d’arguments de FUN, faciles à corriger, qui me faisaient dire que nos fonctions ne faisaient pas la même chose, mais cette différence de comportement (assez facile à corriger elle aussi, c’est vrai : quelques modulations disais-je).

Enfin, je ne connais pas assez les tripes de R pour décider laquelle des deux variantes est la plus efficace ; mais ça n’est en tout cas pas le nombre d’instruction qui permet d’en décider...

Désolé pour les erreurs, j'ai effectivement posté la mauvaise version de la fonction.

Ceci dit, je maintiens que ma fonction fait ce que je lui demande, à savoir gérer une liste de 'times' éléments au final. La tienne génère 'times' + 'n' éléments, et c'est la qu'est la différence.

En corrigeant ça dans ma fonction, ce qui lui fait faire la même chose que la tienne, sur 10000 intérations, elle est plus rapide que la tienne, parce qu'elle se compose de moins d'instructions (1 minute 17 secondes 55 contre 1 minute 17 secondes 92). L'optimisation se fait pas avec le nez, ça se fait avec des mesures.

Ta fonction est plus rapide , et je t’en félicite, mais pas parce qu’elle à moins d’instructions... tout ça est lié à la façon dont ces instructions sont exécutées en interne.

Quant au fait que nos deux fonctions ne font pas la même chose, oui, c’est ce que je disais, merci de confirmer : la mienne rajoute times itérations à une suite existante.

Je maintiens que diminuer le nombre d'allocations permet de gager du temps… essaie de faire une fonction avec 3 lignes et une ou tu alloue 3000 variables, et fais la tourner 100000 fois, tu verras…

Du coup, dans la plupart des cas, diminuer le nombre d'instructions diminue le temps d'exécution. J'ai eu l'occasion de me pencher la dessus depuis que je fais des programmes qui tournent pendant plusieurs jours…

Décidément, quand tu annonces un résultat, il vaut mieux vérifier.

Code:

---

1 2 3 4 5 6 7

> system.time(recurse(c(1,1), sum, 2, 100000) -> A) utilisateur système écoulé 70.500 9.796 80.444 > system.time(ta_recurse(c(1,1), sum, 2, 100000) -> B) utilisateur système écoulé 73.997 9.217 83.340

---

Je crois qu’on va en rester là, je t’ai assez fait perdre de temps.

OK, le temps d'exécution n'est pas linéaire par rapport à la taille de la sortie.

Si tu faisais la même chose pour 10000 itérations, tu obtiendrais le même résultat. Et si tu le faisais pour moins, tu verrais que la différence atteint des ordres de 2/3.

J'apprécie beaucoup que tu mettes systématiquement mes compétences en question alors que j'essaie de travailler sur ton code, et j'apprécie surtout le ton absolument pas pédant avec lequel tu le fais. Bel esprit, je suis sûr que les gens vont accourir pour t'aider maintenant.

Du calme mon gars. C'est moi qui ai un ton pédant, là ?

As-tu bien lu ce que j’ai copié-collé ? Je ne pinaille pas sur la proportion de temps de différence, comme tu as l’air de le penser, mais sur quelle fonction est la plus rapide. C’est la première version qui est plus rapide, pas la tienne. Et c’est, comme tu le dis, vrai à d’autres tailles :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

> system.time(recurse(c(1,1), sum, 2, 1000) -> A) utilisateur système écoulé 0.016 0.000 0.017 > system.time(ta_recurse(c(1,1), sum, 2, 1000) -> B) utilisateur système écoulé 0.024 0.000 0.031 > system.time(recurse(c(1,1), sum, 2, 10000) -> A) utilisateur système écoulé 0.572 0.004 0.596 > system.time(ta_recurse(c(1,1), sum, 2, 10000) -> B) utilisateur système écoulé 0.644 0.008 0.651

---

Je n’en fais pas une affaire, mais quand tu cries que c’est mieux parce qu’il y a moins d’instructions, je dis : non, pas forcément.

Allez, rideau, cette fois, on a assez perdu de temps tous les deux.

Je n'ai pas inventé les données que je t'ai communiqué dans le premier message… ou il apparait que ma fonction corrigée était plus rapide que la tienne.

Bref, au fond je m'en tape un peu, j'ai mieux à faire que de travailler sur le code de quelqu'un qui ne montre pas le moindre signe de reconnaissance. Bonne soirée