Discussion :

[herve1729]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
}

[TimoP]

En plus court pendant la boucle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[herve1729]

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 ?

[TimoP]

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)

[herve1729]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[TimoP]

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.

[herve1729]

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.

[TimoP]

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…

[herve1729]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[TimoP]

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.

[herve1729]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[TimoP]

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