Wenn ich eine R-Liste habe mylist
, können Sie ein Element obj
wie folgt anhängen :
mylist[[length(mylist)+1]] <- obj
Aber es gibt sicherlich einen kompakteren Weg. Als ich neu bei R war, habe ich versucht, lappend()
so zu schreiben :
lappend <- function(lst, obj) {
lst[[length(lst)+1]] <- obj
return(lst)
}
Aber das funktioniert natürlich nicht aufgrund der Call-by-Name-Semantik von R ( lst
wird beim Aufruf effektiv kopiert, sodass Änderungen an lst
außerhalb des Bereichs von nicht sichtbar sind lappend()
. Ich weiß, dass Sie in einer R-Funktion Umgebungs-Hacking durchführen können, um außerhalb des Bereichs zu gelangen Umfang Ihrer Funktion und mutieren die aufrufende Umgebung, aber das scheint wie ein großer Hammer, um eine einfache Append-Funktion zu schreiben.
Kann jemand einen schöneren Weg vorschlagen, dies zu tun? Bonuspunkte, wenn es sowohl für Vektoren als auch für Listen funktioniert.
Antworten:
Wenn es sich um eine Liste von Zeichenfolgen handelt, verwenden Sie einfach die
c()
Funktion:Das funktioniert auch mit Vektoren. Bekomme ich also die Bonuspunkte?
Bearbeiten (01.02.2015): Dieser Beitrag erscheint an seinem fünften Geburtstag. Einige freundliche Leser wiederholen immer wieder Mängel, daher sehen Sie auf jeden Fall auch einige der folgenden Kommentare. Ein Vorschlag für
list
Typen:Im Allgemeinen können R-Typen es schwierig machen, eine und nur eine Redewendung für alle Typen und Verwendungen zu haben.
quelle
LL
hätte noch zwei elemente nachdemC(LL, c="harry")
aufgerufen wird.LL <- c(LL, c="harry")
.c()
hat zwei Argumente: die Liste, an die ich anhängen möchtelist(a=3, b=c(4, 5))
, und das Element, an das ich anhängen möchte, nämlichc=c(6, 7)
. Wenn Sie meinen Ansatz verwenden, werden Sie sehen, dass 2 Listenelemente (6
und7
mit Namenc1
undc2
) anstelle eines einzelnen 2-Element-Vektors angehängt werden , derc
eindeutig benannt ist!mylist <- list(mylist, list(obj))
? Wenn ja, wäre es schön, die Antwort zu ändernDas OP (in der im April 2012 aktualisierten Überarbeitung der Frage) ist daran interessiert zu wissen, ob es eine Möglichkeit gibt, eine Liste in amortisierter konstanter Zeit hinzuzufügen, wie dies beispielsweise mit einem C ++ -
vector<>
Container möglich ist. Die besten Antworten hier zeigen bisher nur die relativen Ausführungszeiten für verschiedene Lösungen bei einem Problem mit fester Größe, gehen jedoch nicht direkt auf die algorithmische Effizienz der verschiedenen Lösungen ein . In den Kommentaren unter vielen Antworten wird die algorithmische Effizienz einiger Lösungen erörtert, aber in jedem bisherigen Fall (Stand April 2015) kommen sie zu dem falschen Ergebnis.Die algorithmische Effizienz erfasst die Wachstumseigenschaften entweder zeitlich (Ausführungszeit) oder räumlich (Speicherbedarf), wenn die Problemgröße zunimmt . Das Ausführen eines Leistungstests für verschiedene Lösungen bei einem Problem mit fester Größe berücksichtigt nicht die Wachstumsrate der verschiedenen Lösungen. Das OP ist daran interessiert zu wissen, ob es eine Möglichkeit gibt, Objekte in "amortisierter konstanter Zeit" an eine R-Liste anzuhängen. Was bedeutet das? Lassen Sie mich zur Erklärung zunächst "konstante Zeit" beschreiben:
Konstantes oder O (1) Wachstum:
Wenn die zur Ausführung einer bestimmten Aufgabe erforderliche Zeit gleich bleibt, während sich die Größe des Problems verdoppelt , weist der Algorithmus ein konstantes Zeitwachstum auf oder, angegeben in der "Big O" -Notation, ein O (1) -Zeitwachstum. Wenn der OP "amortisierte" konstante Zeit sagt, bedeutet er einfach "auf lange Sicht" ... dh wenn die Ausführung einer einzelnen Operation gelegentlich viel länger als normal dauert (z. B. wenn ein vorab zugewiesener Puffer erschöpft ist und gelegentlich eine Größenänderung auf einen größeren erfordert Puffergröße), solange die langfristige durchschnittliche Leistung eine konstante Zeit ist, nennen wir sie immer noch O (1).
Zum Vergleich werde ich auch "lineare Zeit" und "quadratische Zeit" beschreiben:
Lineares oder O (n) Wachstum:
Wenn sich die für die Ausführung einer bestimmten Aufgabe erforderliche Zeit verdoppelt, während sich die Größe des Problems verdoppelt , weist der Algorithmus eine lineare Zeit oder ein O (n) -Wachstum auf.
Quadratisches oder O (n 2 ) Wachstum:
Wenn sich die zur Ausführung einer bestimmten Aufgabe erforderliche Zeit um das Quadrat der Problemgröße erhöht , weist der Algorithmus eine quadratische Zeit oder ein O (n 2 ) -Wachstum auf.
Es gibt viele andere Effizienzklassen von Algorithmen. Ich verweise auf den Wikipedia-Artikel zur weiteren Diskussion.
Ich danke @CronAcronis für seine Antwort, da ich neu bei R bin und es schön war, einen vollständig konstruierten Codeblock für eine Leistungsanalyse der verschiedenen auf dieser Seite vorgestellten Lösungen zu haben. Ich leihe seinen Code für meine Analyse aus, den ich unten dupliziere (in eine Funktion eingeschlossen):
Die von @CronAcronis veröffentlichten Ergebnisse scheinen definitiv darauf hinzudeuten, dass die
a <- list(a, list(i))
Methode zumindest für eine Problemgröße von 10000 am schnellsten ist, aber die Ergebnisse für eine einzelne Problemgröße berücksichtigen nicht das Wachstum der Lösung. Dazu müssen mindestens zwei Profiling-Tests mit unterschiedlichen Problemgrößen durchgeführt werden:Zunächst ein Wort zu den Werten min / lq / mean / median / uq / max: Da wir in einer idealen Welt für jeden von 5 Läufen genau die gleiche Aufgabe ausführen, können wir erwarten, dass es genau dasselbe dauert Zeitdauer für jeden Lauf. Der erste Lauf ist jedoch normalerweise auf längere Zeiten ausgerichtet, da der von uns getestete Code noch nicht in den Cache der CPU geladen ist. Nach dem ersten Durchlauf würden wir erwarten, dass die Zeiten ziemlich konsistent sind, aber gelegentlich kann unser Code aufgrund von Timer-Tick-Interrupts oder anderen Hardware-Interrupts, die nicht mit dem von uns getesteten Code zusammenhängen, aus dem Cache entfernt werden. Indem wir die Code-Snippets fünfmal testen, können wir den Code während des ersten Durchlaufs in den Cache laden und dann jedem Snippet 4 Chancen geben, ohne Störung durch externe Ereignisse vollständig ausgeführt zu werden. Deshalb,
Beachten Sie, dass ich mich für die erste Ausführung mit einer Problemgröße von 2000 und dann für 20000 entschieden habe, sodass sich meine Problemgröße vom ersten bis zum zweiten Lauf um den Faktor 10 erhöht hat.
Leistung der
list
Lösung: O (1) (konstante Zeit)Lassen Sie uns zunächst einen Blick auf das Wachstum der
list
Lösung, da wir sofort sagen kann , dass es die schnellste Lösung in beiden Profilläufe ist: Im ersten Durchgang dauerte es 854 Mikrosekunden (0,854 Milli Sekunden) 2000 „append“ Aufgaben auszuführen. Im zweiten Durchlauf dauerte es 8,746 Millisekunden, um 20000 "Anhängen" -Aufgaben auszuführen. Ein naiver Beobachter würde sagen: "Ah, dielist
Lösung weist ein O (n) -Wachstum auf, da mit zunehmender Problemgröße auch der Zeitaufwand für die Durchführung des Tests zunahm." Das Problem bei dieser Analyse ist, dass das OP die Wachstumsrate einer einzelnen Objekteinfügung wünscht , nicht die Wachstumsrate des Gesamtproblems. Wenn man das weiß, ist es klar, dass dielist
Die Lösung bietet genau das, was das OP will: eine Methode zum Anhängen von Objekten an eine Liste in O (1) -Zeit.Leistung der anderen Lösungen
Keine der anderen Lösungen kommt der Geschwindigkeit der
list
Lösung auch nur annähernd nahe , aber es ist informativ, sie trotzdem zu untersuchen:Die meisten anderen Lösungen scheinen eine Leistung von O (n) zu haben. Zum Beispiel
by_index
dauerte die Lösung, eine sehr beliebte Lösung, basierend auf der Häufigkeit, mit der ich sie in anderen SO-Posts finde, 11,6 Millisekunden, um 2000 Objekte anzuhängen, und 953 Millisekunden, um zehnmal so viele Objekte anzuhängen. Die Zeit des Gesamtproblems wuchs um den Faktor 100, so dass ein naiver Beobachter sagen könnte: "Ah, dieby_index
Lösung weist ein O (n 2 ) -Wachstum auf, da mit der Zunahme der Problemgröße um den Faktor zehn die für die Durchführung des Tests erforderliche Zeit zunahm um den Faktor 100. "Nach wie vor ist diese Analyse fehlerhaft, da das OP am Wachstum einer einzelnen Objekteinfügung interessiert ist. Wenn wir das gesamte Zeitwachstum durch das Größenwachstum des Problems dividieren, stellen wir fest, dass das Zeitwachstum anhängender Objekte nur um den Faktor 10 und nicht um den Faktor 100 zunimmt, was dem Wachstum der Problemgröße entspricht. Dieby_index
Lösung lautet also O. (n). Es sind keine Lösungen aufgeführt, die ein O (n 2 ) -Wachstum zum Anhängen eines einzelnen Objekts aufweisen.quelle
In den anderen Antworten wird nur der
list
Ansatz in O (1) angehängt, aber es entsteht eine tief verschachtelte Listenstruktur und keine einfache einzelne Liste. Ich habe die folgenden Datenstrukturen verwendet, sie unterstützen O (1) (amortisierte) Anhänge und ermöglichen die Rückkonvertierung des Ergebnisses in eine einfache Liste.und
Verwenden Sie sie wie folgt:
Diese Lösungen könnten zu vollständigen Objekten erweitert werden, die alle listenbezogenen Vorgänge selbst unterstützen, die jedoch für den Leser eine Übung bleiben.
Eine andere Variante für eine benannte Liste:
Benchmarks
Leistungsvergleich mit dem Code von @ phonetagger (der auf dem Code von @Cron Arconis basiert). Ich habe auch ein hinzugefügt
better_env_as_container
und dasenv_as_container_
ein bisschen geändert . Das Originalenv_as_container_
war kaputt und speichert nicht alle Nummern.Ergebnis:
Ich habe
linkedList
undexpandingList
und eine Inline-Version von beiden hinzugefügt . DasinlinedLinkedList
ist im Grunde eine Kopie vonlist_
, aber es konvertiert auch die verschachtelte Struktur zurück in eine einfache Liste. Darüber hinaus ist der Unterschied zwischen der Inline- und der Nicht-Inline-Version auf den Overhead der Funktionsaufrufe zurückzuführen.Alle Varianten von
expandingList
undlinkedList
zeigen die Leistung von O (1) -Anhängen, wobei die Benchmark-Zeit linear mit der Anzahl der angehängten Elemente skaliert.linkedList
ist langsamer alsexpandingList
und der Overhead des Funktionsaufrufs ist ebenfalls sichtbar. Wenn Sie also wirklich die Geschwindigkeit benötigen, die Sie bekommen können (und sich an den R-Code halten möchten), verwenden Sie eine Inline-Version vonexpandingList
.Ich habe mir auch die C-Implementierung von R angesehen, und beide Ansätze sollten O (1) für jede Größe angehängt werden, bis Ihnen der Speicher ausgeht.
Ich habe auch geändert
env_as_container_
, die Originalversion würde jedes Element unter dem Index "i" speichern und das zuvor angehängte Element überschreiben. Das, wasbetter_env_as_container
ich hinzugefügt habe, ist sehr ähnlich,env_as_container_
aber ohne dasdeparse
Zeug. Beide weisen eine O (1) -Leistung auf, haben jedoch einen viel größeren Overhead als die verknüpften / expandierenden Listen.Speicheraufwand
In der CR-Implementierung gibt es einen Overhead von 4 Wörtern und 2 Ints pro zugewiesenem Objekt. Der
linkedList
Ansatz weist eine Liste mit einer Länge von zwei pro Anhang zu, was insgesamt (4 * 8 + 4 + 4 + 2 * 8 =) 56 Bytes pro angehängtem Element auf 64-Bit-Computern entspricht (ohne Speicherzuweisungsaufwand, also wahrscheinlich näher an 64) Bytes). DerexpandingList
Ansatz verwendet ein Wort pro angefügtem Element sowie eine Kopie beim Verdoppeln der Vektorlänge, sodass eine Gesamtspeicherauslastung von bis zu 16 Byte pro Element erfolgt. Da sich der Speicher nur in einem oder zwei Objekten befindet, ist der Overhead pro Objekt unbedeutend. Ich habe mich nicht eingehend mit derenv
Speichernutzung befasst, aber ich denke, es wird näher daran liegenlinkedList
.quelle
list_
Option ist schneller und kann nützlich sein, wenn Sie nicht in eine normale Liste konvertieren müssen, dh wenn Sie das Ergebnis als Stapel verwenden.environment
was ich für nestoR verwendet habe.) Mein Engpass ist fast immer die menschliche Zeit, die ich mit Codierung und Datenanalyse verbracht habe, aber ich schätze die Benchmarks, die ich in diesem Beitrag gefunden habe. Was den Speicheraufwand angeht, würde es mir nichts ausmachen, bis zu kB pro Knoten für meine Anwendungen zu verwenden. Ich halte mich an großen Arrays usw. festIm Lisp haben wir es so gemacht:
obwohl es "Nachteile" war, nicht nur "c". Wenn Sie mit einer Empy-Liste beginnen müssen, verwenden Sie l <- NULL.
quelle
c()
Funktion kopiert ihre Argumente in einen neuen Vektor / eine neue Liste und gibt diese zurück.Willst du so etwas vielleicht?
Es ist keine sehr höfliche Funktion (Zuweisen
parent.frame()
ist etwas unhöflich), aber IIUYC ist das, wonach Sie fragen.quelle
Ich habe einen kleinen Vergleich der hier genannten Methoden gemacht.
Ergebnisse:
quelle
list = list
nicht nur der Gewinner ist - sondern um 1 bis 2 Ordnungen oder Größenordnungen!Wenn Sie die Listenvariable als Zeichenfolge in Anführungszeichen übergeben, können Sie sie über die folgende Funktion erreichen:
so:
oder für zusätzliche Gutschrift:
quelle
Ich bin mir nicht sicher, warum Sie nicht glauben, dass Ihre erste Methode nicht funktioniert. Sie haben einen Fehler in der Lappend-Funktion: Länge (Liste) sollte Länge (lst) sein. Dies funktioniert einwandfrei und gibt eine Liste mit dem angehängten Objekt zurück.
quelle
lappend()
, was ich bereitgestellt habe, und es scheint ungefähr so gut zu funktionieren wie c () und append (), die alle O (n ^ 2) -Verhalten aufweisen.Versuchen Sie diese Funktion lappend
und andere Vorschläge von dieser Seite Fügen Sie einer Liste einen benannten Vektor hinzu
Tschüss.
quelle
Ich denke, was Sie tun möchten, ist tatsächlich als Referenz (Zeiger) an die Funktion zu übergeben - erstellen Sie eine neue Umgebung (die als Referenz auf Funktionen übergeben wird) mit der hinzugefügten Liste:
Jetzt ändern Sie nur die vorhandene Liste (erstellen keine neue)
quelle
Dies ist eine einfache Möglichkeit, Elemente zu einer R-Liste hinzuzufügen:
Oder programmatisch:
quelle
append()
Funktion, aber es ist wirklich eine verkettete Funktion und es funktioniert nur mit Vektoren.append()
arbeitet an Vektoren und Listen, und es ist ein echtes Anhängen (was im Grunde das gleiche ist wie verketten, also sehe ich nicht, was Ihr Problem ist)in der Tat gibt es eine Subtilität mit der
c()
Funktion. Wenn Sie tun:Sie erhalten wie erwartet:
Wenn Sie jedoch eine Matrix mit hinzufügen
x <- c(x, matrix(5,2,2)
, enthält Ihre Liste weitere 4 Wertelemente5
! Du solltest es besser machen:Es funktioniert für jedes andere Objekt und Sie erhalten wie erwartet:
Schließlich wird Ihre Funktion:
und es funktioniert für jede Art von Objekt. Sie können schlauer sein und Folgendes tun:
quelle
Es gibt auch
list.append
aus demrlist
( Link zur Dokumentation )Es ist sehr einfach und effizient.
quelle
c()
oderlist
-Methode. Beide sind viel schneller.rlist::list.append()
, ist es im Wesentlichen ein Wrapperbase::c()
.Zur Validierung habe ich den von @Cron bereitgestellten Benchmark-Code ausgeführt. Es gibt einen großen Unterschied (zusätzlich zur schnelleren Ausführung auf dem neueren i7-Prozessor): Der
by_index
jetzt funktioniert fast genauso gut wie derlist_
:Als Referenz dient hier der Benchmark-Code, der wörtlich aus der Antwort von @ Cron kopiert wurde (nur für den Fall, dass er später den Inhalt ändert):
quelle
quelle
Dies ist eine sehr interessante Frage, und ich hoffe, dass mein Gedanke unten einen Lösungsweg dazu beitragen kann. Diese Methode gibt eine flache Liste ohne Indizierung an, verfügt jedoch über eine Liste und eine Auflistung, um die Verschachtelungsstrukturen zu vermeiden. Ich bin mir über die Geschwindigkeit nicht sicher, da ich nicht weiß, wie ich sie messen soll.
quelle
mylist<-list(1,2,3) mylist<-c(mylist,list(5))
So können wir das Element / Objekt mit dem obigen Code einfach anhängen
quelle