¿Agregar un objeto a una lista en R en tiempo constante amortizado, O (1)?

245

Si tengo alguna lista R mylist, puede agregarle un elemento objde esta manera:

mylist[[length(mylist)+1]] <- obj

Pero seguramente hay una forma más compacta. Cuando era nuevo en R, intenté escribir lappend()así:

lappend <- function(lst, obj) {
    lst[[length(lst)+1]] <- obj
    return(lst)
}

pero, por supuesto, eso no funciona debido a la semántica de llamada por nombre de R ( lstse copia efectivamente en la llamada, por lo que los cambios lstno son visibles fuera del alcance de lappend(). Sé que puede hacer pirateo del entorno en una función de R para llegar fuera del alcance de su función y mutar el entorno de llamada, pero eso parece un gran martillo para escribir una función de adición simple.

¿Alguien puede sugerir una forma más hermosa de hacer esto? Puntos de bonificación si funciona tanto para vectores como para listas.

Mella
fuente
55
R tiene las características de datos inmutables que a menudo se encuentran en lenguajes funcionales, odio decir esto, pero creo que solo tienes que lidiar con eso. Tiene sus ventajas y desventajas
Dan
Cuando dices "llamar por nombre" realmente quieres decir "llamar por valor", ¿verdad?
Ken Williams
77
No, definitivamente no es llamada por valor, de lo contrario esto no sería un problema. R en realidad usa la llamada por necesidad ( en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need ).
Nick
44
Una buena idea es preasignar su vector / lista: N = 100 mylist = vector ('list', N) para (i en 1: N) {#mylist [[i]] = ...} Evite 'crecer 'objetos en R.
Fernando
Accidentalmente encontré la respuesta aquí, stackoverflow.com/questions/17046336/… ¡ Tan difícil de implementar un algoritmo tan fácil!
KH Kim

Respuestas:

255

Si es una lista de cadenas, simplemente use la c()función:

R> LL <- list(a="tom", b="dick")
R> c(LL, c="harry")
$a
[1] "tom"

$b
[1] "dick"

$c
[1] "harry"

R> class(LL)
[1] "list"
R> 

Eso también funciona en vectores, así que ¿obtengo los puntos de bonificación?

Editar (2015-Feb-01): esta publicación se acerca en su quinto cumpleaños. Algunos lectores amables siguen repitiendo cualquier deficiencia con él, por lo que también deben ver algunos de los comentarios a continuación. Una sugerencia para los listtipos:

newlist <- list(oldlist, list(someobj))

En general, los tipos R pueden dificultar tener un solo idioma para todos los tipos y usos.

Dirk Eddelbuettel
fuente
19
Esto no se agrega ... se concatena. LLaún tendría dos elementos después de que C(LL, c="harry")se llame.
Nick
27
Sólo reasignar a LL: LL <- c(LL, c="harry").
Dirk Eddelbuettel
51
Esto solo funciona con cadenas. Si a, byc son vectores enteros, el comportamiento es completamente diferente.
Alexandre Rademaker
8
@Dirk: Usted tiene los padres anidados de manera diferente que yo. Mi llamado a c()tiene 2 argumentos: la lista a la que estoy tratando de agregar, a saber list(a=3, b=c(4, 5)), y el elemento que estoy tratando de agregar, a saber c=c(6, 7). Si usa mi enfoque, verá que se añaden 2 elementos de la lista ( 6y 7, con nombres c1y c2) en lugar de un solo vector de 2 elementos con el nombre cclaramente indicado.
j_random_hacker
77
Entonces, ¿es la conclusión mylist <- list(mylist, list(obj))? En caso afirmativo, sería bueno modificar la respuesta
Mateo
96

El OP (en la revisión actualizada de la pregunta de abril de 2012) está interesado en saber si hay una manera de agregar a una lista en tiempo constante amortizado, como se puede hacer, por ejemplo, con un vector<>contenedor C ++ . La mejor respuesta (s) aquí hasta ahora solo muestra los tiempos de ejecución relativos para varias soluciones dado un problema de tamaño fijo, pero no aborda directamente la eficiencia algorítmica de ninguna de las soluciones . Los comentarios debajo de muchas de las respuestas discuten la eficiencia algorítmica de algunas de las soluciones, pero en todos los casos hasta la fecha (a partir de abril de 2015) llegan a una conclusión incorrecta.

La eficiencia algorítmica captura las características de crecimiento, ya sea en tiempo (tiempo de ejecución) o espacio (cantidad de memoria consumida) a medida que crece el tamaño del problema . La ejecución de una prueba de rendimiento para varias soluciones dado un problema de tamaño fijo no aborda la tasa de crecimiento de las diferentes soluciones. El OP está interesado en saber si hay una manera de agregar objetos a una lista R en "tiempo constante amortizado". Qué significa eso? Para explicar, primero déjame describir el "tiempo constante":

  • Crecimiento constante u O (1) :

    Si el tiempo requerido para realizar una tarea determinada sigue siendo el mismo que el tamaño del problema se duplica , entonces decimos que el algoritmo exhibe un crecimiento de tiempo constante , o establecido en la notación "Big O", exhibe un crecimiento de tiempo O (1). Cuando el OP dice tiempo constante "amortizado", simplemente quiere decir "a largo plazo" ... es decir, si realizar una sola operación ocasionalmente lleva mucho más tiempo de lo normal (por ejemplo, si un búfer preasignado se agota y ocasionalmente requiere cambiar el tamaño a un tamaño mayor tamaño del búfer), siempre que el rendimiento promedio a largo plazo sea un tiempo constante, todavía lo llamaremos O (1).

    A modo de comparación, también describiré "tiempo lineal" y "tiempo cuadrático":

  • Crecimiento lineal u O (n) :

    Si el tiempo requerido para realizar una tarea dada dobles como el tamaño de los problemas dobles , entonces decimos las exposiciones algoritmo lineal de tiempo , o O (n) el crecimiento.

  • Crecimiento cuadrático u O (n 2 ) :

    Si el tiempo requerido para realizar una tarea determinada aumenta al cuadrado del tamaño del problema , les decimos que el algoritmo exhibe un tiempo cuadrático o un crecimiento de O (n 2 ) .

Hay muchas otras clases de algoritmos de eficiencia; Me remito al artículo de Wikipedia para mayor discusión.

Agradezco a @CronAcronis por su respuesta, ya que soy nuevo en R y fue bueno tener un bloque de código completamente construido para hacer un análisis de rendimiento de las diversas soluciones presentadas en esta página. Estoy tomando prestado su código para mi análisis, que duplico (envuelto en una función) a continuación:

library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 
runBenchmark <- function(n) {
    microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
    )
}

Los resultados publicados por @CronAcronis definitivamente parecen sugerir que el a <- list(a, list(i))método es más rápido, al menos para un tamaño de problema de 10000, pero los resultados para un tamaño de problema único no abordan el crecimiento de la solución. Para eso, necesitamos ejecutar un mínimo de dos pruebas de perfil, con diferentes tamaños de problemas:

> runBenchmark(2e+3)
Unit: microseconds
              expr       min        lq      mean    median       uq       max neval
    env_with_list_  8712.146  9138.250 10185.533 10257.678 10761.33 12058.264     5
                c_ 13407.657 13413.739 13620.976 13605.696 13790.05 13887.738     5
             list_   854.110   913.407  1064.463   914.167  1301.50  1339.132     5
          by_index 11656.866 11705.140 12182.104 11997.446 12741.70 12809.363     5
           append_ 15986.712 16817.635 17409.391 17458.502 17480.55 19303.560     5
 env_as_container_ 19777.559 20401.702 20589.856 20606.961 20939.56 21223.502     5
> runBenchmark(2e+4)
Unit: milliseconds
              expr         min         lq        mean    median          uq         max neval
    env_with_list_  534.955014  550.57150  550.329366  553.5288  553.955246  558.636313     5
                c_ 1448.014870 1536.78905 1527.104276 1545.6449 1546.462877 1558.609706     5
             list_    8.746356    8.79615    9.162577    8.8315    9.601226    9.837655     5
          by_index  953.989076 1038.47864 1037.859367 1064.3942 1065.291678 1067.143200     5
           append_ 1634.151839 1682.94746 1681.948374 1689.7598 1696.198890 1706.683874     5
 env_as_container_  204.134468  205.35348  208.011525  206.4490  208.279580  215.841129     5
> 

En primer lugar, una palabra sobre los valores min / lq / mean / median / uq / max: dado que estamos realizando exactamente la misma tarea para cada una de las 5 ejecuciones, en un mundo ideal, podríamos esperar que tomaría exactamente lo mismo cantidad de tiempo para cada carrera. Pero la primera ejecución normalmente está sesgada hacia tiempos más largos debido al hecho de que el código que estamos probando aún no está cargado en la memoria caché de la CPU. Después de la primera ejecución, esperaríamos que los tiempos sean bastante consistentes, pero ocasionalmente nuestro código puede ser desalojado de la caché debido a interrupciones de temporizador u otras interrupciones de hardware que no están relacionadas con el código que estamos probando. Al probar los fragmentos de código 5 veces, permitimos que el código se cargue en el caché durante la primera ejecución y luego le damos a cada fragmento 4 posibilidades de ejecutarse hasta su finalización sin interferencia de eventos externos. Por esta razón,

Tenga en cuenta que elegí ejecutar primero con un tamaño de problema de 2000 y luego de 20000, por lo que el tamaño de mi problema aumentó en un factor de 10 de la primera ejecución a la segunda.

Rendimiento de la listsolución: O (1) (tiempo constante)

Primero veamos el crecimiento de la listsolución, ya que podemos decir de inmediato que es la solución más rápida en ambas ejecuciones de creación de perfiles: en la primera ejecución, se necesitaron 854 microsegundos (0.854 milisegundos ) para realizar 2000 tareas de "agregar". En la segunda ejecución, se necesitaron 8.746 milisegundos para realizar 20000 tareas de "agregar". Un observador ingenuo diría: "Ah, la listsolución muestra un crecimiento de O (n), ya que a medida que el tamaño del problema creció en un factor de diez, también lo hizo el tiempo requerido para ejecutar la prueba". El problema con ese análisis es que lo que quiere el OP es la tasa de crecimiento de la inserción de un solo objeto , no la tasa de crecimiento del problema general. Sabiendo eso, está claro que ellist La solución proporciona exactamente lo que quiere el OP: un método para agregar objetos a una lista en O (1) tiempo.

Rendimiento de las otras soluciones.

Ninguna de las otras soluciones se acerca a la velocidad de la listsolución, pero es informativo examinarlas de todos modos:

La mayoría de las otras soluciones parecen ser O (n) en rendimiento. Por ejemplo, la by_indexsolución, una solución muy popular basada en la frecuencia con la que la encuentro en otras publicaciones de SO, tardó 11,6 milisegundos en agregar 2000 objetos y 953 milisegundos en agregar diez veces esa cantidad de objetos. El tiempo general del problema aumentó en un factor de 100, por lo que un observador ingenuo podría decir "Ah, la by_indexsolución muestra un crecimiento de O (n 2 ), ya que a medida que el tamaño del problema aumentó en un factor de diez, el tiempo requerido para ejecutar la prueba aumentó por un factor de 100 ".Como antes, este análisis es defectuoso, ya que el OP está interesado en el crecimiento de una inserción de un solo objeto. Si dividimos el crecimiento del tiempo general por el crecimiento del tamaño del problema, encontramos que el crecimiento del tiempo de los objetos anexos aumentó en un factor de solo 10, no un factor de 100, que coincide con el crecimiento del tamaño del problema, por lo que la by_indexsolución es O (norte). No hay soluciones enumeradas que exhiban un crecimiento de O (n 2 ) para agregar un solo objeto.

etiqueta de teléfono
fuente
1
Para el lector: Por favor lea la respuesta de JanKanis, que proporciona una extensión muy práctico para mis hallazgos anteriormente, y se sumerge un poco en la sobrecarga de diversas soluciones dado el funcionamiento interno de la implementación en C de R.
phonetagger
44
No estoy seguro de que la opción de lista implemente lo que se requiere:> length (c (c (c (list (1)), list (2)), list (3))) [1] 3> length (list (list (list (lista (1)), lista (2)), lista (3))) [1] 2. Se parece más a las listas anidadas.
Picarus el
@Picarus - Creo que tienes razón. Ya no estoy trabajando con R, pero afortunadamente JanKanis publicó una respuesta con una solución O (1) mucho más útil y toma nota del problema que identificó. Estoy seguro de que JanKanis apreciará tu voto a favor.
phonetagger
@ phonetagger, deberías editar tu respuesta. No todos leerán todas las respuestas.
Picarus el
"ni una sola respuesta ha abordado la pregunta real" -> El problema es que la pregunta original no era sobre la complejidad del algoritmo, eche un vistazo a las ediciones de la pregunta. El OP preguntó primero cómo agregar un elemento en una lista, que, varios meses después, cambió la pregunta.
Carlos Cinelli
41

En las otras respuestas, solo el listenfoque da como resultado O (1), pero da como resultado una estructura de lista profundamente anidada, y no una lista simple. He utilizado las siguientes estructuras de datos, admiten los anexos O (1) (amortizados) y permiten que el resultado se convierta de nuevo en una lista simple.

expandingList <- function(capacity = 10) {
    buffer <- vector('list', capacity)
    length <- 0

    methods <- list()

    methods$double.size <- function() {
        buffer <<- c(buffer, vector('list', capacity))
        capacity <<- capacity * 2
    }

    methods$add <- function(val) {
        if(length == capacity) {
            methods$double.size()
        }

        length <<- length + 1
        buffer[[length]] <<- val
    }

    methods$as.list <- function() {
        b <- buffer[0:length]
        return(b)
    }

    methods
}

y

linkedList <- function() {
    head <- list(0)
    length <- 0

    methods <- list()

    methods$add <- function(val) {
        length <<- length + 1
        head <<- list(head, val)
    }

    methods$as.list <- function() {
        b <- vector('list', length)
        h <- head
        for(i in length:1) {
            b[[i]] <- head[[2]]
            head <- head[[1]]
        }
        return(b)
    }
    methods
}

Úselos de la siguiente manera:

> l <- expandingList()
> l$add("hello")
> l$add("world")
> l$add(101)
> l$as.list()
[[1]]
[1] "hello"

[[2]]
[1] "world"

[[3]]
[1] 101

Estas soluciones podrían expandirse en objetos completos que admitan todas las operaciones relacionadas con la lista, pero eso seguirá siendo un ejercicio para el lector.

Otra variante para una lista con nombre:

namedExpandingList <- function(capacity = 10) {
    buffer <- vector('list', capacity)
    names <- character(capacity)
    length <- 0

    methods <- list()

    methods$double.size <- function() {
        buffer <<- c(buffer, vector('list', capacity))
        names <<- c(names, character(capacity))
        capacity <<- capacity * 2
    }

    methods$add <- function(name, val) {
        if(length == capacity) {
            methods$double.size()
        }

        length <<- length + 1
        buffer[[length]] <<- val
        names[length] <<- name
    }

    methods$as.list <- function() {
        b <- buffer[0:length]
        names(b) <- names[0:length]
        return(b)
    }

    methods
}

Puntos de referencia

Comparación de rendimiento utilizando el código de @ phonetagger (que se basa en el código de @Cron Arconis). También agregué un better_env_as_containery cambié env_as_container_un poco. El original env_as_container_estaba roto y en realidad no almacena todos los números.

library(microbenchmark)
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(lab)]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 
env2list <- function(env, len) {
    l <- vector('list', len)
    for (i in 1:len) {
        l[[i]] <- env[[as.character(i)]]
    }
    l
}
envl2list <- function(env, len) {
    l <- vector('list', len)
    for (i in 1:len) {
        l[[i]] <- env[[paste(as.character(i), 'L', sep='')]]
    }
    l
}
runBenchmark <- function(n) {
    microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(hash=TRUE, parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            envl2list(listptr, n)
        },
        better_env_as_container = {
            env <- new.env(hash=TRUE, parent=globalenv())
            for(i in 1:n) env[[as.character(i)]] <- i
            env2list(env, n)
        },
        linkedList = {
            a <- linkedList()
            for(i in 1:n) { a$add(i) }
            a$as.list()
        },
        inlineLinkedList = {
            a <- list()
            for(i in 1:n) { a <- list(a, i) }
            b <- vector('list', n)
            head <- a
            for(i in n:1) {
                b[[i]] <- head[[2]]
                head <- head[[1]]
            }                
        },
        expandingList = {
            a <- expandingList()
            for(i in 1:n) { a$add(i) }
            a$as.list()
        },
        inlineExpandingList = {
            l <- vector('list', 10)
            cap <- 10
            len <- 0
            for(i in 1:n) {
                if(len == cap) {
                    l <- c(l, vector('list', cap))
                    cap <- cap*2
                }
                len <- len + 1
                l[[len]] <- i
            }
            l[1:len]
        }
    )
}

# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
    expandingList <- function(capacity = 10) {
        buffer <- vector('list', capacity)
        length <- 0

        methods <- list()

        methods$double.size <- function() {
            buffer <<- c(buffer, vector('list', capacity))
            capacity <<- capacity * 2
        }

        methods$add <- function(val) {
            if(length == capacity) {
                methods$double.size()
            }

            length <<- length + 1
            buffer[[length]] <<- val
        }

        methods$as.list <- function() {
            b <- buffer[0:length]
            return(b)
        }

        methods
    }

    linkedList <- function() {
        head <- list(0)
        length <- 0

        methods <- list()

        methods$add <- function(val) {
            length <<- length + 1
            head <<- list(head, val)
        }

        methods$as.list <- function() {
            b <- vector('list', length)
            h <- head
            for(i in length:1) {
                b[[i]] <- head[[2]]
                head <- head[[1]]
            }
            return(b)
        }

        methods
    }

# We need to repeatedly add an element to a list. With normal list concatenation
# or element setting this would lead to a large number of memory copies and a
# quadratic runtime. To prevent that, this function implements a bare bones
# expanding array, in which list appends are (amortized) constant time.
    namedExpandingList <- function(capacity = 10) {
        buffer <- vector('list', capacity)
        names <- character(capacity)
        length <- 0

        methods <- list()

        methods$double.size <- function() {
            buffer <<- c(buffer, vector('list', capacity))
            names <<- c(names, character(capacity))
            capacity <<- capacity * 2
        }

        methods$add <- function(name, val) {
            if(length == capacity) {
                methods$double.size()
            }

            length <<- length + 1
            buffer[[length]] <<- val
            names[length] <<- name
        }

        methods$as.list <- function() {
            b <- buffer[0:length]
            names(b) <- names[0:length]
            return(b)
        }

        methods
    }

