Wir hängen ein Objekt zu einer Liste in R in amortisiert konstanter Zeit, O(1)?

Der OP (im April 2012 aktualisierte revision nicht in Frage) ist daran interessiert zu wissen, wenn es einen Weg gibt, um das hinzufügen zu einer Liste in amortisiert konstanter Zeit, wie getan werden kann, zum Beispiel mit einem C++ - vector<> container. Die beste Antwort(en?) hier bisher nur die relativen Ausführungszeiten für verschiedene Lösungen gegeben eine Feste Größe-problem, aber nicht die Adresse eine der verschiedenen Lösungen' Algorithmische Effizienz direkt. Kommentare unten viele der Antworten, besprechen der algorithmischen Effizienz der einige der Lösungen, aber in jedem Fall der Zeitpunkt (ab April 2015) Sie kommen zu der falschen Schlussfolgerung.

Algorithmische Effizienz fängt das Wachstum Eigenschaften, entweder in der Zeit (Ausführungszeit) oder Raum (Speicherverbrauch) als ein problem der Größe wächst. Läuft ein performance-test für verschiedene Lösungen gegeben eine Feste Größe-problem wird nicht auf die verschiedenen Lösungen Wachstumsrate. Der OP ist daran interessiert zu wissen, ob es eine Möglichkeit zum Anhängen von Objekten an ein R-Liste in der "amortized constant time". Was bedeutet das? Um zu erklären, lassen Sie mich zuerst beschreiben, "Konstante Zeit":

• Konstante oder O(1) Wachstum:

  Wenn die Zeit, die erforderlich ist zur Erfüllung einer bestimmten Aufgabe bleibt die gleiche als die Größe des Problems verdoppelt, dann sagt man, der Algorithmus Exponate konstanter Zeit Wachstum, oder erklärt, im "Big-O" - notation, Exponate O(1) Zeit Wachstum. Wenn der OP sagt "abgeschrieben" Konstante Zeit, er bedeutet einfach nur "in the long run"... also, wenn die Durchführung einer einzigen operation gelegentlich dauert viel länger als normal (z.B. wenn eine Feste Puffer erschöpft ist und gelegentlich erfordert eine Anpassung durch einen größeren Puffer), solange die langfristige Durchschnittliche Leistung ist konstanter Zeit, wir werden es immer noch O(1).

  Für den Vergleich, ich werde auch beschreiben, "lineare Zeit" und "in quadratischer Zeit":

• Lineare oder O(n) Wachstum:

  Wenn die Zeit, die erforderlich ist zur Erfüllung einer bestimmten Aufgabe verdoppelt als die Größe des Problems verdoppelt, dann sagt man, der Algorithmus Exponate die lineare Zeit, oder O(n) Wachstum.

• Quadratische oder O(n²) Wachstum:

  Wenn die Zeit, die erforderlich ist zur Erfüllung einer bestimmten Aufgabe erhöht sich mit dem Quadrat der problem-Größe, wir sagen, der Algorithmus Exponate quadratische Zeit, oder O(n²) Wachstum.

Gibt es viele andere Effizienz-Klassen von algorithmen; ich aufschieben, um die Wikipedia-Artikel für die weitere Diskussion.

Ich danke @CronAcronis für seine Antwort, als ich bin neu in R und es war schön, eine voll konstruierte code-block, der für eine performance-Analyse der verschiedenen Lösungen präsentiert auf dieser Seite. Ich bin Kreditaufnahme seinen code für meine Analyse, die ich duplizieren (eingewickelt in einer Funktion) unten:

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

Die Ergebnisse gepostet von @CronAcronis scheinen definitiv zu vermuten, dass die a <- list(a, list(i)) Methode ist am schnellsten, zumindest für ein problem der Größe von 10000, aber die Ergebnisse für ein einzelnes problem Größe tun, nicht auf das Wachstum der Lösung. Für die, die wir ausführen müssen, um ein minimum von zwei profiling-tests, mit unterschiedlichen Größen problem:

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

