Anexar um objeto a uma lista em R em tempo constante amortizado, O (1)?

245

Se eu tiver alguma lista R mylist, você pode anexar um item obja ele da seguinte forma:

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

Mas certamente há uma maneira mais compacta. Quando eu era novo na R, tentei escrever lappend()assim:

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

mas é claro que isso não funciona devido à semântica de chamada por nome de R ( lsté efetivamente copiada durante a chamada, portanto as alterações para lstnão são visíveis fora do escopo de lappend(). Eu sei que você pode fazer hackers de ambiente em uma função R para alcançar fora do escopo de sua função e modifique o ambiente de chamada, mas isso parece um martelo grande para escrever uma função simples de acréscimo.

Alguém pode sugerir uma maneira mais bonita de fazer isso? Pontos de bônus se funcionar para vetores e listas.

usuario
fonte
5
R tem as características de dados imutáveis ​​que são freqüentemente encontradas em linguagens funcionais, odeio dizer isso, mas acho que você só precisa lidar com isso. Ele tem seus prós e seus contras
Dan
Quando você diz "chamar por nome", você realmente quer dizer "chamar por valor", certo?
Ken Williams
7
Não, definitivamente não é chamado por valor, caso contrário, isso não seria um problema. O R realmente usa a chamada por necessidade ( en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need ).
Nick
4
Uma boa idéia é pré-alocar seu vetor / lista: N = 100 mylist = vetor ('list', N) para (i em 1: N) {#mylist [[i]] = ...} Evite 'crescer 'objetos em R.
Fernando
Achei acidentalmente a resposta aqui, stackoverflow.com/questions/17046336/… Tão difícil de implementar, um algoritmo tão fácil!
KH Kim

Respostas:

255

Se for uma lista de cadeias, use a c()função:

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> 

Isso também funciona em vetores, então recebo os pontos de bônus?

Edit (01/02/2015): Este post está chegando no seu quinto aniversário. Alguns leitores gentis continuam repetindo quaisquer deficiências com isso, então, por todos os meios, veja também alguns dos comentários abaixo. Uma sugestão para listtipos:

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

Em geral, os tipos R podem dificultar a existência de um e apenas um idioma para todos os tipos e usos.

Dirk Eddelbuettel
fonte
19
Isso não acrescenta ... concatena. LLainda teria dois elementos depois de C(LL, c="harry")ser chamado.
Nick
27
Apenas transferir para LL: LL <- c(LL, c="harry").
Dirk Eddelbuettel
51
Isso funciona apenas com strings. Se a, bec são vetores inteiros, o comportamento é completamente diferente.
Alexandre Rademaker
8
@Dirk: Você tem as parênteses aninhadas de maneira diferente da minha. Minha chamada para c()tem 2 argumentos: a lista que estou tentando anexar, a saber list(a=3, b=c(4, 5)), e o item que estou tentando anexar, a saber c=c(6, 7). Se você usar minha abordagem, verá que 2 itens da lista são anexados ( 6e 7, com nomes c1e c2) em vez de um único vetor de 2 elementos nomeado ccomo pretendido claramente!
Jrandom_hacker
7
Então é a conclusão mylist <- list(mylist, list(obj))? Se sim, seria bom para modificar a resposta
Matthew
96

O OP (na revisão atualizada da pergunta de abril de 2012) está interessado em saber se há uma maneira de adicionar a uma lista no tempo constante amortizado, como pode ser feito, por exemplo, com um vector<>contêiner C ++ . As melhores respostas aqui até agora mostram apenas os tempos de execução relativos de várias soluções, devido a um problema de tamanho fixo, mas não abordam diretamente a eficiência algorítmica de várias soluções . Os comentários abaixo de muitas das respostas discutem a eficiência algorítmica de algumas das soluções, mas em todos os casos até o momento (em abril de 2015) eles chegaram à conclusão errada.

A eficiência algorítmica captura as características de crescimento, no tempo (tempo de execução) ou no espaço (quantidade de memória consumida) à medida que o tamanho do problema aumenta . A execução de um teste de desempenho para várias soluções, devido a um problema de tamanho fixo, não aborda a taxa de crescimento das várias soluções. O OP está interessado em saber se existe uma maneira de anexar objetos a uma lista R em "tempo constante amortizado". O que isso significa? Para explicar, primeiro deixe-me descrever "tempo constante":

  • Crescimento constante ou O (1) :

    Se o tempo necessário para executar uma determinada tarefa permanecer o mesmo que o tamanho do problema dobrar , dizemos que o algoritmo exibe crescimento de tempo constante , ou indicado na notação "Big O", exibe crescimento de tempo O (1). Quando o OP diz "tempo amortizado" constante, ele simplesmente significa "a longo prazo" ... ou seja, se executar uma única operação ocasionalmente leva muito mais tempo que o normal (por exemplo, se um buffer pré-alocado estiver esgotado e, ocasionalmente, for necessário redimensionar para um tamanho maior) tamanho do buffer), desde que o desempenho médio de longo prazo seja constante, ainda o chamaremos de O (1).

    Para comparação, também descreverei "tempo linear" e "tempo quadrático":

  • Crescimento linear ou O (n) :

    Se o tempo necessário para executar uma determinada tarefa dobrar à medida que o tamanho do problema dobrar , dizemos que o algoritmo exibe tempo linear ou crescimento de O (n) .

  • Crescimento quadrático ou O (n 2 ) :

    Se o tempo necessário para executar uma determinada tarefa aumenta pelo quadrado do tamanho do problema , dizemos que o algoritmo exibe tempo quadrático ou crescimento de O (n 2 ) .

Existem muitas outras classes de eficiência de algoritmos; Adardo o artigo da Wikipedia para uma discussão mais aprofundada.

Agradeço ao @CronAcronis por sua resposta, pois sou novo no R e foi bom ter um bloco de código totalmente construído para fazer uma análise de desempenho das várias soluções apresentadas nesta página. Estou emprestando seu código para minha análise, que eu duplico (empacotado em uma função) abaixo:

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
        }   
    )
}