resultado:

> runBenchmark(1000)
Unit: microseconds
                    expr       min        lq      mean    median        uq       max neval
          env_with_list_  3128.291  3161.675  4466.726  3361.837  3362.885  9318.943     5
                      c_  3308.130  3465.830  6687.985  8578.913  8627.802  9459.252     5
                   list_   329.508   343.615   389.724   370.504   449.494   455.499     5
                by_index  3076.679  3256.588  5480.571  3395.919  8209.738  9463.931     5
                 append_  4292.321  4562.184  7911.882 10156.957 10202.773 10345.177     5
       env_as_container_ 24471.511 24795.849 25541.103 25486.362 26440.591 26511.200     5
 better_env_as_container  7671.338  7986.597  8118.163  8153.726  8335.659  8443.493     5
              linkedList  1700.754  1755.439  1829.442  1804.746  1898.752  1987.518     5
        inlineLinkedList  1109.764  1115.352  1163.751  1115.631  1206.843  1271.166     5
           expandingList  1422.440  1439.970  1486.288  1519.728  1524.268  1525.036     5
     inlineExpandingList   942.916   973.366  1002.461  1012.197  1017.784  1066.044     5
> runBenchmark(10000)
Unit: milliseconds
                    expr        min         lq       mean     median         uq        max neval
          env_with_list_ 357.760419 360.277117 433.810432 411.144799 479.090688 560.779139     5
                      c_ 685.477809 734.055635 761.689936 745.957553 778.330873 864.627811     5
                   list_   3.257356   3.454166   3.505653   3.524216   3.551454   3.741071     5
                by_index 445.977967 454.321797 515.453906 483.313516 560.374763 633.281485     5
                 append_ 610.777866 629.547539 681.145751 640.936898 760.570326 763.896124     5
       env_as_container_ 281.025606 290.028380 303.885130 308.594676 314.972570 324.804419     5
 better_env_as_container  83.944855  86.927458  90.098644  91.335853  92.459026  95.826030     5
              linkedList  19.612576  24.032285  24.229808  25.461429  25.819151  26.223597     5
        inlineLinkedList  11.126970  11.768524  12.216284  12.063529  12.392199  13.730200     5
           expandingList  14.735483  15.854536  15.764204  16.073485  16.075789  16.081726     5
     inlineExpandingList  10.618393  11.179351  13.275107  12.391780  14.747914  17.438096     5
