矢量、矩阵和数据帧在R中是如何实现的？

Question

我一直在尝试学习流行语言中使用的不同数据结构，如Python语言中的列表和字典、PHP中的关联数组(本质上是哈希表)、C++中的向量等。

我有很多使用R的同事，我想知道矢量、矩阵和数据帧是如何在R中实现的，它们的优点和缺点是什么？我看了看源代码，但我找不到数据结构本身。这些定义在源代码中的什么位置？

Answer 1

如前所述，请查看this part of "Writing R extensions"和"R internals"手册。

Answer 2

从R内部，1.1 SEXP：

...R对象的基本构建块通常称为节点...这两种类型的节点结构的前三个字段都有一个32位的spxinfo头，然后是三个指针(指向属性以及双向链表中的上一个和下一个节点)

因此，R中的向量被实现为双向链表。而且，甚至看起来没有比单节点链表更小的数据结构。这一点从以下几个方面体现出来：

> a <- 4
> a[1]
4

正如其他人所提到的：builtin.c有do_makevector和do_makelist，array.c有do_matrix的源代码。此外，array.c包含allocMatrix的源代码，memory.c包含allocVector的源代码。

虽然发生的许多事情都超出了我的理解，但很明显，矩阵只是一个双向链表的双向链表。我相信(尽管我不确定)行名和列名(就像那些存储在数据框中的名称)存储在每个列表的“属性”中。

对数据结构实现的“优缺点”的回应是(据我有限的知识)双向链表的优点是动态内存分配更简单，不需要复制和重新分配整个数组的开销，缺点是(取决于有多少指针指向列表:头、尾、中间、季度等)。访问随机值v[99]会占用在找到所需元素之前遍历多个元素的开销。

这是正确的吗？

Answer 3

有点晚了，但想指出其他答案中的一个错误，并给出明确的答案。查看内部手册：

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

阅读本节的开头，以及“INTSXP”的条目。似乎整数向量被实现为一个C int数组。'REALSXP‘和'CHARSXP’也是如此。

将其实现为链表将会非常慢。