ベクトルを何回もpush_backするための速い方法

Question

私はC++コードのボトルネックを特定しました。私の目標はそれをスピードアップすることです。条件が真であれば、あるベクトルから別のベクトルにアイテムを移動しています。私はC++でこれを行う方法をハッキングしてきたし、それが正常に動作している

my_vector = [x for x in data_vector if x > 1] 

：Pythonで

、これを行うのニシキヘビの方法は、リストの内包表記を使用することです。しかし、私はこのループをwhileループで何百万回も呼びますが、それは遅いです。私はメモリ割り当てについて多くのことを理解していませんが、私は自分の問題がpush_backを使ってメモリを何度も何度も割り当てていると仮定しています。このコードをスピードアップするために私のメモリを別々に割り当てる方法はありますか？ （my_vectorは、for -loopが完了するまでどのくらいの大きさでなければならないのかわかりません）。

std::vector<float> data_vector; 
// Put a bunch of floats into data_vector 
std::vector<float> my_vector; 

while (some_condition_is_true) { 
    my_vector.clear(); 
    for (i = 0; i < data_vector.size(); i++) { 
     if (data_vector[i] > 1) { 
      my_vector.push_back(data_vector[i]); 
     } 
    } 
    // Use my_vector to render graphics on the GPU, but do not change the elements of my_vector 
    // Change the elements of data_vector, but not the size of data_vector 
} 

Answer 1

使用std::copy_if、当初my_vector積立金data_vector.size()（これはあなたの述語が真と評価できたために要素の最大可能な数であるとして）：

std::vector<int> my_vec; 
my_vec.reserve(data_vec.size()); 
std::copy_if(data_vec.begin(), data_vec.end(), std::back_inserter(my_vec), 
    [](const auto& el) { return el > 1; }); 

（注）reserveを避けることができあなたの述語が真であると評価される回数がdata_vectorのサイズよりはるかに小さいと予想するなら、ここに電話してください。

Answer 2

最初に必要な新しい要素の数を数えるだけでコードを2回実行します。次に、reserveを使用して、必要なメモリをすべて割り当ててください。

while (some_condition_is_true) { 
    my_vector.clear(); 
    int newLength = 0; 
    for (i = 0; i < data_vector.size(); i++) { 
     if (data_vector[i] > 1) { 
      newLength++; 
    my_vector.reserve(newLength); 

    for (i = 0; i < data_vector.size(); i++) { 
     if (data_vector[i] > 1) { 
      my_vector.push_back(data_vector[i]); 
     } 
    } 
    // Do stuff with my_vector and change data_vector 
} 

Answer 3

my_vectorの容量がすぐに十分になるはずであるので、whileループが何度も実行された場合は、特に問題はありません。my_vectorが問題になります。

しかし、あなたはdata_vectorの大きさに対応するmy_vectorでちょうど余力できることを確認することにする：あなたは、Linux上にある場合

my_vector.reserve(data_vector.size()); 

while (some_condition_is_true) { 
    my_vector.clear(); 
    for (auto value : data_vector) { 
     if (value > 1) 
      my_vector.push_back(value); 
    } 
} 

Answer 4

あなたはあなたのケースではボトルネックとなっているstd::vector再配分を防ぐためにmy_vectorのためのメモリを予約することができます。 reserveは余分なコミットメントのためにメモリを浪費しませんので、予約金額の大まかな見積もりはあなたのニーズに合っています。あなたの場合、data_vectorのサイズで十分でしょう。このコード行whileループは、ボトルネックを修正する必要があります前に：

my_vector.reserve(data_vector.size()); 

Answer 5

クエリの他のユーザーが投稿し様々な偉大なソリューションがありますが、あなたが多くをそうでない、メモリ割り当てのための多くの説明はまだありませんようです理解していますので、このトピックに関する知識をお伝えしたいと思います。お役に立てれば。

まず、C++には、stack,heap,data segmentのようなメモリがいくつかあります。

Stackはローカル変数用です。たとえば、自動的に割り当てが解除され、その操作が非常に高速で、サイズがOSに依存して小さく、stackにいくつかのKBのデータを格納するとメモリがオーバーフローする可能性があるなど、重要な機能がいくつかあります。等である。

Heapのメモリにグローバルにアクセスできます。その重要な特徴としては、必要に応じてサイズを動的に拡張することができ、そのサイズはより大きく（stackよりはるかに大きい）、その操作はstackより遅く、手動でメモリを解放する必要がありますプログラム終了時に自動的に解放されます）。

Data segmentは、グローバル変数と静的変数です。実際には、このメモリはさらに小さな部分に分割することができます。 BBS。

あなたのケースでは、vectorが使用されます。実際、vectorの要素は、内部の動的配列、つまり動的な配列サイズを持つ内部配列に格納されます。初期のC++では、stackメモリ上に動的配列を作成することができますが、もはやそうではありません。動的配列を作成するには、heapに作成する必要があります。したがって、vectorの要素は内部ダイナミック配列heapに格納されます。実際には、配列のサイズを動的に増やすには、プロセス、すなわちmemory reallocationが必要です。しかし、vectorユーザーが自分のvectorを拡大し続けると、reallocationのオーバーヘッドコストが高くなります。それに対処するために、vectorは、現在の必要性よりも大きい、将来の潜在的な使用のためのメモリを割り当てるメモリを最初に割り当てる。したがって、あなたのコードでは、push_back()が呼び出されるたびにmemory reallocationが実行されるわけではありません。しかし、コピーするvectorがかなり大きい場合、将来の使用のために予約されたメモリは十分ではありません。その後、memory allocationが発生します。それに取り組むには、vector.reserve()を使用することができます。

私は初心者です。うまくいけば、私は私の分け前に間違いをしなかった。 これが役立つことを願っています。