> runBenchmark(20000)
Unit: milliseconds
                    expr         min          lq       mean      median          uq         max neval
          env_with_list_ 1723.899913 1915.003237 1921.23955 1938.734718 1951.649113 2076.910767     5
                      c_ 2759.769353 2768.992334 2810.40023 2820.129738 2832.350269 2870.759474     5
                   list_    6.112919    6.399964    6.63974    6.453252    6.910916    7.321647     5
                by_index 2163.585192 2194.892470 2292.61011 2209.889015 2436.620081 2458.063801     5
                 append_ 2832.504964 2872.559609 2983.17666 2992.634568 3004.625953 3213.558197     5
       env_as_container_  573.386166  588.448990  602.48829  597.645221  610.048314  642.912752     5
 better_env_as_container  154.180531  175.254307  180.26689  177.027204  188.642219  206.230191     5
              linkedList   38.401105   47.514506   46.61419   47.525192   48.677209   50.952958     5
        inlineLinkedList   25.172429   26.326681   32.33312   34.403442   34.469930   41.293126     5
           expandingList   30.776072   30.970438   34.45491   31.752790   38.062728   40.712542     5
     inlineExpandingList   21.309278   22.709159   24.64656   24.290694   25.764816   29.158849     5

He agregado linkedListy expandingListuna versión en línea de ambos. El inlinedLinkedListes básicamente una copia list_, sino que también convierte la parte de atrás estructura anidada en una lista simple. Más allá de eso, la diferencia entre las versiones en línea y no en línea se debe a la sobrecarga de las llamadas a funciones.

