Ici, nous allons à nouveau: ajout d'un élément à une liste, en R

Ajout d'éléments à une liste est très lent en faire un élément à la fois. Voir ces deux exemples:

Je vais garder le Result variable dans l'environnement mondial afin d'éviter les copies à l'évaluation de cadres et de raconter des R où le chercher avec .GlobalEnv$, pour éviter un aveugle de recherche avec <<-:

Result <- list()

AddItemNaive <- function(item)
{
    .GlobalEnv$Result[[length(.GlobalEnv$Result)+1]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemNaive(i))
#   user  system elapsed 
#  15.60    0.00   15.61 

Lent. Maintenant, nous allons essayer la deuxième approche:

Result <- list()

AddItemNaive2 <- function(item)
{
    .GlobalEnv$Result <- c(.GlobalEnv$Result, item)
}

system.time(for(i in seq_len(2e4)) AddItemNaive2(i))
#   user  system elapsed 
#  13.85    0.00   13.89

Encore lent.

Maintenant, nous allons essayer d'utiliser un environment, et la création de nouvelles variables à l'intérieur de cet environnement, au lieu d'ajouter des éléments à une liste. Le problème ici est que les variables doivent être nommées, donc je vais utiliser le compteur comme une chaîne de caractères pour un nom à chaque élément de "slot":

Counter <- 0
Result <- new.env()

AddItemEnvir <- function(item)
{
    .GlobalEnv$Counter <- .GlobalEnv$Counter + 1

    .GlobalEnv$Result[[as.character(.GlobalEnv$Counter)]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemEnvir(i))
#   user  system elapsed 
#   0.36    0.00    0.38 

Whoa beaucoup plus rapide. 🙂 C'est peut être un peu maladroit, mais il fonctionne.

Une dernière approche utilise une liste, mais au lieu d'augmenter sa taille un élément à la fois, il double la taille à chaque fois que la liste est complète. La taille de la liste est également conservée dans une variable, pour éviter tout ralentissement à l'aide de length:

Counter <- 0
Result <- list(NULL)
Size <- 1

AddItemDoubling <- function(item)
{
    if( .GlobalEnv$Counter == .GlobalEnv$Size )
    {
        length(.GlobalEnv$Result) <- .GlobalEnv$Size <- .GlobalEnv$Size * 2
    }

    .GlobalEnv$Counter <- .GlobalEnv$Counter + 1

    .GlobalEnv$Result[[.GlobalEnv$Counter]] <- item
}

system.time(for(i in seq_len(2e4)) AddItemDoubling(i))
#   user  system elapsed 
#   0.22    0.00    0.22

C'est encore plus rapide. Et aussi facile à un travail comme une liste.

Essayons de ces deux dernières solutions avec plus d'itérations:

Counter <- 0
Result <- new.env()

system.time(for(i in seq_len(1e5)) AddItemEnvir(i))
#   user  system elapsed 
#  27.72    0.06   27.83 


Counter <- 0
Result <- list(NULL)
Size <- 1

system.time(for(i in seq_len(1e5)) AddItemDoubling(i))
#   user  system elapsed 
#   9.26    0.00    9.32

Bien, la dernière est définitivement la voie à suivre.

Des opérations qui modifient la longueur d'une liste/vecteur dans la R toujours copier tous les éléments dans une nouvelle liste, et donc sera lente, en O(n). Le stockage dans un environnement O(1) mais a une plus grande constante de frais généraux. Pour un O(1) ajout et la comparaison d'un certain nombre d'approches, voir ma réponse à l'autre question à https://stackoverflow.com/a/32870310/264177.