Erstens, ein Wort über die min/lq/mean/median/uq/max-Werte: Da wir uns an die exakt gleiche Aufgabe für jeden der 5 läuft, in einer idealen Welt könnten wir erwarten, dass es dauern würde, genau die gleiche Menge an Zeit für jeden Lauf. Aber der erste Lauf ist normalerweise vorgespannt in Richtung auf längere Zeit aufgrund der Tatsache, dass der code, den wir hier testen, ist noch nicht geladen, in den cache der CPU. Nach dem ersten Lauf, würden wir erwarten, dass die Zeiten relativ konstant, aber gelegentlich unser code kann entfernt werden aus dem cache aufgrund der timer-tick-interrupts oder hardware-interrupts, die keinen Bezug zum code, den wir testen. Testen Sie die code-snippets, 5-mal, wir werden so dass der code in den cache geladen beim ersten mal und dann jedes snippet 4 Chancen bis zum Abschluss ausgeführt, ohne Einmischung von außen-Veranstaltungen. Aus diesem Grund, und weil wir auch wirklich die exakt gleiche code unter den exakt gleichen eingangsbedingungen jedes mal, betrachten wir nur die 'min' mal ausreichend zu sein für die besten Vergleich zwischen den verschiedenen code-Optionen.

Beachten Sie, dass ich entschied mich für den ersten Lauf mit einem problem der Größe von 2000 und 20000, also mein problem vergrößert um einen Faktor von 10 aus dem ersten Lauf auf den zweiten.

Leistung der list Lösung: O(1) (Konstante Zeit)

Lassen Sie uns zuerst einen Blick auf die Entwicklung der list Lösung, da wir sofort erkennen kann, dass es die Schnellste Lösung in beiden profiling läuft: Im ersten Lauf, es dauerte 854 microSekunden (0.854 milliSekunden), um 2000 "append" - Aufgaben. Im zweiten Durchgang dauerte es 8.746 Millisekunden durchführen 20000 "append" - Aufgaben. Ein naiver Beobachter würde sagen, "Ah, die list - Lösung Exponate O(n) Wachstum, da das problem der Größe wuchs um den Faktor zehn, so hat die Zeit, die erforderlich ist, um den test auszuführen." Das problem mit dieser Analyse ist, dass das, was der OP will, ist die Wachstumsrate der ein einzelnes Objekt einfügen, nicht die Wachstumsrate des Gesamt-Problems. Wissen, dass, es ist klar, dass dann die list Lösung bietet genau das, was der OP will: eine Methode zum anfügen von Objekten zu einer Liste in O(1) Zeit.

Leistung von anderen Lösungen

Keine der anderen Lösungen auch nur annähernd die Geschwindigkeit des list Lösung, aber es ist lehrreich, zu prüfen, Sie trotzdem:

Meisten anderen Lösungen zu sein scheinen, O(n) in der Leistung. Zum Beispiel, die by_index Lösung, eine sehr beliebte Lösung, basierend auf der Häufigkeit, mit der ich es in anderen posts, nahm 11.6 Millisekunden Anhängen 2000 Objekte und 953 Millisekunden angefügt zehn mal, dass viele Objekte. Das Allgemeine problem ist an der Zeit wuchs um den Faktor 100, so daß ein naiver Beobachter könnte sagen "Ah, die by_index - Lösung Exponate O(n²) Wachstum, da das problem der Größe wuchs um den Faktor zehn, die Zeit, die erforderlich ist, um den test auszuführen wuchs um den Faktor 100." Nach wie vor, diese Analyse ist fehlerhaft, da die OP ist daran interessiert, das Wachstum eines einzelnen Objekts einfügen. Wenn wir unterteilen die gesamte Zeit Wachstum mit dem problem, die Größe, das Wachstum, finden wir, dass der Zeit-Wachstum von Anhängen Objekte stieg um einen Faktor von nur 10, nicht einen Faktor von 100, das entspricht dem Wachstum der problem-Größe, so dass die by_index Lösung ist O(n). Es gibt keine Lösungen aufgeführt, die zeigen O(n²) Wachstum für das anfügen eines einzelnen Objekts.

Du willst so etwas wie das vielleicht?

> 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

Es ist nicht sehr höflich Funktion (Zuordnung zu parent.frame() ist sowas von unhöflich), aber IIUYC es ist, was Sie für Fragen.

Habe ich mal einen kleinen Vergleich von Methoden, die hier erwähnt.

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

Ergebnisse:

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 

versuchen, diese Funktion lappend

lappend <- function (lst, ...){
  lst <- c(lst, list(...))
  return(lst)
}

und andere Anregungen von dieser Seite Fügen Sie namens-Vektor in eine Liste

Bye.

Dies ist eine einfache Möglichkeit zum hinzufügen von Elementen zu einem R-Liste:

# 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"]

Oder programmatisch:

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

Gibt es auch list.append von der rlist (link zur Dokumentation)

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

Es ist sehr einfach und effizient.

> 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

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

So können wir leicht append-element/Objekt mit dem obigen code