动态数组状结构中R' [英] Dynamic Array-Like Structure In R?

问题描述

在R编程语言，我怎么一个动态数组（作为维基百科描述）或等效的数据结构？我想具有以下属性的内容：

1. O（1）建立索引。




2. 平摊O（1​​）追加。




3. O（N）或更小的空间浪费。




4. 键入参数，即，可以容纳列表，用户定义的对象，功能，矩阵，等，不只是数字




5. 追加不点名应予以支持。因此，使用环境将不会削减它。

据我所知，使用列表不起作用因为追加到以下任一操作方式需要O（N）的时间，不摊销O（1）：

 富＆LT;  - 列表（）
富[长度（富）+ 1]]＆LT;  -  1
 

解决方案

而不是每次都追加到列表中，用一个固定长度preallocate它。然后，当列表已满，它的两倍，按照对维基百科文章的描述。这应该给你，你以后的表现。

 富＆LT;  - 矢量（名单，1000）＃填充列表，其中N＆GT;＆GT; 1000 ...
为（ⅰ序列（N））的
{
    富[[I]]＆LT;  -  ...    ＃如果列表已满，扩展它
    如果（我==长度（富））
        富＆LT;  -  C（富，载体（名单，长度（富）））
}
 

In the R programming language, how do I get a dynamic array (as described on Wikipedia) or equivalent data structure? I want something with the following attributes:

1. O(1) indexing.

2. Amortized O(1) appending.

3. O(N) or less wasted space.

4. Type parametric, i.e. can hold lists, user-defined objects, functions, matrices, etc., not just numbers.

5. Appending without naming should be supported. Therefore, using an environment won't cut it.

From what I can tell, using a list doesn't work because appending to one the following way takes O(N) time, not amortized O(1):

foo <- list()
foo[[length(foo) + 1]] <- 1

解决方案

Instead of appending to the list each time, preallocate it with a fixed length. Then when the list is full, double it, as per the description on the Wikipedia article. This should give you the performance you're after.

foo <- vector("list", 1000)

# populate the list, with N >> 1000...
for(i in seq(N))
{
    foo[[i]] <- ...

    # if the list is full, extend it
    if(i == length(foo))
        foo <- c(foo, vector("list", length(foo)))
}

这篇关于动态数组状结构中R'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！