1

データの長い配列 ( n 個のエンティティ) があります。この配列内のすべてのオブジェクトには、いくつかの値があります (オブジェクトのm値としましょう)。そして、私は次のようなサイクルを持っています:

myType* A; 

// reading the array of objects   
std::vector<anotherType> targetArray;
int i, j, k = 0;
for (i = 0; i < n; i++)
     for (j = 0; j < m; j++)
     { 
         if (check((A[i].fields[j]))
         {
             // creating and adding the object to targetArray
             targetArray[k] = someGenerator(A[i].fields[j]);
             k++;
         }
     }

場合によっては、( n * m ) /10 以下のn * m の有効なオブジェクトがあります。 問題は、メモリをどのように割り当てるかです。
targetArray

  1. targetArray.reserve(n*m);
    // Do work
    targetArray.shrink_to_fit();

  2. オブジェクトを生成せずに要素を数えてから、必要なだけのメモリを割り当てて、もう一度サイクルを実行します。

  3. 新しいオブジェクトが作成される反復ごとに配列のサイズを変更します。

私の方法のそれぞれに大きな戦術的誤りがあることがわかります。それを行う別の方法はありますか？

4

2 に答える 2

6

ここで行っていることは、時期尚早の最適化と呼ばれます。デフォルトでは、std::vector新しいオブジェクトを格納するためのメモリが不足すると、メモリ フットプリントが指数関数的に増加します。たとえば、最初の apush_backは 2 つの要素を割り当てます。3番目push_backはサイズなどを2倍にします。そのままpush_backにして、コードを機能させます。

上記のアプローチが設計のボトルネックであることが判明した場合にのみ、メモリ割り当ての最適化について考え始める必要があります。reserve()それが起こった場合、最善の策は、有効なオブジェクトの数について適切な近似を考え出し、ベクトルを呼び出すことだと思います。あなたの最初のアプローチのようなもの。ベクトルは縮小するのが好きではないため、実装に合わせて縮小することが正しいことを確認してください。を使用する必要がありますswap。

すべてのステップで配列のサイズを変更するのは良くありstd::vectorません。一生懸命努力しない限り、実際にはそうしません。

オブジェクトのリストを余分に循環させることは役に立ちますが、簡単に CPU サイクルを浪費したり、CPU キャッシュを肥大化させたりする可能性があるため、悪影響を与える可能性もあります。疑わしい場合は、プロファイリングしてください。

于 2012-07-01T17:55:56.650 に答える
4

典型的な方法は、targetArray.push_back() を使用することです。これにより、必要に応じてメモリが再割り当てされ、データを 2 回通過する必要がなくなります。メモリを再割り当てするためのシステムがあり、ベクトルが大きくなるにつれて再割り当てが少なくなり、非常に効率的になります。

ただし、check() 関数が非常に高速な場合は、データを 2 回調べて、必要なメモリ量を判断し、ベクトルを最初から適切なサイズにすることで、パフォーマンスが向上する可能性があります。ただし、プロファイリングで本当に必要であると判断された場合にのみ、これを行います。

于 2012-07-01T17:44:14.823 に答える