Os resultados publicados por @CronAcronis definitivamente parecem sugerir que o a <- list(a, list(i))método é mais rápido, pelo menos para um tamanho de problema de 10000, mas os resultados para um único tamanho de problema não abordam o crescimento da solução. Para isso, precisamos executar no mínimo dois testes de criação de perfil, com diferentes tamanhos 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
> 

Antes de mais nada, uma palavra sobre os valores min / lq / média / mediana / uq / max: Como estamos realizando exatamente a mesma tarefa para cada uma das 5 execuções, em um mundo ideal, poderíamos esperar que fosse necessário exatamente o mesmo quantidade de tempo para cada execução. Mas a primeira execução normalmente é influenciada por períodos mais longos, devido ao fato de que o código que estamos testando ainda não foi carregado no cache da CPU. Após a primeira execução, esperamos que os tempos sejam razoavelmente consistentes, mas, ocasionalmente, nosso código pode ser despejado do cache devido a interrupções de tick de timer ou outras interrupções de hardware que não estejam relacionadas ao código que estamos testando. Ao testar os trechos de código 5 vezes, estamos permitindo que o código seja carregado no cache durante a primeira execução e, em seguida, dando a cada trecho 4 chances de execução até a conclusão sem interferência de eventos externos. Por esta razão,

Observe que eu escolhi executar primeiro com um tamanho de problema de 2000 e, em seguida, 20000, portanto, o tamanho do meu problema aumentou em um fator de 10 da primeira execução para a segunda.

Desempenho da listsolução: O (1) (tempo constante)

Vamos primeiro examinar o crescimento da listsolução, pois podemos dizer imediatamente que é a solução mais rápida nas duas execuções de criação de perfis: Na primeira execução, foram necessários 854 microssegundos (0,854 mili segundos) para executar 2000 tarefas " anexadas ". Na segunda execução, foram necessários 8.746 milissegundos para executar 20000 tarefas "anexar". Um observador ingênuo diria: "Ah, a listsolução exibe crescimento de O (n), pois, como o tamanho do problema aumentou em um fator de dez, o mesmo aconteceu com o tempo necessário para executar o teste". O problema com essa análise é que o que o OP deseja é a taxa de crescimento de uma única inserção de objeto , não a taxa de crescimento do problema geral. Sabendo disso, fica claro que olist A solução fornece exatamente o que o OP deseja: um método de anexar objetos a uma lista em O (1).

Desempenho das outras soluções

Nenhuma das outras soluções chega nem perto da velocidade da listsolução, mas é informativo examiná-las de qualquer maneira:

A maioria das outras soluções parece ter O (n) em desempenho. Por exemplo, a by_indexsolução, uma solução muito popular baseada na frequência com a qual eu a encontro em outras postagens de SO, levou 11,6 milissegundos para acrescentar 2000 objetos e 953 milissegundos para acrescentar dez vezes mais objetos. O tempo total do problema aumentou em um fator de 100; portanto, um observador ingênuo pode dizer "Ah, a by_indexsolução exibe crescimento de O (n 2 ), pois como o tamanho do problema aumentou em um fator de dez, o tempo necessário para executar o teste aumentou. por um fator de 100 ".Como antes, essa análise é falha, uma vez que o OP está interessado no crescimento de uma inserção de um único objeto. Se dividirmos o crescimento do tempo geral pelo crescimento do tamanho do problema, descobrimos que o crescimento do tempo dos objetos anexos aumentou por um fator de apenas 10, e não um fator de 100, que corresponde ao crescimento do tamanho do problema; portanto, a by_indexsolução é O (n) Não há soluções listadas que exibam crescimento de O (n 2 ) para anexar um único objeto.

phonetagger
fonte
1
Para o leitor: Leia a resposta de JanKanis, que fornece uma extensão muito prática para minhas descobertas acima, e mergulha um pouco nas despesas gerais de várias soluções, dados os trabalhos internos da implementação C de R.
phonetagger
4
Não tenho certeza se a opção de lista implementa o que é necessário:> length (c (c (c (lista (1)), list (2)), list (3))) [1] 3> length (list (list (list) (lista (1)), lista (2)), lista (3))) [1] 2. Parece mais uma lista aninhada.
Picarus
@Picarus - Eu acho que você está certo. Não estou mais trabalhando com R, mas felizmente JanKanis postou uma resposta com uma solução O (1) muito mais útil e observa o problema que você identificou. Tenho certeza que JanKanis vai gostar do seu voto.
phonetagger
@phonetagger, você deve editar sua resposta. Nem todo mundo vai ler todas as respostas.
Picarus
"nem uma única resposta abordou a questão real" -> O problema é que a pergunta original não era sobre complexidade de algoritmos, dê uma olhada nas edições da pergunta. O OP perguntou primeiro como anexar um elemento em uma lista e, vários meses depois, ele mudou a pergunta.
Carlos Cinelli
41

Nas outras respostas, apenas a listabordagem resulta em O (1) anexa, mas resulta em uma estrutura de lista profundamente aninhada, e não em uma lista simples e simples. Usei as estruturas de dados abaixo, elas suportam anexos O (1) (amortizados) e permitem que o resultado seja convertido novamente em uma lista simples.

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
}

e

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
}

Use-os da seguinte maneira:

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

[[2]]
[1] "world"

[[3]]
[1] 101

Essas soluções podem ser expandidas em objetos completos que suportam todas as operações relacionadas à lista, mas que permanecerão como um exercício para o leitor.

Outra variante para uma lista nomeada:

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
}

Benchmarks

Comparação de desempenho usando o código do @ phonetagger (que é baseado no código do @Cron Arconis). Eu também adicionei um better_env_as_containere mudei env_as_container_um pouco. O original env_as_container_estava quebrado e, na verdade, não armazena todos os 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

Eu adicionei linkedListe expandingListe uma versão embutido de ambos. A inlinedLinkedListé basicamente uma cópia list_, mas também converte a estrutura de volta aninhada em uma lista simples. Além disso, a diferença entre as versões embutida e não embutida se deve à sobrecarga das chamadas de função.

Todas as variantes de expandingListe linkedListmostram O (1) acrescentam desempenho, com o tempo de referência escalando linearmente com o número de itens anexados. linkedListé mais lento que expandingListe a sobrecarga da chamada de função também é visível. Portanto, se você realmente precisa de toda a velocidade possível (e deseja manter o código R), use uma versão embutida de expandingList.

Também observei a implementação C do R, e as duas abordagens devem ser O (1) anexadas para qualquer tamanho até que você fique sem memória.

Também mudei env_as_container_, a versão original armazenaria todos os itens no índice "i", substituindo o item anexado anteriormente. O que better_env_as_containereu adicionei é muito parecido, env_as_container_mas sem as deparsecoisas. Ambos exibem desempenho O (1), mas possuem uma sobrecarga um pouco maior que as listas vinculadas / expansíveis.