Todas las variantes de expandingListy linkedListmuestran O (1) agregan rendimiento, con el tiempo de referencia escalando linealmente con el número de elementos agregados. linkedListes más lento que expandingList, y la sobrecarga de la llamada a la función también es visible. Entonces, si realmente necesita toda la velocidad que puede obtener (y desea apegarse al código R), use una versión en línea de expandingList.

También he echado un vistazo a la implementación C de R, y ambos enfoques deben ser O (1) agregar para cualquier tamaño hasta que se quede sin memoria.

También he cambiado env_as_container_, la versión original almacenaría cada elemento en el índice "i", sobrescribiendo el elemento adjunto anteriormente. El better_env_as_containerque he agregado es muy similar env_as_container_pero sin las deparsecosas. Ambos exhiben un rendimiento O (1), pero tienen una sobrecarga que es bastante mayor que las listas vinculadas / expandidas.

Sobrecarga de memoria

En la implementación de CR hay una sobrecarga de 4 palabras y 2 entradas por objeto asignado. El linkedListenfoque asigna una lista de longitud dos por apéndice, para un total de (4 * 8 + 4 + 4 + 2 * 8 =) 56 bytes por elemento agregado en computadoras de 64 bits (excluyendo la sobrecarga de asignación de memoria, por lo que probablemente esté más cerca de 64 bytes). El expandingListenfoque utiliza una palabra por elemento adjunto, más una copia al duplicar la longitud del vector, por lo que un uso de memoria total de hasta 16 bytes por elemento. Como la memoria está en uno o dos objetos, la sobrecarga por objeto es insignificante. No he examinado profundamente el envuso de la memoria, pero creo que estará más cerca linkedList.

