Dodać obiekt do listy w R w zamortyzowanym stałym czasie, O (1)?

245

Jeśli mam listę R mylist, możesz objdo niej dodać element w następujący sposób:

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

Ale na pewno jest jakiś bardziej zwarty sposób. Kiedy byłem nowy w R, próbowałem pisać w ten lappend()sposób:

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

ale oczywiście to nie działa z powodu semantyki wywołania R według nazwy ( lstjest skutecznie kopiowane podczas wywołania, więc zmiany lstnie są widoczne poza zakresem lappend(). Wiem, że możesz zrobić hakowanie środowiska za pomocą funkcji R, aby dotrzeć poza zakres funkcji i mutowanie środowiska wywołującego, ale wydaje się, że to duży młot do napisania prostej funkcji dołączania.

Czy ktoś może zasugerować piękniejszy sposób na zrobienie tego? Punkty bonusowe, jeśli działa zarówno dla wektorów, jak i list.

Nacięcie
źródło
5
R ma niezmienne cechy danych, które często występują w językach funkcjonalnych, nie chcę tego mówić, ale myślę, że po prostu trzeba sobie z tym poradzić. Ma swoje zalety i wady
Dan
Kiedy mówisz „call-by-name”, naprawdę masz na myśli „call-by-value”, prawda?
Ken Williams
7
Nie, zdecydowanie nie jest to call-by-value, w przeciwnym razie nie byłoby problemu. R faktycznie używa call-by-need ( en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need ).
Nick
4
Dobrym pomysłem jest wstępne przydzielenie wektora / listy: N = 100 lista odtwarzania = wektor („lista”, N) dla (i w 1: N) {# lista [[i]] = ...} Unikaj wzrostu 'obiekty w R.
Fernando
Tutaj przypadkowo znalazłem odpowiedź, stackoverflow.com/questions/17046336/... Tak trudno wdrożyć tak łatwy algorytm!
KH Kim

Odpowiedzi:

255

Jeśli jest to lista ciągów znaków, po prostu użyj c()funkcji:

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> 

Działa to również na wektory, więc czy otrzymam punkty bonusowe?

Edycja (2015-luty-01): Ten wpis będzie miał piąte urodziny. Niektórzy życzliwi czytelnicy powtarzają wszelkie niedociągnięcia, więc zdecydowanie zobacz także niektóre z poniższych komentarzy. Jedna sugestia dla listtypów:

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

Ogólnie rzecz biorąc, typy R mogą utrudnić posiadanie jednego i tylko jednego idiomu dla wszystkich typów i zastosowań.

Dirk Eddelbuettel
źródło
19
Nie dołącza się ... łączy. LLnadal miałby dwa elementy po C(LL, c="harry")wywołaniu.
Nick
27
Wystarczy przypisać do LL: LL <- c(LL, c="harry").
Dirk Eddelbuettel
51
Działa to tylko z łańcuchami. Jeśli a, b i c są wektorami całkowitymi, zachowanie jest zupełnie inne.
Alexandre Rademaker,
8
@Dirk: Masz pareny zagnieżdżone inaczej niż ja. Moje wezwanie do c()ma 2 argumenty: listę, do której próbuję dołączyć, a mianowicie list(a=3, b=c(4, 5))element, który próbuję dołączyć, mianowicie c=c(6, 7). Jeśli użyjesz mojego podejścia, zobaczysz, że 2 elementy listy są dołączane ( 6wraz 7z nazwami c1i c2) zamiast jednego 2-elementowego wektora o nazwie ctak, jak jest to wyraźnie zamierzone!
j_random_hacker
7
Więc jaki jest wniosek mylist <- list(mylist, list(obj))? Jeśli tak, dobrze byłoby zmodyfikować odpowiedź
Mateusz
96

OP (w zaktualizowanej wersji pytania z kwietnia 2012 r.) Jest zainteresowany wiedzą, czy istnieje sposób, aby dodać do listy w zamortyzowanym stałym czasie, na przykład za pomocą vector<>kontenera C ++ . Najlepsza odpowiedź (odpowiedzi)? Jak dotąd pokazuje tylko względne czasy wykonania dla różnych rozwiązań, biorąc pod uwagę problem o stałej wielkości, ale nie odnosi się bezpośrednio do wydajności algorytmicznej różnych rozwiązań . Komentarze poniżej wielu odpowiedzi omawiają wydajność algorytmiczną niektórych rozwiązań, ale w każdym przypadku do tej pory (od kwietnia 2015 r.) Dochodzą do błędnych wniosków.

Wydajność algorytmiczna rejestruje charakterystykę wzrostu, zarówno w czasie (czas wykonania), jak i przestrzeni (ilość zajętej pamięci) wraz ze wzrostem wielkości problemu . Przeprowadzenie testu wydajności dla różnych rozwiązań ze względu na problem o stałej wielkości nie odnosi się do tempa wzrostu różnych rozwiązań. OP chce wiedzieć, czy istnieje sposób na dodanie obiektów do listy R w „zamortyzowanym czasie stałym”. Co to znaczy? Aby wyjaśnić, najpierw pozwól mi opisać „stały czas”:

  • Stały wzrost lub O (1) :

    Jeśli czas wymagany do wykonania danego zadania pozostaje taki sam, ponieważ rozmiar problemu podwaja się , to mówimy, że algorytm wykazuje stały wzrost czasu , lub określony w notacji „Big O”, wzrost czasu O (1). Kiedy OP mówi „zamortyzowany” stały czas, to po prostu znaczy „w długim okresie” ... tj. Jeśli wykonanie pojedynczej operacji czasami zajmuje znacznie więcej czasu niż normalnie (np. Jeśli wstępnie przydzielony bufor jest wyczerpany i czasami wymaga zmiany rozmiaru na większy rozmiar bufora), o ile średnia długoterminowa wydajność jest stała, nadal będziemy ją nazywać O (1).

    Dla porównania opiszę również „czas liniowy” i „czas kwadratowy”:

  • Wzrost liniowy lub O (n) :

    Jeśli czas potrzebny do wykonania określonego zadania podwójne jako wielkości problemu podwójnej , to znaczy z wystawy algorytmu liniowej czasie lub O (n) wzrostu.

  • Wzrost kwadratowy lub O (n 2 ) :

    Jeśli czas wymagany do wykonania danego zadania zwiększa się o kwadrat wielkości problemu , to mówimy, że algorytm wykazuje kwadratowy czas lub wzrost O (n 2 ) .

Istnieje wiele innych klas wydajności algorytmów; Odsyłam do artykułu z Wikipedii w celu dalszej dyskusji.

Dziękuję @CronAcronis za jego odpowiedź, ponieważ jestem nowy w R i miło było mieć w pełni skonstruowany blok kodu do analizy wydajności różnych rozwiązań przedstawionych na tej stronie. Pożyczam jego kod do mojej analizy, którą powielam (zawinięty w funkcję) poniżej:

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

Wyniki opublikowane przez @CronAcronis zdecydowanie wydają się sugerować, że a <- list(a, list(i))metoda jest najszybsza, przynajmniej dla rozmiaru problemu 10000, ale wyniki dla pojedynczego rozmiaru problemu nie uwzględniają wzrostu rozwiązania. W tym celu musimy przeprowadzić co najmniej dwa testy profilowania o różnych rozmiarach problemów:

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

Po pierwsze, słowo o wartościach min / lq / średnia / mediana / uq / max: Ponieważ wykonujemy dokładnie to samo zadanie dla każdego z 5 przebiegów, w idealnym świecie możemy oczekiwać, że zajmie to dokładnie to samo ilość czasu na każdy bieg. Jednak pierwsze uruchomienie jest zwykle tendencyjne w kierunku dłuższych czasów, ponieważ testowany kod nie jest jeszcze ładowany do pamięci podręcznej procesora. Po pierwszym uruchomieniu spodziewalibyśmy się, że czasy będą dość spójne, ale czasami nasz kod może zostać usunięty z pamięci podręcznej z powodu przerwania taktowania zegara lub innych przerwań sprzętowych niezwiązanych z testowanym kodem. Testując fragmenty kodu 5 razy, pozwalamy na załadowanie kodu do pamięci podręcznej podczas pierwszego uruchomienia, a następnie dajemy każdemu z 4 fragmentów szansę na ukończenie bez zakłócania przez zdarzenia zewnętrzne. Z tego powodu,

Zauważ, że wybrałem najpierw uruchomienie z problemem o wielkości 2000, a następnie 20000, więc mój rozmiar problemu wzrósł o współczynnik 10 od pierwszego uruchomienia do drugiego.

Wydajność listrozwiązania: O (1) (czas stały)

Spójrzmy najpierw na rozwój listrozwiązania, ponieważ od razu możemy stwierdzić, że jest to najszybsze rozwiązanie w obu przebiegach profilowania: w pierwszym uruchomieniu wykonanie 2000 zadań „dopisania” zajęło 854 mikrosekund (0,854 milisekund ). W drugim uruchomieniu wykonanie 20000 zadań „dopisujących” zajęło 8,746 milisekund. Naiwny obserwator powiedziałby: „Ach, listrozwiązanie wykazuje wzrost O (n), ponieważ wraz ze wzrostem wielkości problemu dziesięciokrotnie zwiększył się czas potrzebny na wykonanie testu”. Problem z tą analizą polega na tym, że PO chce szybkości wzrostu wstawienia pojedynczego obiektu , a nie szybkości wzrostu ogólnego problemu. Wiedząc o tym, jasne jest, żelist rozwiązanie zapewnia dokładnie to, czego chce OP: metodę dołączania obiektów do listy w czasie O (1).

Wydajność innych rozwiązań

Żadne z pozostałych rozwiązań nie zbliża się nawet do szybkości listrozwiązania, ale i tak warto je zbadać:

Wydaje się, że większość innych rozwiązań ma wydajność O (n). Na przykład by_indexrozwiązanie, bardzo popularne rozwiązanie oparte na częstotliwości, z jaką znajduję je w innych postach SO, zajęło 11,6 milisekund, aby dołączyć 2000 obiektów, i 953 milisekund, aby dołączyć dziesięć razy tyle obiektów. Czas ogólnego problemu wzrósł 100-krotnie, więc naiwny obserwator mógłby powiedzieć: „Ach, by_indexrozwiązanie wykazuje wzrost O (n 2 ), ponieważ wraz ze wzrostem wielkości problemu dziesięciokrotnie zwiększył się czas potrzebny na wykonanie testu 100 razy. ”Tak jak poprzednio, analiza ta jest błędna, ponieważ PO jest zainteresowany wzrostem wstawiania jednego obiektu. Jeśli podzielimy całkowity wzrost czasu przez wzrost wielkości problemu, okaże się, że wzrost czasu dołączanych obiektów zwiększył się tylko 10, a nie 100, co odpowiada wzrostowi wielkości problemu, więc by_indexrozwiązaniem jest O (n). Nie ma na liście rozwiązań, które wykazują wzrost O (n 2 ) przy dołączaniu pojedynczego obiektu.

fonetagger
źródło
1
Do czytelnika: Proszę przeczytać odpowiedź JanKanisa, która stanowi bardzo praktyczne rozszerzenie moich ustaleń powyżej i zanurza się nieco w narzutu różnych rozwiązań, biorąc pod uwagę wewnętrzne funkcjonowanie implementacji C R.
phonetagger
4
Nie jestem pewien, czy opcja listy implementuje to, co jest wymagane:> długość (c (c (c (lista (1)), lista (2)), lista (3))) [1] 3> długość (lista (lista (lista) (lista (1)), lista (2)), lista (3))) [1] 2. Wygląda bardziej jak listy zagnieżdżone.
Picarus
@Picarus - Myślę, że masz rację. Nie pracuję już z R, ale na szczęście JanKanis opublikował odpowiedź ze znacznie bardziej użytecznym rozwiązaniem O (1) i odnotowuje zidentyfikowany problem. Jestem pewien, że JanKanis doceni twoją opinię.
fonetagger
@phonetagger, powinieneś edytować swoją odpowiedź. Nie wszyscy przeczytają wszystkie odpowiedzi.
Picarus,
„żadna odpowiedź nie rozwiązała rzeczywistego pytania” -> Problem polega na tym, że pierwotne pytanie nie dotyczyło złożoności algorytmu, spójrz na edycje pytania. OP najpierw zapytał, jak dołączyć element do listy, a następnie kilka miesięcy później zmienił pytanie.
Carlos Cinelli,
41

W pozostałych odpowiedziach tylko listpodejście podejścia w O (1) dołącza, ale skutkuje głęboko zagnieżdżoną strukturą listy, a nie zwykłą pojedynczą listą. Użyłem poniższych struktur danych, obsługują one załączniki O (1) (amortyzowane) i pozwalają na przekonwertowanie wyniku z powrotem na zwykłą listę.

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
}

