2

我正在将 R 代码翻译成 c++，我想找到一个等效的（最佳）结构，它允许与数据帧相同类型的操作，但在 c++ 中。

操作是：

  • 添加元素（行）
  • 从索引中删除元素（行）
  • 获取最小值的索引

例如：

a <- data.frame(i = c(4, 9, 3, 1, 8, 2, 7, 10, 6, 6), 
                j = c(8, 8, 8, 4, 3, 9, 1, 4,  8, 9) , 
                v = c(1.9, 18, 1.3, 17, 1.5, 14, 11, 1.4, 18, 2.0), 
                o = c(3, 3, 3, 3, 1, 2, 1, 2, 3, 3))

a[which.min(a$v), c('i', 'j')] # find lowest v value and get i,j value
a <- a[-which.min(a$v)] # remove row from index
a <- cbind(a, data.frame(i = 3, j = 9, v = 2, o = 2)) # add a row

当我使用 Rcpp 时，Rcpp::DataFrame 可能是一个选项（我不知道我会怎么用 which.min 它），但我想这对于任务来说相当慢，因为这些操作需要重复很多次并且我不需要将它运回 R。

编辑：

目标。只是说清楚这里的目标是提高速度。这是将代码从 R 转换为 C++ 的明显原因（可能还有其他原因，这就是我澄清的原因）。但是，维护和易于实施排在第二位。

操作更精确。算法是：向数组中添加大量数据（多行），然后提取最小值并将其删除。重复。这就是为什么我不会选择排序向量，而是总是根据需要搜索最低数据，因为数组经常更新（添加）。我认为它更快，但也许我错了。

4

5 回答 5

1

这个问题有点陈旧，但我想我会提供一些与此类任务有关的一般性意见。

如果您将行集合保持在有序状态，这可能是您的 which.min 策略的假设，那么有效支持的最困难的操作是行插入，如果这是一种常见的操作。您将很难不使用list<>数据结构，这可能会导致 which.min 变成线性运算，因为列表不适合二分搜索。

如果您保留一个无序集合，您可以通过将记录从帧末尾复制到删除空出的行并从行数中减去 1 来处理删除。或者，您可以只使用另一个 bool 向量标记删除，直到删除计数达到阈值，例如sqrt(N)，此时您执行合并复制。对于插入/删除，您会比摊销 O(N^2) 更好，但 which.min 将是每次对整个向量进行线性搜索。

当您需要将最小/最大元素识别为常见操作时，通常要做的事情是使用某种优先级队列，有时会复制索引列的数据。在我的脑海中，将一个数据列上的优先级队列与由于非列表实现中的删除操作而移动的数据帧的行同步是很棘手的。

如果这些行仅被标记为已删除，则优先级队列将保持同步（尽管您必须丢弃与随后删除的行相对应的从队列中弹出的元素，直到您得到一个好的元素）；在合并副本之后，您将重新索引优先级队列，如果您不经常这样做，这将非常快。通常，如果您有足够的内存来将结构扩大到更大的大小，那么如果结构缩小，您就不会过度要求重新归还内存；你并不明显如果您的结构倾向于以接近高水位线的大小持续存在，则需要合并，但请注意优先级队列已过期和对同一存储行的新引用的情况，因为您将新数据写入先前删除的行. 为了提高效率，有时您最终会使用辅助列表来跟踪标记为已删除的行，这样您就可以在不到线性的时间内找到插入行的存储空间。

很难从优先队列的内部提取陈旧的项目，因为这些项目往往被设计为仅在队列顶部移除；通常，您必须将陈旧的物品留在那儿，并安排在以后出现时忽略它们。

当你带着性能目标进入 C++ 时，有很多方法可以让猫剥皮，你需要比原始 R 代码表达的性能权衡更精确，以获得所有必需操作的良好执行时间。

于 2011-08-30T05:40:02.360 回答
1

我认为向量的向量应该做你想要的。您需要手动实现最小值查找（两个嵌套循环），这是您在不增加开销的情况下可以做到的最快速度。您可以通过跟踪每行中最小元素的位置以及该行来加快最小查找速度。

于 2011-07-13T03:11:53.270 回答
0

C++ 术语中的 R数据框是对象的容器（R矩阵可能是向量的向量，但如果您关心效率，则不太可能以这种方式实现它。）

所以，用这个类表示数据框：

class A{
public:
  int i,j,o;
  double v;
public:
  A(int i_,int j_,int v_,int o_):i(i_),j(j_),v(v_),o(o_){}
}

并准备这个算法参数函数来帮助找到最小值：

bool comp(A &x,A &y){
return x.v<y.v;
}

（在生产代码中，我更可能使用仿函数对象（参见 Meyer 的 Effective STL，第 46 项），或者boost lambda，或者最重要的是 C++0x 的 lambdas）

然后这个代码体：

std::vector<A> a;
a.push_back(A(4,8,1.9,3));
a.push_back(A(9,8,18,3));
a.push_back(A(1,4,1.3,3));
//...

std::vector<A>::iterator lowest=std::min_element(a.begin(),a.end(),comp);
std::cout<< lowest->i << ',' << lowest->j <<"\n";

a.erase(lowest);

a.push_back( A(3,9,2,0) );

根据您实际在做什么，首先排序可能会更有效a，最好先排序。然后，如果您想删除最低的项目，您只需截断向量。如果您实际上是在到处删除，并且which.min()只是为了举例，您可能会发现链表更有效。

于 2011-08-15T07:02:33.067 回答
0

Adata.frame实际上只是一个向量列表。在 C++ 中，我们实际上只有那些使添加行变得困难的向量列表。

删除行的同义词——因为 Rcpp 适用于原始 R 表示，您总是需要复制所有剩余的值。

至于which.min()等价物：我认为一旦出现在列表中，您就可以使用 STL 习语做一些简单的事情。我不记得我们在 API 中有这个。

于 2011-07-13T03:12:01.133 回答
0

不，data.frame 比向量的向量复杂一点。

我可能会说，在所有情况下，最简单的速度设计是将每一列存储在一个类型化的向量中，并创建一个列表作为行的标题。然后在它之上创建一个侵入性列表。

于 2014-02-18T17:30:05.253 回答