No estoy contento con la aceptación de la respuesta a la Añadir un objeto a una lista de R en amortizados constante de tiempo?

> list1 <- list("foo", pi)
> bar <- list("A", "B")

¿Cómo puedo anexar nuevo elemento bar a list1? Claramente, c() no funciona, se aplana bar:

> c(list1, bar)
[[1]]
[1] "foo"

[[2]]
[1] 3.141593

[[3]]
[1] "A"

[[4]]
[1] "B"

La asignación de índice de obras:

> list1[[length(list1)+1]] <- bar
> list1
[[1]]
[1] "foo"

[[2]]
[1] 3.141593

[[3]]
[[3]][[1]]
[1] "A"

[[3]][[2]]
[1] "B"

¿Cuál es la eficiencia de este método? Hay una forma más elegante?

  • c(list1,list(bar))? Por favor, utilice el paquete de microbenchmark de referencia de este mismo.
  • ¿Prefiere el rendimiento, la elegancia o un compromiso de ambos? Es de todos los datos conocidos a la cadena ser, o podría ser arbitrario? Por favor aclarar la pregunta del título y el texto en consecuencia.
  • Posibles duplicados de añadir un objeto a una lista de R en la amortizado de tiempo constante O(1)?
  • ¿Puede alguien decir por qué c() no funciona y aplanado de los valores?
  • porque semánticamente c() está sobrecargado. Se construye de vectores de elementos, y también por la concatenación de los vectores.
  • Te gustaría ser capaz de explicar siguiente comportamiento? Al anexar la lista c() se aplana, pero no durante la creación de la lista. un<-list(c(«hola, hola»),2) > [[1]] [1] «hola, hola» [[2]] [1] 2 append(a,c(«qué»,»ver»)) [[1]] [1] «hola, hola» [[2]] [1] 2 [[3]] [1] «¿» [[4]] [1] «ver»
  • No tiene nada que ver con c(), que se observa un comportamiento diferente entre list() y append(). ¿Puede explicar por qué te sorprendió?

InformationsquelleAutor user443854 | 2013-06-11

3 Comentarios

  1. 50

    La adición de elementos a una lista es muy lento cuando se trata de un elemento en un tiempo. Ver a estos dos ejemplos:

    Me quedo con la Result variable en el entorno global para evitar copias a la evaluación de los marcos y decirle R donde a buscarlo con .GlobalEnv$, para evitar una búsqueda ciega con <<-:

    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 

    Lento. Ahora vamos a tratar el segundo enfoque:

    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

    Todavía lento.

    Ahora vamos a tratar de usar un environment, y la creación de nuevas variables dentro de este entorno, en lugar de agregar elementos a una lista. El problema aquí es que las variables deben ser nombrado, así que voy a utilizar el contador como cadena de caracteres para el nombre de cada elemento de la «ranura»:

    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 mucho más rápido. 🙂 Puede ser un poco difícil de trabajar, pero funciona.

    Una aproximación final utiliza una lista, pero en lugar de aumentar su tamaño de un elemento en un tiempo, dobles el tamaño cada vez que la lista está completa. El tamaño de la lista se mantiene en una variable, para evitar cualquier desaceleración utilizando 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

    Es aún más rápido. Y tan fácil para un trabajo como cualquier lista.

    Vamos a tratar estas dos últimas soluciones con más iteraciones:

    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, el pasado es definitivamente el camino a seguir.

    • He probado el primer acercamiento con [[]] con diferente número de elementos: 2e3 se ejecuta 100 veces más rápida que 2e4, claramente O(N^2), por lo que la lista se va a copiar. Por otro lado, la asignación a nombre de variable diferente cada vez que toma alrededor de 20x tiempo para 2e5 elementos de comparación para 2e4 elementos, que es O(N) — el rendimiento que lo que yo esperaría de adición de un elemento a una lista.
    • La eliminación de .GlobalEnv$ hace que la función sea más rápido
    • que rompe el código, ver mi comentario con su respuesta.
    • Me gusta la duplicación del tamaño de método, pero yo siempre terminan con una lista de más de lo que yo quiero. ¿Cómo puedo quitar el NULO entradas en la cola de la lista:
  2. 19

    Es muy fácil. Sólo se necesita añadir de la siguiente manera :

    list1$bar <- bar
    • Esto no abordar la cuestión de la eficiencia en todo.
    • Sí, pero es very easy... @Richard
  3. 6

    Operaciones que cambiar la longitud de una lista o vector en R siempre copia de todos los elementos en una lista de nuevo, y así va a ser lento, O(n). Almacenar en un entorno es O(1), pero tiene un mayor constante sobrecarga. Para una real O(1) anexar punto de referencia y comparación de una serie de enfoques, véase mi respuesta a la otra pregunta en https://stackoverflow.com/a/32870310/264177.

    • Y por O(1) para almacenar un elemento en un entorno, me refiero amortizado O(1) (es decir, en promedio), pero para la mayoría de los casos, es suficiente.
    • R el uso de un estilo de programación funcional que siempre tendrán problemas al añadir un elemento a una estructura existente, como en v <- c(v, newElement). La adición o sustitución de elementos a través de índice no es el estilo de programación funcional, sin embargo. No sé la representación interna de los vectores en R, pero el uso de un fragmentada de la matriz (individuales más pequeñas matrices que se vinculan en una cadena para formar una matriz más grande, básicamente), las partes no afectadas por el append podría ser reutilizado sin modificar, eliminar la carga de la GC. Después de todo, la base de R no es muy bien diseñado, por lo que es muy difícil hacer las cosas simples, a veces.
    • R los vectores son básicamente llano, de tamaño fijo, C matrices. Si algo cambia la longitud de R crea una nueva copia de la matriz completa. Que funciona muy bien para hacer el análisis de grandes conjuntos de datos, pero no tan bien para anexar los elementos uno por uno.

Dejar respuesta

Please enter your comment!
Please enter your name here