i

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
}

Użyj ich w następujący sposób:

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

[[2]]
[1] "world"

[[3]]
[1] 101

Rozwiązania te można rozszerzyć na pełne obiekty, które same obsługują wszystkie operacje związane z listami, ale pozostaną dla czytelnika ćwiczeniem.

Kolejny wariant dla nazwanej listy:

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
}

Benchmarki

Porównanie wydajności przy użyciu kodu @ phonetagger (który jest oparty na kodzie @Cron Arconis). Dodałem również better_env_as_containeri env_as_container_nieco zmieniłem . Oryginał env_as_container_został zepsuty i nie przechowuje wszystkich numerów.

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
    }

wynik:

> 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

Dodałem linkedListi expandingListwbudowaną wersję obu. Jest inlinedLinkedListto w zasadzie kopia list_, ale przekształca również zagnieżdżoną strukturę z powrotem w zwykłą listę. Poza tym różnica między wersjami wbudowanymi i nie wstawionymi wynika z narzutu wywołań funkcji.

Wszystkie warianty expandingListi linkedListpokazują wydajność O (1), z skalowaniem czasu testu porównawczego liniowo z liczbą dołączanych elementów. linkedListjest wolniejszy niż expandingList, a narzut funkcji jest również widoczny. Więc jeśli naprawdę potrzebujesz całej prędkości, jaką możesz uzyskać (i chcesz trzymać się kodu R), użyj wbudowanej wersji expandingList.

