jak wektory, macierze i ramki danych zaimplementowane w R?

Question

Próbowałem dowiedzieć się o różnych strukturach danych używanych w popularnych językach, z którymi mam doświadczenie, takich jak listy i słowniki w Pythonie, tablice asocjacyjne w PHP (głównie tabele mieszania), wektory w C++ itd.

Mam wielu kolegów, którzy używają R religijnie i zastanawiałem się, w jaki sposób wektory, matryce i ramki danych są implementowane w R. Jakie są ich mocne i słabe strony? Przeglądałem kod źródłowy, ale nie mogłem znaleźć samych struktur danych. Gdzie w kodzie źródłowym znajdują się te definicje?

Answer 1

Jak już wspomniano, zapoznaj się z instrukcją "R internals", a także this part of "Writing R extensions".

Answer 2

Od R Internals, 1,1 SEXPs:

... podstawowe cegiełki obiektów R są często zwane węzły ... Oba typy struktury węzła mają na pierwszych trzech pól 32-bit spxinfo nagłówek, a następnie trzy wskaźniki (do atrybutów i poprzedniego i następnego węzła na liście podwójnie połączonej)

Wektory w R są zaimplementowane jako lista podwójnie połączona. I nawet wydaje się, że nie ma struktury danych mniejszej niż lista połączona z jednym węzłem. To oczywiste:

> a <- 4 
> a[1] 
4 

Jak wspomniano przez innych: builtin.c ma do_makevector i do_makelist i array.c ma źródło do_matrix. Ponadto array.c zawiera źródło dla allocMatrix i memory.c zawiera źródło dla allocVector.

Podczas gdy wiele rzeczy, które się działo, było nad moją głową, wydaje się oczywiste, że macierz jest po prostu podwójnie połączoną listą podwójnie powiązanych list. Uważam (choć jestem pewien), że nazwy wierszy i kolumn (podobnie jak te przechowywane w ramce danych) są przechowywane w "atrybutach" każdej listy.

Odpowiedzią na "mocne i słabe strony" implementacji struktur danych byłyby (z mojej ograniczonej wiedzy) listy podwójnie powiązane, które mają siłę w tym, że dynamiczna alokacja pamięci jest prostsza i nie wymaga narzut kopiowania i ponownego przydzielania całej tablicy, a jej słabością (w zależności od tego, ile wskaźników jest na liście: głowa, ogon, środek, ćwiartki, itd.) uzyskanie dostępu do losowej wartości v[99] może przejąć obciążenie iteracyjne przez kilka elementy przed znalezieniem pożądanego.

Czy to prawda?

Answer 3

Nieco późno, ale chciałem wskazać błąd w jednej z pozostałych odpowiedzi i udzielić jednoznacznej odpowiedzi. Spójrz na internals instrukcji:

https://cran.r-project.org/doc/manuals/R-ints.html#The-_0027data_0027

Czytaj początku tej sekcji, a wejście do 'INTSXP'. Wydaje się, że wektory całkowite są implementowane jako tablica C int. Podobnie dla "REALSXP" i "CHARSXP".

Wdrożenie go jako listy połączonej byłoby zbyt powolne.