Pourquoi sont-boucles lent dans R?

Question

Je sais que les boucles sont lents, en R, et que je devrais essayer de faire les choses dans un vectorisées au lieu.

Mais, pourquoi? Pourquoi sont-boucles lent et apply est rapide? apply des appels de plusieurs sous-fonctions, qui ne semble pas rapide.

Mise à jour: je suis désolé, la question a été mal posé. J'étais confus de vectorisation avec apply. Ma question doit avoir été, "Pourquoi est-vectorisation plus vite?"

Answer 1

Il n'est pas toujours le cas que les boucles sont lents et apply est rapide. Il y a une belle discussion de cette en Mai 2008, à la question de la R de News:

Uwe Ligges et John Fox. R Bureau d'Aide: Comment puis-je éviter cette boucle ou le rendre plus rapide? R News, 8(1):46-50, Mai 2008.

Dans la section "Boucles!" (commençant à la page 48), ils disent:

Beaucoup de commentaires sur la R de l'état que l'utilisation de boucles est particulièrement mauvaise idée. Ce n'est pas nécessairement vrai. Dans certains cas, il est difficile d'écrire vectorisé code, ou vectorisé code peut consommer une grande quantité de mémoire.

Ils suggèrent en outre:

• Initialiser de nouveaux objets à la pleine longueur avant la boucle, plutôt que l'augmentation de leur taille à l'intérieur de la boucle.
• Ne pas faire les choses dans un la boucle peut être fait en dehors de la boucle.
• Ne pas éviter les boucles tout simplement par souci d'éviter les boucles.

Ils ont un exemple simple où un for boucle prend 1,3 sec, mais apply de manque de mémoire.

Answer 2

Des boucles de R sont lents pour la même raison un langage interprété est lent: toutes les l'opération porte autour d'un lot de bagages supplémentaires.

Regardez - R_execClosure en eval.c (c'est la fonction appelée pour appeler un fonction définie par l'utilisateur). C'est près de 100 lignes et effectue toutes sortes de des opérations, de créer un environnement pour l'exécution, l'attribution des arguments dans l'environnement, etc.

Pensez à combien se produit lorsque vous appelez une fonction en C (push args sur pile, de sauter, de la pop args).

C'est pourquoi vous obtenez timings comme ceux-ci (comme joran souligné dans le commentaire, ce n'est pas réellement apply qui est rapide; c'est l'interne de la boucle C en mean c'est d'être rapide. apply est juste ordinaire ancienne R code):

A = matrix(as.numeric(1:100000))

À l'aide d'une boucle: 0.342 secondes:

system.time({
    Sum = 0
    for (i in seq_along(A)) {
        Sum = Sum + A[[i]]
    }
    Sum
})

À l'aide de somme: unmeasurably petit:

sum(A)

C'est un peu déconcertant, car, asymptotiquement, la boucle est tout aussi bon en tant que sum; il n'y a aucune raison pratique, il doit être lente; il est juste de faire plus travail supplémentaire à chaque itération.

Donc prendre en compte:

# 0.370 seconds
system.time({
    I = 0
    while (I < 100000) {
        10
        I = I + 1
    }
})

# 0.743 seconds -- double the time just adding parentheses
system.time({
    I = 0
    while (I < 100000) {
        ((((((((((10))))))))))
        I = I + 1
    }
})

(Cet exemple a été découvert par Radford Neal)

Parce qu' ( dans R est un opérateur, et exige en fait une recherche de nom à chaque fois que vous l'utilisez:

> `(` = function(x) 2
> (3)
[1] 2

Ou, en général, interprété opérations (dans toutes les langues) ont plus d'étapes. Bien sûr, ces mesures fournissent des avantages: vous ne pouvez pas faire qu' ( truc en C.

Answer 3

La seule Réponse à la Question est posée; boucles sont pas ralentir si ce que vous devez faire est de parcourir un ensemble de données de l'exécution de certains de la fonction et que la fonction ou l'opération n'est pas vectorisé. Un for() boucle sera aussi rapide, en général, apply(), mais peut-être un peu plus lent qu'un lapply() appel. Le dernier point est bien couvert sur, par exemple dans cette Réponse, et s'applique si le code impliqués dans la mise en place et de fonctionnement de la boucle est une partie importante de l'ensemble de la charge de calcul de la boucle.

Pourquoi beaucoup de gens pensent, for() boucles sont lent, c'est parce qu'ils ont, par l'utilisateur, sont de l'écriture de mauvais code. En général (mais il existe plusieurs exceptions), si vous avez besoin pour développer/pousser un objet, cela va nécessiter la copie de sorte que vous avez à la fois la surcharge de copie et la croissance de l'objet. Ce n'est pas seulement limitée à boucles, mais si vous copiez/grandir à chaque itération d'une boucle, bien sûr, la boucle va être lent parce que vous êtes encourir beaucoup de copier/les opérations de croissance.

Le général idiome pour l'utilisation de for() boucles dans R, c'est que vous allouer du stockage dont vous avez besoin avant la boucle commence, et puis de remplir l'objet ainsi attribuées. Si vous suivez cet idiome, les boucles ne sera pas ralenti. C'est ce qu' apply() gère pour vous l', mais il est juste caché de la vue.

Bien sûr, si un vectorisées fonction existe pour l'opération de mise en œuvre avec l' for() boucle, ne pas le faire. De même, ne pas utiliser apply() etc si un vectorisées fonction existe (par exemple, apply(foo, 2, mean) est mieux effectuée par l'intermédiaire d' colMeans(foo)).

Answer 4

Juste a titre de comparaison (ne pas lire trop!): J'ai couru un (très) simple boucle for dans R et dans le code JavaScript de Chrome et IE 8. Notez que Chrome ne compilation en code natif, et R avec le compilateur paquet est compilé en bytecode.

# In R 2.13.1, this took 500 ms
f <- function() { sum<-0.5; for(i in 1:1000000) sum<-sum+i; sum }
system.time( f() )

# And the compiled version took 130 ms
library(compiler)
g <- cmpfun(f)
system.time( g() )

@Gavin Simpson: Btw, il a fallu 1162 ms dans S-Plus...

Et le "même" code JavaScript:

// In IE8, this took 282 ms
// In Chrome 14.0, this took 4 ms
function f() {
    var sum = 0.5;
    for(i=1; i<=1000000; ++i) sum = sum + i;
    return sum;
}

var start = new Date().getTime();
f();
time = new Date().getTime() - start;