Spojrzałem również na implementację C w R i oba podejścia powinny być dołączone do O (1) dla dowolnego rozmiaru aż do wyczerpania pamięci.

Zmieniłem również env_as_container_, oryginalna wersja przechowywałaby każdy element pod indeksem „i”, zastępując wcześniej dołączony element. better_env_as_containerDodałem jest bardzo podobny do env_as_container_, ale bez deparserzeczy. Oba wykazują wydajność O (1), ale mają narzut, który jest nieco większy niż listy połączone / rozwijane.

Narzut pamięci

W implementacji CR występuje narzut 4 słów i 2 ints na przydzielony obiekt. linkedListPrzydziela podejście jedna lista dwóch długości za dodać, w sumie (4 * 8 + 4 + 4 + 2 * 8 =) 56 bajty na załączonym pozycji na komputerach 64-bitowych (bez alokacji pamięci górnym, więc prawdopodobnie bliżej 64 bajty). expandingListPodejście wykorzystuje jedno słowo za załączonym pozycji, a także kopię gdy podwojenie długości wektora, więc całkowite zużycie pamięci do 16 bajtów na pozycji. Ponieważ pamięć jest w jednym lub dwóch obiektach, narzut na obiekt jest nieznaczny. Nie zagłębiłem się w envużycie pamięci, ale myślę, że będzie bliżejlinkedList .

