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はオプションかもしれませんが（ただし、どのようにすればよいかわかりません）、これらの操作を何度も繰り返す必要があるため、タスクにはかなり時間がかかると思います。 Rに返送する必要はありません。

編集：

目標。ここでの目標はスピードを上げることです。コードをRからC++に変換するのは明らかな理由です（他にもあるかもしれません。それが私が明確にする理由です）。ただし、メンテナンスと簡単な実装が2番目になります。

操作の精度が向上します。アルゴリズムは次のとおりです。配列に大量のデータ（複数行）を追加してから、最小値を抽出して削除します。繰り返す。そのため、並べ替えられたベクトルを探すのではなく、配列が頻繁に更新（追加）されるため、常に最も低いデータをオンデマンドで検索します。速いと思いますが、間違っているかもしれません。

4

5 に答える 5

1

ベクトルのベクトルはあなたが望むことをするべきだと思います。min-findingを手動で実装する必要があります（2つのネストされたループ）。これは、オーバーヘッドを追加せずに実行できる最速です。各行の最小要素の位置を行とともに追跡することで、最小値の検出を高速化できます。

于 2011-07-13T03:11:53.270 に答える
1

この質問は少し古くなっていますが、私はこの種のタスクに関連するいくつかの一般的な観察を提供すると思いました。

行のコレクションを順序付けられた状態に保つ場合（which.min戦略の前提となる可能性があります）、これが一般的な操作である場合、効率的にサポートするのが最も難しい操作は行の挿入です。リストは二分法の検索には適していないため、データ構造を使用しないことは難しいでしょう。list<>その結果、which.minが線形演算に変わる可能性があります。

順序付けされていないコレクションを保持している場合は、フレームの終わりから削除によって空いた行にレコードをコピーし、行数から1を引くことで、削除を処理できます。または、削除カウントがなどのしきい値に達するまで、boolの別のベクトルで削除にフラグを立てることができsqrt(N)ます。その時点で、合体コピーを実行します。挿入/削除については、償却されたO（N ^ 2）よりも優れていますが、which.minは、毎回ベクトル全体を線形検索します。

min / max要素を一般的な操作として識別する必要がある場合に行う通常のことは、ある種の優先キューを使用することであり、インデックス付けされた列のデータを複製する場合があります。リスト以外の実装での削除操作の結果として移動しているデータフレームの行と、1つのデータ列の優先度付きキューを同期するのは難しいでしょう。

行が単に削除済みとしてマークされている場合、優先キューは同期されたままになります（ただし、適切な行が得られるまで、後で削除される行に対応するキューからポップされた要素を破棄する必要があります）。合体コピーの後、優先キューのインデックスを再作成します。これは、あまり頻繁に行わない場合は非常に高速です。通常、構造を大きなサイズに拡張するのに十分なメモリがある場合、構造が縮小した場合にメモリを元に戻すように過度に圧迫されることはありません。あなたが今までに明らかではありません構造が最高水準点に近いサイズで存続する傾向がある場合は合体する必要がありますが、以前に削除された行に新しいデータを書き込んだため、優先キューが期限切れになり、同じストレージ行への新しい参照があった場合に注意してください。効率を上げるために、補助リストを使用して削除済みとマークされた行を追跡し、挿入された行のストレージを線形時間未満で見つけることができる場合があります。

優先キューの腸から古いアイテムを抽出するのは難しい場合があります。これらはキューの一番上で削除するためだけに設計されている傾向があるためです。多くの場合、古いアイテムをそこに残し、後で表面化した場合は無視するように手配する必要があります。

パフォーマンスの目標を持ってC++に入るとき、猫の皮を剥ぐ方法はたくさんあります。必要なすべての操作の実行時間を長くするには、元のRコードが表現したものよりもパフォーマンスのトレードオフについてはるかに正確である必要があります。

于 2011-08-30T05:40:02.360 に答える
0

Adata.frameは実際には単なるベクトルのリストです。C ++では、実際には、行の追加を困難にするベクトルのリストしかありません。

行を削除するためのIdem-Rcppは元のR表現で機能するため、残りのすべての値を常にコピーする必要があります。

同等のものについてwhich.min()：私はそれがリストに一度出てきて、STLイディオムで簡単なことをすることができると思います。APIにそれがあったことを覚えていません。

于 2011-07-13T03:12:01.133 に答える
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を参照）を使用するか、ラムダ、または何よりもC ++ 0xのラムダをブーストする可能性が高くなります）

そして、このコード本体：

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

いいえ、data.frameはvectorのベクトルよりも少し複雑です。

すべての場合において、速度を上げるための最も簡単な設計は、各列を型付きベクトルに格納し、行のヘッダーとしてリストを作成することです。次に、その上に煩わしいリストを作成します。

于 2014-02-18T17:30:05.253 に答える