c - 向量、矩阵和数据框是如何在 R 中实现的？

Question

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

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

score 4 · Accepted Answer

4

于 2012-12-19T17:00:14.347 回答

score 1 · Accepted Answer

来自 R Internals，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]可能会花费在所需元素之前遍历几个元素的开销被发现。

它是否正确？

score 0 · Accepted Answer

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

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

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

3 回答 3