JanKanis
źródło
po co utrzymywać opcję listy, jeśli nie rozwiązuje ona problemu, który próbujemy rozwiązać?
Picarus,
1
@Picarus Nie jestem pewien, co masz na myśli. Dlaczego trzymałem go w benchmarku? W porównaniu z innymi opcjami. Ta list_opcja jest szybsza i może być użyteczna, jeśli nie musisz konwertować na normalną listę, tj. Jeśli użyjesz wyniku jako stosu.
JanKanis,
@Gabor Csardi opublikował szybszy sposób konwersji środowisk z powrotem na listy w innym pytaniu na stackoverflow.com/a/29482211/264177. Testowałem to również w moim systemie. Jest około dwa razy szybszy better_env_as_container, ale wciąż wolniejszy niż linkedList i expandingList.
JanKanis
Głęboko zagnieżdżone (n = 99999) listy wydają się łatwe do zarządzania i tolerowane w niektórych aplikacjach: Czy ktoś chce przeprowadzić test porównawczy nestoR ? (Nadal jestem trochę noob w environmentsprawach, których użyłem do nestoR.) Moim wąskim gardłem jest prawie zawsze ludzki czas spędzany na kodowaniu i analizie danych, ale doceniam testy porównawcze, które znalazłem w tym poście. Jeśli chodzi o narzut pamięci, nie miałbym nic przeciwko około kB na węzeł dla moich aplikacji. Trzymam się dużych tablic itp.
Ana Nimbus
17

