Accélérer le fonctionnement de la boucle en R

Question

J'ai un gros problème de performance dans R. J'ai écrit une fonction qui itère sur un objet data.frame. Elle ajoute simplement une nouvelle colonne à un data.frame et accumule qqch. (opération simple). Le data.frame contient environ 850 000 lignes. Mon PC fonctionne encore depuis environ 10 heures et je n'ai aucune idée de la durée d'exécution.

dayloop2 <- function(temp){
    for (i in 1:nrow(temp)){    
        temp[i,10] <- i
        if (i > 1) {             
            if ((temp[i,6] == temp[i-1,6]) & (temp[i,3] == temp[i-1,3])) { 
                temp[i,10] <- temp[i,9] + temp[i-1,10]                    
            } else {
                temp[i,10] <- temp[i,9]                                    
            }
        } else {
            temp[i,10] <- temp[i,9]
        }
    }
    names(temp)[names(temp) == "V10"] <- "Kumm."
    return(temp)
}

Une idée pour accélérer cette opération ?

Answer 1

Le plus gros problème et la racine de l'inefficacité est l'indexation de data.frame, je veux dire toutes ces lignes où vous utilisez temp[,] .
Essayez d'éviter cela autant que possible. J'ai pris votre fonction, modifié l'indexation et ici version_A

dayloop2_A <- function(temp){
    res <- numeric(nrow(temp))
    for (i in 1:nrow(temp)){    
        res[i] <- i
        if (i > 1) {             
            if ((temp[i,6] == temp[i-1,6]) & (temp[i,3] == temp[i-1,3])) { 
                res[i] <- temp[i,9] + res[i-1]                   
            } else {
                res[i] <- temp[i,9]                                    
            }
        } else {
            res[i] <- temp[i,9]
        }
    }
    temp$`Kumm.` <- res
    return(temp)
}

Comme vous pouvez le voir, je crée un vecteur res qui recueillent des résultats. À la fin, je l'ajoute à data.frame et je n'ai pas besoin de m'embêter avec les noms. Alors, en quoi c'est mieux ?

J'exécute chaque fonction pour data.frame avec nrow de 1 000 à 10 000 par 1 000 et mesure le temps avec system.time

X <- as.data.frame(matrix(sample(1:10, n*9, TRUE), n, 9))
system.time(dayloop2(X))

Le résultat est

Vous pouvez voir que votre version dépend de manière exponentielle de nrow(X) . La version modifiée a une relation linéaire, et simple lm prévoit que pour 850 000 lignes, le calcul prend 6 minutes et 10 secondes.

La puissance de la vectorisation

Comme Shane et Calimo le disent dans leurs réponses, la vectorisation est une clé pour de meilleures performances. A partir de votre code, vous pourriez vous déplacer en dehors de la boucle :

• conditionnement
• initialisation des résultats (qui sont temp[i,9] )

Cela conduit à ce code

dayloop2_B <- function(temp){
    cond <- c(FALSE, (temp[-nrow(temp),6] == temp[-1,6]) & (temp[-nrow(temp),3] == temp[-1,3]))
    res <- temp[,9]
    for (i in 1:nrow(temp)) {
        if (cond[i]) res[i] <- temp[i,9] + res[i-1]
    }
    temp$`Kumm.` <- res
    return(temp)
}

Comparez le résultat pour ces fonctions, cette fois pour nrow de 10.000 à 100.000 par 10.000.

Accorder l'accordéon

Une autre modification consiste à changer dans une boucle d'indexation temp[i,9] à res[i] (qui sont exactement les mêmes dans la i-ème itération de la boucle). C'est encore une fois la différence entre l'indexation d'un vecteur et l'indexation d'un objet data.frame .
Deuxièmement, lorsque vous regardez la boucle, vous pouvez voir qu'il n'y a pas besoin de boucler sur tous les éléments de l'échantillon. i mais seulement pour ceux qui sont en bonne condition.
Donc, nous y voilà

dayloop2_D <- function(temp){
    cond <- c(FALSE, (temp[-nrow(temp),6] == temp[-1,6]) & (temp[-nrow(temp),3] == temp[-1,3]))
    res <- temp[,9]
    for (i in (1:nrow(temp))[cond]) {
        res[i] <- res[i] + res[i-1]
    }
    temp$`Kumm.` <- res
    return(temp)
}