JanKanis
fuente
¿Cuál es el punto de mantener la opción de lista si no resuelve el problema que estamos tratando de resolver?
Picarus
1
@Picarus No estoy seguro de lo que quieres decir. ¿Por qué lo mantuve en el punto de referencia? Como comparación con las otras opciones. La list_opción es más rápida y podría ser útil si no necesita convertir a una lista normal, es decir, si utiliza el resultado como una pila.
JanKanis
@Gabor Csardi publicó una forma más rápida de convertir entornos a listas en una pregunta diferente en stackoverflow.com/a/29482211/264177. Lo comparé también en mi sistema. Es aproximadamente el doble de rápido better_env_as_container pero aún más lento que LinkedList y expandList.
JanKanis
Las listas profundamente anidadas (n = 99999) parecen manejables y tolerables para ciertas aplicaciones: ¿Alguien quiere comparar nestoR ? (Todavía soy un poco novato en las environmentcosas que utilicé para nestoR). Mi cuello de botella casi siempre es tiempo humano dedicado a codificar y hacer análisis de datos, pero aprecio los puntos de referencia que he encontrado en esta publicación. En cuanto a la sobrecarga de memoria, no me importaría hasta aproximadamente un KB por nodo para mis aplicaciones. Me aferro a grandes matrices, etc.
Ana Nimbus
17

En el Lisp lo hicimos de esta manera:

> l <- c(1)
> l <- c(2, l)
> l <- c(3, l)
> l <- rev(l)
> l
[1] 1 2 3

aunque era 'contras', no solo 'c'. Si necesita comenzar con una lista vacía, use l <- NULL.

Arsenio
fuente
3
¡Excelente! Todas las otras soluciones devuelven una lista extraña de listas.
metakermit
44
En Lisp, anteponer a una lista es una operación O (1), mientras que el anexo se ejecuta en O (n), @flies. La necesidad de reversión se ve compensada por la ganancia de rendimiento. Este no es el caso en R. Ni siquiera en la lista, que generalmente se parece más a las listas de listas.
Palec
@Palec "Este no es el caso en R" - No estoy seguro de a qué "esto" te refieres. ¿Estás diciendo que agregar no es O (1), o no es O (n)?
vuela
1
Estoy diciendo que si estuviera codificando en Lisp, su enfoque sería ineficiente, @flies. Ese comentario tenía la intención de explicar por qué la respuesta está escrita tal como está. En R, los dos enfoques están a la par en cuanto al rendimiento, AFAIK. Pero ahora no estoy seguro de la complejidad amortizada. No he tocado a R desde el momento en que se escribió mi comentario anterior.
Palec
3
En R, este enfoque será O (n). La c()función copia sus argumentos en un nuevo vector / lista y lo devuelve.
JanKanis
6

¿Quieres algo como esto quizás?

> push <- function(l, x) {
   lst <- get(l, parent.frame())
   lst[length(lst)+1] <- x
   assign(l, lst, envir=parent.frame())
 }
> a <- list(1,2)
> push('a', 6)
> a
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 6

No es una función muy educada (asignar parent.frame()es un poco grosero) pero IIUYC es lo que estás pidiendo.

Ken Williams
fuente
6

He hecho una pequeña comparación de los métodos mencionados aquí.

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj} 

microbenchmark(times = 5,  
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = { 
            a <- list(0)    
            for(i in 1:n) {a <- append(a, i)} 
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)} 
            listptr
        }   
)

Resultados:

Unit: milliseconds
              expr       min        lq       mean    median        uq       max neval cld
    env_with_list_  188.9023  198.7560  224.57632  223.2520  229.3854  282.5859     5  a 
                c_ 1275.3424 1869.1064 2022.20984 2191.7745 2283.1199 2491.7060     5   b
             list_   17.4916   18.1142   22.56752   19.8546   20.8191   36.5581     5  a 
          by_index  445.2970  479.9670  540.20398  576.9037  591.2366  607.6156     5  a 
           append_ 1140.8975 1316.3031 1794.10472 1620.1212 1855.3602 3037.8416     5   b
 env_as_container_  355.9655  360.1738  399.69186  376.8588  391.7945  513.6667     5  a 
Cron Merdek
fuente
Esta es una gran información: nunca habría adivinado que list = listno solo fueron el ganador, ¡sino de 1 a 2 órdenes o magnitud!
javadba
5

Si pasa la variable de lista como una cadena entre comillas, puede alcanzarla desde la función como:

push <- function(l, x) {
  assign(l, append(eval(as.name(l)), x), envir=parent.frame())
}

entonces:

> a <- list(1,2)
> a
[[1]]
[1] 1

[[2]]
[1] 2

> push("a", 3)
> a
[[1]]
[1] 1

[[2]]
[1] 2

[[3]]
[1] 3

> 

o por crédito extra:

> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
> 
ayman
fuente
1
Este es básicamente el comportamiento que quiero, sin embargo, todavía llama anexar internamente, lo que resulta en el rendimiento de O (n ^ 2).
Nick
4

No estoy seguro de por qué no crees que tu primer método no funcionará. Tiene un error en la función lappend: longitud (lista) debe ser longitud (lst). Esto funciona bien y devuelve una lista con el obj adjunto.

Pablo
fuente
3
Tienes toda la razón. Hubo un error en el código y lo solucioné. He probado lo lappend()que he proporcionado y parece funcionar tan bien como c () y append (), todos los cuales exhiben un comportamiento O (n ^ 2).
Nick
2

Creo que lo que quiere hacer es en realidad pasan por referencia (puntero) a la function-- crear un nuevo entorno (que se pasa por referencia a las funciones) con la lista añadido a la misma:

listptr=new.env(parent=globalenv())
listptr$list=mylist

#Then the function is modified as:
lPtrAppend <- function(lstptr, obj) {
    lstptr$list[[length(lstptr$list)+1]] <- obj
}

Ahora solo está modificando la lista existente (sin crear una nueva)