W Lisp zrobiliśmy to w ten sposób:

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

chociaż były to „minusy”, a nie tylko „c”. Jeśli chcesz zacząć od listy empy, użyj l <- NULL.

Arsen
źródło
3
Doskonały! Wszystkie pozostałe rozwiązania zwracają dziwną listę list.
metakermit
4
W Lisp poprzedzanie listy jest operacją O (1), podczas gdy dołączanie działa w O (n), @flies. Potrzeba zmiany jest równoważona przez wzrost wydajności. Tak nie jest w przypadku R. Nawet w pairlist, który generalnie najbardziej przypomina listy List.
Palec,
@Palec „Tak nie jest w R” - nie jestem pewien, do którego „tego” się odnosisz. Czy mówisz, że dołączanie nie jest O (1), czy nie jest O (n)?
lata
1
Mówię, że jeśli kodujesz w Lisp, twoje podejście byłoby nieefektywne, @flies. Ta uwaga miała wyjaśnić, dlaczego odpowiedź jest napisana w obecnej formie. W wersji R oba podejścia są równorzędne pod względem wydajności - AFAIK. Ale teraz nie jestem pewien co do zamortyzowanej złożoności. Nie dotykałem R. od czasu, kiedy napisano mój poprzedni komentarz.
Palec
3
W przypadku R podejściem tym będzie O (n). W c()kopiuje swoje argumenty do nowego wektora / listy i zwraca.
JanKanis,
6

Może chcesz coś takiego?

> 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

Nie jest to bardzo uprzejma funkcja (przypisywanie do niej parent.frame()jest niegrzeczne), ale IIUYC jest tym, o co prosisz.

Ken Williams
źródło
6

Dokonałem niewielkiego porównania wymienionych tu metod.

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

Wyniki:

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
źródło
To świetna informacja: nigdy nie zgadłbym, że list = listto nie tylko zwycięzca - ale o 1 do 2 zamówień lub wielkości!
javadba
5

Jeśli przekażesz zmienną listy jako ciąg cytowany, możesz uzyskać do niej dostęp z funkcji takiej jak:

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

więc:

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

[[2]]
[1] 2

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

[[2]]
[1] 2

[[3]]
[1] 3

> 

lub dla dodatkowego kredytu:

> v <- vector()
> push("v", 1)
> v
[1] 1
> push("v", 2)
> v
[1] 1 2
> 
ayman
źródło
1
Jest to w zasadzie zachowanie, które chcę, jednak nadal wywołuje append wewnętrznie, co powoduje wydajność O (n ^ 2).
Nick
4

Nie jestem pewien, dlaczego uważasz, że Twoja pierwsza metoda nie zadziała. Masz błąd w funkcji lappend: długość (lista) powinna być długością (pierwsza). Działa to dobrze i zwraca listę z dołączonym obj.

Paweł
źródło
3
Masz absolutną rację. W kodzie był błąd i naprawiłem go. Przetestowałem lappend()dostarczone przeze mnie i wydaje się, że działają one równie dobrze jak c () i append (), z których wszystkie wykazują zachowanie O (n ^ 2).
Nick
2

Myślę, że to, co chcesz zrobić, to faktycznie przechodzą przez odniesienie (wskaźnik) do function-- stworzyć nowe środowisko, (które są przekazywane przez referencję do funkcji) z listy dodano do niego:

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
}

Teraz modyfikujesz tylko istniejącą listę (nie tworzysz nowej)