Sobrecarga de memória

Na implementação do CR, há uma sobrecarga de 4 palavras e 2 ints por objeto alocado. A linkedListabordagem aloca uma lista de comprimento dois por anexo, para um total de (4 * 8 + 4 + 4 + 2 * 8 =) 56 bytes por item acrescentado em computadores de 64 bits (excluindo a sobrecarga de alocação de memória, provavelmente mais perto de 64 bytes). A expandingListabordagem usa uma palavra por item acrescentado, além de uma cópia ao dobrar o comprimento do vetor, para um uso total de memória de até 16 bytes por item. Como a memória está toda em um ou dois objetos, a sobrecarga por objeto é insignificante. Não examinei profundamente o envuso da memória, mas acho que será mais próximo linkedList.

JanKanis
fonte
qual é o sentido de manter a opção de lista se ela não resolver o problema que estamos tentando resolver?
Picarus
1
@Picarus Não sei ao certo o que você quer dizer. Por que eu o mantive na referência? Como comparação com as outras opções. A list_opção é mais rápida e pode ser útil se você não precisar converter para uma lista normal, ou seja, se você usar o resultado como uma pilha.
JanKanis
O @Gabor Csardi postou uma maneira mais rápida de converter ambientes de volta para listas em uma pergunta diferente em stackoverflow.com/a/29482211/264177. Comparei isso também no meu sistema. É cerca de duas vezes mais rápido better_env_as_container, mas ainda mais lento que o linkedList e o expandList.
JanKanis
Listas profundamente aninhadas (n = 99999) parecem gerenciáveis ​​e toleráveis ​​para determinadas aplicações: alguém deseja fazer benchmark de nestoR ? (Ainda sou um pouco environmentdescuidado com as coisas que usei para o nestoR.) Meu gargalo é quase sempre o tempo humano gasto em codificação e análise de dados, mas aprecio os benchmarks que encontrei neste post. Quanto à sobrecarga de memória, eu não me importaria em cerca de um kB por nó para meus aplicativos. Eu mantenho grandes matrizes, etc.
Ana Nimbus
17

No Lisp, fizemos da seguinte maneira:

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

embora fosse 'contras', não apenas 'c'. Se você precisar começar com uma lista empy, use l <- NULL.

Arseny
fonte
3
Excelente! Todas as outras soluções retornam uma lista estranha de listas.
metakermit
4
No Lisp, o acréscimo a uma lista é uma operação O (1), enquanto o acréscimo é executado em O (n), @fly. A necessidade de reversão é superada pelo ganho de desempenho. Esse não é o caso em R. Nem mesmo no pairlist, que geralmente se assemelha à lista de listas.
Palec
@Palec "Este não é o caso em R" - não tenho certeza a qual "você" está se referindo. Você está dizendo que acrescentar não é O (1) ou não é O (n)?
voa
1
Estou dizendo que se você estivesse codificando no Lisp, sua abordagem seria ineficiente, @fly. Essa observação pretendia explicar por que a resposta está escrita como está. Em R, as duas abordagens estão no desempenho, AFAIK. Mas agora não tenho certeza da complexidade amortizada. Não toquei no R desde a época em que meu comentário anterior foi escrito.
Palec
3
Em R, essa abordagem será O (n). A c()função copia seus argumentos em um novo vetor / lista e retorna isso.
JanKanis
6

Você quer algo assim talvez?

> 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

Não é uma função muito educada (atribuir a parent.frame()é meio rude), mas IIUYC é o que você está pedindo.

Ken Williams
fonte
6

Fiz uma pequena comparação dos métodos mencionados aqui.

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
fonte
Esta é uma ótima informação: nunca teria adivinhado que list = listnão eram apenas os vencedores - mas por 1 a 2 ordens ou magnitude!
Javadba
5

Se você passar a variável da lista como uma string entre aspas, poderá alcançá-la na função, como:

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

tão:

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

[[2]]
[1] 2

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

[[2]]
[1] 2

[[3]]
[1] 3

> 

ou para crédito extra:

> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
> 
ayman
fonte
1
Esse é basicamente o comportamento que eu quero, no entanto, ele ainda chama anexos internamente, resultando em desempenho O (n ^ 2).
Nick
4