Les performances que vous obtenez dépendent fortement d'une structure de données. Précisément - sur le pourcentage de TRUE dans la condition. Pour mes données simulées, le temps de calcul pour 850 000 lignes est inférieur à une seconde.

Si vous voulez, vous pouvez aller plus loin, je vois au moins deux choses qui peuvent être faites :

• écrire un C code pour faire un cumul conditionnel

• si vous savez que dans vos données la séquence maximale n'est pas grande, vous pouvez changer la boucle en un while vectorisé, quelque chose comme

  while (any(cond)) {
      indx <- c(FALSE, cond[-1] & !cond[-n])
      res[indx] <- res[indx] + res[which(indx)-1]
      cond[indx] <- FALSE
  }

Answer 2

Stratégies générales pour accélérer le code R

D'abord, déterminez où la partie lente est vraiment. Il n'est pas nécessaire d'optimiser du code qui ne s'exécute pas lentement. Pour de petites quantités de code, il suffit d'y réfléchir. Si cela échoue, RProf et les outils de profilage similaires peuvent être utiles.

Une fois que vous avez trouvé le goulot d'étranglement, pensez à des algorithmes plus efficaces pour faire ce que vous voulez. Les calculs ne doivent être exécutés qu'une seule fois si possible, par exemple :

• Stocker les résultats et y accéder plutôt que de les recalculer à plusieurs reprises.
• Sortir les calculs non dépendants des boucles des boucles
• Évitez les calculs qui ne sont pas nécessaires (par ex. n'utilisez pas d'expressions régulières avec des recherches fixes. )

Utiliser plus fonctions efficaces peut produire des gains de vitesse modérés ou importants. Par exemple, paste0 produit un petit gain d'efficacité mais .colSums() et ses proches produisent des gains un peu plus prononcés. mean est particulièrement lent .

Vous pourrez ainsi éviter certains problèmes particulièrement problèmes communs :

• cbind vous ralentira très rapidement.
• Initialisez vos structures de données, puis remplissez-les, plutôt que de les étendre à chaque chaque fois .
• Même avec la préaffectation, vous pourriez passer à une approche par référence plutôt qu'à une approche par valeur, mais cela ne vaut peut-être pas la peine.
• Jetez un coup d'œil à la R Inferno pour d'autres pièges à éviter.

Essayez de vous améliorer vectorisation ce qui peut souvent, mais pas toujours, aider. À cet égard, les commandes intrinsèquement vectorielles telles que ifelse , diff et d'autres éléments similaires apporteront davantage d'améliorations que le système de gestion de la qualité de l'eau. apply (qui n'offrent que peu ou pas de gain de vitesse par rapport à une boucle bien écrite).

Vous pouvez également essayer de fournir plus d'informations aux fonctions R . Par exemple, utilisez vapply plutôt que sapply et préciser colClasses lors de la lecture de données en format texte . Les gains de vitesse seront variables en fonction de la quantité de supposition que vous éliminez.

Ensuite, considérez paquets optimisés : Le site data.table peut produire des gains de vitesse massifs là où son utilisation est possible. Si votre goulot d'étranglement semble être la lecture de grandes quantités de données, sqldf peut vous aider. Ou, le nouveau fread sur data.table .

Ensuite, essayez de gagner en vitesse grâce à un moyen plus efficace d'appeler R :

• Compilez votre script R. Ou utilisez l'outil Ra et jit de concert pour une compilation juste à temps (Dirk a un exemple dans cette présentation ).
• Assurez-vous que vous utilisez un BLAS optimisé. Celles-ci offrent des gains de vitesse généralisés. Honnêtement, c'est une honte que R n'utilise pas automatiquement la bibliothèque la plus efficace à l'installation. Espérons que Revolution R fera profiter l'ensemble de la communauté du travail qu'elle a réalisé ici.
• Radford Neal a réalisé un grand nombre d'optimisations, dont certaines ont été adoptées dans R Core, et beaucoup d'autres ont été transférées dans le programme pqR .

Enfin, si tout ce qui précède ne vous permet toujours pas d'obtenir la rapidité dont vous avez besoin, vous devrez peut-être opter pour une un langage plus rapide pour un extrait de code lent . La combinaison de Rcpp et inline ici, il est particulièrement facile de remplacer uniquement la partie la plus lente de l'algorithme par du code C++. Voici, par exemple ma première tentative de le faire et il surpasse même les solutions R hautement optimisées.

