Rollen Sie Ihre eigene verknüpfte Liste / Baum in R?

  • Ich versuche, mich mit den grundlegenden Konzepten der Programmiersprache R zu beschäftigen und finde es schwierig, da R eher auf Statistiken als auf Universalprogramme ausgerichtet ist. Ich kann nichts ähnlich wie Zeiger / Referenzen finden. Wie würden Sie eine verknüpfte Liste, einen Suchbaum usw. in der R-Sprache implementieren?

    Hinweis: Ich verstehe das, wenn Sie tatsächlich Ihre eigenen selbstreferenziellen Datenstrukturen einrollen R, es gibt wahrscheinlich einen besseren Weg, um das zu erreichen, was Sie zu erreichen versuchen. Ich glaube jedoch, dass eine Antwort mir helfen wird, die Gesamtstruktur und die Konzepte der Sprache besser zu verstehen.

    Bearbeiten: Im Hinblick auf Matt Shotwells Kommentar ist der Punkt dieser Frage, dass ich Ich möchte vernetzte Listen und Bäume sauber innerhalb von R schreiben, nicht als Erweiterung in C oder einer anderen Sprache. Wenn Sie es als Erweiterung verwenden oder mit geheimnisvollen Details des Interpreters mucken, wird der Zweck verfehlt.

    22 November 2011
    dsimcha
1 answer
  • Eine verknüpfte Liste in R kann als Vektor dargestellt werden, normalerweise als list. Sie müssen keinen speziellen Code schreiben, um auf das nächste und vorherige Element zu verweisen, da R dies durch Indizierung für Sie erledigt.

    Um ein neues Element zur Liste hinzuzufügen, behalten Sie es einfach bei verfolgen Sie die Länge und ordnen Sie sie der nächsten Zeile zu.

     lst <- list() # creates an empty (length zero) list
    lst[[1]] <- 1 # automagically extends the lst
    lst[[2]] <- 2 # ditto
     

    Dies kann wegen langer Listen ineffizient sein die Art, wie R mit dem Speicher umgeht. Erstellen Sie nach Möglichkeit die Liste im Voraus und weisen Sie deren Inhalt zu, sobald sie verfügbar sind.

     lst <- list(1, 2, 3, 4, 5)    # a list of 5 items
    
    lst <- vector("list", 10000)  # 10000 NULLs
    lst[[1]] <- 1
    lst[[10000]] <- 10000  # lst now contains 1, NULL, ..., NULL, 10000
     

    Löschen eines Elements Aus der Liste können Negativindizes erstellt werden.

     lst <- list(1, 2, 3, 4, 5)
    lst <- lst[-2]  # now contains 1, 3, 4, 5
     

    Ein Baum ist nur eine Liste, die andere Listen enthält.

     tree <- list(list(1, 2), list(3, list(4, 5)))
    
    # left child: list(1, 2)
    tree[[1]]
    
    # right child
    tree[[2]]
    
    # right child of right child:list(4, 5)
    tree[[2]][[2]]
     

    Standardmäßig gibt es keine integrierte Durchsetzung der Struktur, z. B. nur zwei Kinder pro Knoten für eine Binärdatei Baum. Über S4-Klassen stehen strukturiertere Ansätze zur Verfügung, aber dies erledigt den Job in der Not.

    22 November 2011
    Hong Ooistatistician_in_training