Não sei por que você acha que seu primeiro método não funcionará. Você tem um erro na função lappend: length (list) deve ser length (lst). Isso funciona bem e retorna uma lista com o objeto anexado.

Paulo
fonte
3
Você está absolutamente certo. Houve um erro no código e eu o corrigi. Testei o lappend()que forneci e parece ter um desempenho tão bom quanto c () e append (), todos exibindo comportamento O (n ^ 2).
Nick
2

Eu acho que o que você deseja fazer é realmente passar por referência (ponteiro) para a função - criar um novo ambiente (que é passado por referência a funções) com a lista adicionada a ele:

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
}

Agora você está apenas modificando a lista existente (não criando uma nova)

DavidM
fonte
1
Isso parece ter complexidade de tempo quadrática novamente. O problema é obviamente que o redimensionamento de lista / vetor não é implementado da maneira como geralmente é implementado na maioria dos idiomas.
eold
Sim - parece que o anexo no final é muito lento - provavelmente as listas b / c são recursivas e R é melhor em operações vetoriais do que em operações do tipo loop. Sua melhor a fazer:
DavidM
1
system.time (para (i em c (1: 10000) mylist [i] = i) (alguns segundos), ou melhor ainda, faça tudo em uma operação: system.time (mylist = list (1: 100000)) (menos do que um segundo), então a modificação que lista pré-alocados para com o ciclo irá também ser mais rápido.
DavidM
2

Esta é uma maneira simples de adicionar itens a uma 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"]

Ou programaticamente:

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
fonte
Isso realmente não é anexado. E se eu tiver 100 objetos e desejar anexá-los a uma lista programaticamente? R tem uma append()função, mas é realmente uma função concatenada e funciona apenas em vetores.
Nick
append()funciona em vetores e listas, e é um verdadeiro acréscimo (que é basicamente o mesmo que concatenate, então eu não vejo qual é seu problema)
Hadley
8
Uma função de acréscimo deve modificar um objeto existente, não criar um novo. Um anexo verdadeiro não teria comportamento O (N ^ 2).
Nick
2

de fato, há um sub-subtipo com a c()função. Se você fizer:

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

você obterá como esperado:

[[1]]
[1]

[[2]]
[1] "foo"

mas se você adicionar uma matriz com x <- c(x, matrix(5,2,2), sua lista terá outros 4 elementos de valor 5! É melhor você fazer:

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

Funciona para qualquer outro objeto e você obterá como esperado:

[[1]]
[1]

[[2]]
[1] "foo"

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

Finalmente, sua função se torna:

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

e funciona para qualquer tipo de objeto. Você pode ser mais inteligente e fazer:

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

Também existe list.appendno rlist( link para a documentação )

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

É muito simples e eficiente.

skan
fonte
1
não parece R para mim ... Python?
JD Longo
1
Fiz uma edição e tentei: é muito lento. Melhor usar o c()ou list-method. Ambos são muito mais rápidos.
5 de
Procurando um código rlist::list.append(), é essencialmente um invólucro base::c().
Nbenn 12/04/19
1

Para validação, executei o código de referência fornecido pelo @Cron. Há uma grande diferença (além de rodar mais rápido no processador i7 mais recente): o by_indexdesempenho agora é quase tão bom quanto o 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

Para referência, aqui está o código de referência copiado literalmente da resposta de @ Cron (caso ele mude mais tarde o conteúdo):

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
fonte
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
fonte
2
Não acho que esse seja o tipo de anexo que o OP estava procurando.
joran
Isso não está anexando elementos em uma lista. Aqui você está aumentando os elementos do vetor inteiro, que é o único elemento da lista. A lista possui apenas um elemento, um vetor inteiro.
Sergio
0

Essa é uma pergunta muito interessante e espero que meu pensamento abaixo possa contribuir com uma solução. Esse método fornece uma lista simples sem indexação, mas possui list e unlist para evitar as estruturas de aninhamento. Não tenho certeza sobre a velocidade, pois não sei como compará-la.

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
fonte
O que eu quero acrescentar é que ele fornece uma lista aninhada de dois níveis, mas é isso. A maneira como lista e trabalho itens não listados não é muito claro para mim, mas este é o resultado testando o código
xappppp
-1

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

Assim, podemos acrescentar facilmente o elemento / objeto usando o código acima

saravanan saminathan
fonte