come sono implementati vettori, matrici e frame di dati in R?

Question

Ho cercato di conoscere le diverse strutture dati utilizzate nei linguaggi popolari che ho esperienza con elenchi e dizionari in Python, array associativi in ​​PHP (essenzialmente tabelle hash), vettori in C++, ecc.

Ho molti colleghi che usano R religiosamente e mi chiedevo come i vettori, le matrici e le cornici di dati siano implementati in R. Quali sono i loro punti di forza e di debolezza? Stavo guardando il codice sorgente ma non sono riuscito a trovare le strutture dei dati. Dove si trovano queste definizioni nel codice sorgente?

Answer 1

Come già accennato, consultare il manuale "R internals" e this part of "Writing R extensions".

Answer 2

Da R Internals, 1.1 SEXPs:

... gli elementi di base di oggetti R sono spesso chiamati nodi ... Entrambi i tipi di struttura del nodo hanno come loro primi tre campi a 32 bit spxinfo intestazione e quindi tre puntatori (agli attributi e al nodo precedente e successivo in una lista doppiamente collegata)

Così i vettori in R sono implementati come una lista doppiamente collegata. Inoltre, sembra che non ci sia una struttura di dati più piccola di una lista collegata a un nodo singolo. Ciò è evidente dal:

> a <- 4 
> a[1] 
4 

Come detto da altri: builtin.c ha do_makevector e do_makelist, e array.c ha la sorgente per do_matrix. Inoltre, array.c contiene la fonte per allocMatrix e memory.c contiene la fonte per allocVector.

Mentre un sacco di cose che stavano succedendo erano sopra la mia testa, sembra evidente che una matrice sia semplicemente una lista doppiamente collegata di liste doppiamente collegate. Credo (anche se non sono sicuro) che i nomi di riga e colonna (come quelli memorizzati in un frame di dati) sono memorizzati negli 'attributi' di ogni lista.

La risposta a "quali sono i punti di forza e di debolezza" dell'implementazione delle strutture di dati sarebbe che (dalla mia conoscenza limitata) le liste doppiamente collegate hanno una forza in quella allocazione dinamica della memoria è più semplice e non richiede il sovraccarico di copia e riallocazione di un intero array, e la debolezza è che (a seconda di quanti puntatori ci sono nella lista: testa, coda, centro, quarti, ecc.) l'accesso a un valore casuale v[99] può richiedere l'overhead di iterare attraverso diversi elementi prima che venga trovato quello desiderato.

È corretto?

Answer 3

Un po 'in ritardo, ma voleva segnalare un errore con una delle altre risposte e dare una risposta esplicita. Guarda manuale internals:

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

leggere l'inizio di questa sezione, e la voce di 'INTSXP'. Sembra che i vettori integer siano implementati come una matrice di C int. Analogamente per "REALSXP" e "CHARSXP".

L'implementazione come elenchi concatenati sarebbe stata proibitivamente lenta.