DavidM
fuente
1
Esto parece tener una complejidad de tiempo cuadrático nuevamente. El problema es obviamente que el cambio de tamaño de lista / vector no se implementa de la manera en que generalmente se implementa en la mayoría de los idiomas.
eold
Sí, parece que la adición al final es muy lenta, probablemente las listas b / c son recursivas, y R es mejor en operaciones de vectores en lugar de operaciones de tipo bucle. Es mucho mejor hacerlo:
DavidM
1
system.time (para (i in c (1: 10000) mylist [i] = i) (unos segundos), o mejor aún, hágalo todo en una sola operación: system.time (mylist = list (1: 100000)) (menos de un segundo), luego modificar esa lista preasignada con el bucle for también será más rápido.
DavidM
2

Esta es una forma sencilla de agregar elementos a una Lista R:

# create an empty list:
small_list = list()

# now put some objects in it:
small_list$k1 = "v1"
small_list$k2 = "v2"
small_list$k3 = 1:10

# retrieve them the same way:
small_list$k1
# returns "v1"

# "index" notation works as well:
small_list["k2"]

O programáticamente:

kx = paste(LETTERS[1:5], 1:5, sep="")
vx = runif(5)
lx = list()
cn = 1

for (itm in kx) { lx[itm] = vx[cn]; cn = cn + 1 }

print(length(lx))
# returns 5
Doug
fuente
Esto no es realmente atractivo. ¿Qué sucede si tengo 100 objetos y deseo agregarlos a una lista mediante programación? R tiene una append()función, pero en realidad es una función concatenada y solo funciona en vectores.
Nick
append()trabaja en vectores y listas, y es un verdadero modo de adición (que es básicamente el mismo que concatenar, así que no veo cuál es tu problema)
Hadley
8
Una función de agregar debe mutar un objeto existente, no crear uno nuevo. Un verdadero agregado no tendría un comportamiento O (N ^ 2).
Nick
2

De hecho, hay una subtelty con la c()función. Si lo haces:

x <- list()
x <- c(x,2)
x = c(x,"foo")

obtendrá lo esperado:

[[1]]
[1]

[[2]]
[1] "foo"

¡pero si agrega una matriz con x <- c(x, matrix(5,2,2), su lista tendrá otros 4 elementos de valor 5! Será mejor que hagas:

x <- c(x, list(matrix(5,2,2))

Funciona para cualquier otro objeto y obtendrá lo esperado:

[[1]]
[1]

[[2]]
[1] "foo"

[[3]]
     [,1] [,2]
[1,]    5    5
[2,]    5    5

Finalmente, tu función se convierte en:

push <- function(l, ...) c(l, list(...))

y funciona para cualquier tipo de objeto. Puedes ser más inteligente y hacer:

push_back <- function(l, ...) c(l, list(...))
push_front <- function(l, ...) c(list(...), l)
David Bellot
fuente
1

También hay list.appendde rlist( enlace a la documentación )

require(rlist)
LL <- list(a="Tom", b="Dick")
list.append(LL,d="Pam",f=c("Joe","Ann"))

Es muy simple y eficiente.

skan
fuente
1
no me parece R ... ¿Python?
JD Long
1
Hice una edición y la probé: es muy lento. Mejor use el método c()o list. Ambos son mucho más rápidos.
5
Buscando un código rlist::list.append(), es esencialmente una envoltura base::c().
nbenn
1

Para la validación ejecuté el código de referencia proporcionado por @Cron. Hay una diferencia importante (además de correr más rápido en el nuevo procesador i7): by_indexahora funciona casi tan bien como list_:

Unit: milliseconds
              expr        min         lq       mean     median         uq
    env_with_list_ 167.882406 175.969269 185.966143 181.817187 185.933887
                c_ 485.524870 501.049836 516.781689 518.637468 537.355953
             list_   6.155772   6.258487   6.544207   6.269045   6.290925
          by_index   9.290577   9.630283   9.881103   9.672359  10.219533
           append_ 505.046634 543.319857 542.112303 551.001787 553.030110
 env_as_container_ 153.297375 154.880337 156.198009 156.068736 156.800135

Como referencia, aquí está el código de referencia copiado literalmente de la respuesta de @ Cron (en caso de que luego cambie el contenido):

n = 1e+4
library(microbenchmark)
### Using environment as a container
lPtrAppend <- function(lstptr, lab, obj) {lstptr[[deparse(substitute(lab))]] <- obj}
### Store list inside new environment
envAppendList <- function(lstptr, obj) {lstptr$list[[length(lstptr$list)+1]] <- obj}

microbenchmark(times = 5,
        env_with_list_ = {
            listptr <- new.env(parent=globalenv())
            listptr$list <- NULL
            for(i in 1:n) {envAppendList(listptr, i)}
            listptr$list
        },
        c_ = {
            a <- list(0)
            for(i in 1:n) {a = c(a, list(i))}
        },
        list_ = {
            a <- list(0)
            for(i in 1:n) {a <- list(a, list(i))}
        },
        by_index = {
            a <- list(0)
            for(i in 1:n) {a[length(a) + 1] <- i}
            a
        },
        append_ = {
            a <- list(0)
            for(i in 1:n) {a <- append(a, i)}
            a
        },
        env_as_container_ = {
            listptr <- new.env(parent=globalenv())
            for(i in 1:n) {lPtrAppend(listptr, i, i)}
            listptr
        }
)
javadba
fuente
0
> LL<-list(1:4)

> LL

[[1]]
[1] 1 2 3 4

> LL<-list(c(unlist(LL),5:9))

> LL

[[1]]
 [1] 1 2 3 4 5 6 7 8 9
Soo Lee
fuente
2
No creo que este sea el tipo de anexo que estaba buscando el OP.
joran
Esto no es agregar elementos en una lista. Aquí está aumentando los elementos del vector entero, que es el único elemento de la lista. La lista tiene solo un elemento, un vector entero.
Sergio
0

Esta es una pregunta muy interesante y espero que mi pensamiento a continuación pueda contribuir a solucionarlo. Este método proporciona una lista plana sin indexar, pero tiene una lista y una lista para evitar las estructuras de anidación. No estoy seguro de la velocidad ya que no sé cómo compararla.

a_list<-list()
for(i in 1:3){
  a_list<-list(unlist(list(unlist(a_list,recursive = FALSE),list(rnorm(2))),recursive = FALSE))
}
a_list

[[1]]
[[1]][[1]]
[1] -0.8098202  1.1035517

[[1]][[2]]
[1] 0.6804520 0.4664394

[[1]][[3]]
[1] 0.15592354 0.07424637
xappppp
fuente
Lo que quiero agregar es que da una lista anidada de dos niveles, pero eso es todo. La forma en que funciona la lista y la anulación de la lista no me resulta muy clara, pero este es el resultado al probar el código
xappppp,
-1

mylist<-list(1,2,3) mylist<-c(mylist,list(5))

Entonces podemos agregar fácilmente el elemento / objeto usando el código anterior

saravanan saminathan
fuente