Si vous avez encore des problèmes après tout cela, vous avez simplement besoin de plus de puissance de calcul. Regardez dans parallélisation ( http://cran.r-project.org/web/views/HighPerformanceComputing.html ) ou même des solutions basées sur le GPU ( gpu-tools ).

Liens vers d'autres orientations

• http://www.noamross.net/blog/2013/4/25/faster-talk.html

Answer 3

Si vous utilisez for boucles, vous êtes très probablement en train de coder R comme s'il s'agissait de C ou de Java ou autre chose. Le code R qui est correctement vectorisé est extrêmement rapide.

Prenez par exemple ces deux simples bouts de code pour générer une liste de 10 000 entiers en séquence :

Le premier exemple de code est la façon dont on coderait une boucle en utilisant un paradigme de codage traditionnel. Il faut 28 secondes pour compléter

system.time({
    a <- NULL
    for(i in 1:1e5)a[i] <- i
})
   user  system elapsed 
  28.36    0.07   28.61 

Vous pouvez obtenir une amélioration de près de 100 fois par la simple action de pré-allouer la mémoire :

system.time({
    a <- rep(1, 1e5)
    for(i in 1:1e5)a[i] <- i
})

   user  system elapsed 
   0.30    0.00    0.29 

Mais en utilisant l'opération vectorielle de la base R en utilisant l'opérateur deux-points : cette opération est pratiquement instantanée :

system.time(a <- 1:1e5)

   user  system elapsed 
      0       0       0

Answer 4

Cette opération pourrait être beaucoup plus rapide en sautant les boucles grâce à l'utilisation d'index ou d'imbrications. ifelse() déclarations.

idx <- 1:nrow(temp)
temp[,10] <- idx
idx1 <- c(FALSE, (temp[-nrow(temp),6] == temp[-1,6]) & (temp[-nrow(temp),3] == temp[-1,3]))
temp[idx1,10] <- temp[idx1,9] + temp[which(idx1)-1,10] 
temp[!idx1,10] <- temp[!idx1,9]    
temp[1,10] <- temp[1,9]
names(temp)[names(temp) == "V10"] <- "Kumm."

Answer 5

Comme Ari l'a mentionné à la fin de sa réponse, les Rcpp et inline les paquets rendent incroyablement facile la réalisation rapide de choses. Par exemple, essayez ceci inline (avertissement : non testé) :

body <- 'Rcpp::NumericMatrix nm(temp);
         int nrtemp = Rccp::as<int>(nrt);
         for (int i = 0; i < nrtemp; ++i) {
             temp(i, 9) = i
             if (i > 1) {
                 if ((temp(i, 5) == temp(i - 1, 5) && temp(i, 2) == temp(i - 1, 2) {
                     temp(i, 9) = temp(i, 8) + temp(i - 1, 9)
                 } else {
                     temp(i, 9) = temp(i, 8)
                 }
             } else {
                 temp(i, 9) = temp(i, 8)
             }
         return Rcpp::wrap(nm);
        '

settings <- getPlugin("Rcpp")
# settings$env$PKG_CXXFLAGS <- paste("-I", getwd(), sep="") if you want to inc files in wd
dayloop <- cxxfunction(signature(nrt="numeric", temp="numeric"), body-body,
    plugin="Rcpp", settings=settings, cppargs="-I/usr/include")

dayloop2 <- function(temp) {
    # extract a numeric matrix from temp, put it in tmp
    nc <- ncol(temp)
    nm <- dayloop(nc, temp)
    names(temp)[names(temp) == "V10"] <- "Kumm."
    return(temp)
}

Il existe une procédure similaire pour #include où vous passez juste un paramètre

inc <- '#include <header.h>

à la fonction cxxf, comme include=inc . Ce qui est vraiment génial, c'est qu'il fait tout le travail de liaison et de compilation pour vous, ce qui rend le prototypage très rapide.

Disclaimer : Je ne suis pas totalement sûr que la classe de tmp devrait être numérique et non pas matrice numérique ou autre chose. Mais je suis presque sûr.

Edit : si vous avez toujours besoin de plus de vitesse après cela, OpenMP est une installation de parallélisation bonne pour C++ . Je n'ai pas essayé de l'utiliser à partir de inline mais cela devrait fonctionner. L'idée serait, dans le cas de n cœurs, l'itération des boucles k être réalisée par k % n . Une introduction appropriée se trouve dans l'ouvrage de Matloff L'art de la programmation R disponible ici dans le chapitre 16, Recours au C .