DavidM
źródło
1
Wydaje się, że znów ma kwadratową złożoność czasu. Problem polega oczywiście na tym, że zmiana rozmiaru listy / wektora nie jest zaimplementowana w sposób, w jaki jest zwykle implementowany w większości języków.
odważny
Tak - wygląda na to, że dołączanie na końcu jest bardzo wolne - prawdopodobnie listy b / c są rekurencyjne, a R najlepiej sprawdza się w operacjach wektorowych, a nie w operacjach typu pętli. O wiele lepiej zrobić:
DavidM
1
system.time (dla listy odtwarzania (i in c (1: 10000) [i] = i) (kilka sekund), lub jeszcze lepiej zrób to wszystko w jednej operacji: system.time (lista odtwarzania (1: 100000)) (mniej niż sekunda), a także szybsze modyfikowanie tej wstępnie przydzielonej listy za pomocą pętli for
DavidM
2

Jest to prosty sposób dodawania elementów do listy 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"]

Lub programowo:

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
źródło
To naprawdę nie jest dołączane. Co jeśli mam 100 obiektów i chcę programowo dołączyć je do listy? R ma append()funkcję, ale tak naprawdę jest to funkcja łącząca i działa tylko na wektorach.
Nick
append()działa na wektorach i listach i jest to prawdziwy dodatek (który jest w zasadzie taki sam jak konkatenacja, więc nie rozumiem, na czym polega twój problem)
hadley
8
Funkcja dołączania powinna mutować istniejący obiekt, a nie tworzyć nowy. Prawdziwy append nie miałby zachowania O (N ^ 2).
Nick
2

w rzeczywistości istnieje subtelność z c()funkcją. Jeśli zrobisz:

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

otrzymasz zgodnie z oczekiwaniami:

[[1]]
[1]

[[2]]
[1] "foo"

ale jeśli dodasz macierz x <- c(x, matrix(5,2,2), twoja lista będzie miała jeszcze 4 elementy wartości 5! Lepiej wykonaj:

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

Działa dla każdego innego obiektu, a otrzymasz zgodnie z oczekiwaniami:

[[1]]
[1]

[[2]]
[1] "foo"

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

Wreszcie twoja funkcja staje się:

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

i działa na każdym typie obiektu. Możesz być mądrzejszy i robić:

push_back <- function(l, ...) c(l, list(...))
push_front <- function(l, ...) c(list(...), l)
David Bellot
źródło
1

Jest również list.appendz rlist( link do dokumentacji )

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

To bardzo proste i wydajne.

skan
źródło
1
dla mnie nie wygląda jak R ... Python?
JD Long
1
Zrobiłem edycję i wypróbowałem: To cholernie wolno. Lepiej użyj metody c()lub list. Oba są znacznie szybsze.
5
Poszukując kodu rlist::list.append(), jest to zasadniczo opakowanie base::c().
nbenn
1

W celu weryfikacji uruchomiłem kod testu dostarczony przez @Cron. Jest jedna główna różnica (oprócz szybszego działania na nowszym procesorze i7): by_indexteraz działa prawie tak dobrze, jak 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

W celach informacyjnych znajduje się kod testu porównawczego skopiowany dosłownie z odpowiedzi @ Cron (na wypadek, gdyby później zmienił treść):

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
źródło
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
źródło
2
Nie sądzę, żeby tego rodzaju dodatek szukał OP.
joran
To nie jest dodawanie elementów na liście. Tutaj zwiększasz elementy wektora liczb całkowitych, który jest jedynym elementem listy. Lista ma tylko jeden element, wektor liczb całkowitych.
Sergio,
0

To bardzo interesujące pytanie i mam nadzieję, że moja poniższa myśl może przyczynić się do rozwiązania tego problemu. Ta metoda daje płaską listę bez indeksowania, ale ma listę i listę, aby uniknąć zagnieżdżania struktur. Nie jestem pewien szybkości, ponieważ nie wiem, jak ją przeprowadzić.

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
źródło
Chcę dodać, że daje dwupoziomową listę zagnieżdżoną, ale to wszystko. Sposób, w jaki działa praca z listą i listą, nie jest dla mnie bardzo jasny, ale jest to wynik testowania kodu
xappppp 14.04.16
-1

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

Możemy więc łatwo dołączyć element / obiekt za pomocą powyższego kodu

saravanan saminathan
źródło